Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

How is programming a quantum algorithm different? What would a C like language look like if it was designed for qubits? Would types change?

share|improve this question

closed as too broad by MichaelT, Kilian Foth, World Engineer Sep 11 '13 at 22:26

There are either too many possible answers, or good answers would be too long for this format. Please add details to narrow the answer set or to isolate an issue that can be answered in a few paragraphs.If this question can be reworded to fit the rules in the help center, please edit the question.

    
Note: Im not sure if this is a valid question. Sorry if it is not. –  Dokkat Aug 16 '12 at 14:07
4  
I think it is. Then again, I don't really know the rules of this site very well. And I don't really have a great answer to this question, but I know of this algorithm that could be used to factor integers much more efficiently: arxiv.org/abs/0812.0380 –  John Davis Aug 16 '12 at 14:15
2  
I think though this topic is still at scientific research, the basics of an hypothetical quantum computer are AFAIK well known, so the question should be answerable by a domain expert (which I am not). So I vote not to close it. –  Doc Brown Aug 16 '12 at 15:17

3 Answers 3

What would a C like language look like if it was designed for qubits? Would types change?

It would be so drastically different as to be incomprehensible as C.

The main issue (as I understand it) is that quantum computing does not work in a nice imperative manner 'do this, then that, then this other thing'. Trying to force C's ability to do that into the 'processor' of quantum computer will be if not impossible, wildly inefficient.

Programming algorithms for quantum computers (again, as I understand them) tend to be closer to functional programming style map/reduce, since quantum computing allows all of the candidates in the 'reduce' part to exist concurrently and "fall out" of the computer when observed.

Note that there are some existing algorithms for quantum computers, even though the devices don't exist to run them. Simon's algorithm for example.

share|improve this answer
    
ELI5 for a quantum algorithm would be great. –  Dokkat Aug 16 '12 at 15:30

When I looked into this some time ago, it was clear that quantum algorithms, while not particularly fast, permit exponentially massive parallelism. So they will shine in cases involving search in spaces that are not practical with sequential hardware, even massively parallel sequential hardware.

One property of quantum algorithms is that they have to be reversible. Any given algorithm can be translated into one that is reversible, by adding to it enough record-keeping to allow it to be run backward.

Another property is that getting an answer out of a quantum algorithm is a hit-and-miss affair, because what you get at the end of a computation is multiple answers, each with its own probability. It needs to be run in such a way that the answer you want has high probability. This may involve running the algorithm forward and backward multiple times.

Check out Grover's Search Algorithm.

I was personally interested in how this could be applied to verification of software correctness. Now we test software by throwing a bunch of test inputs at it and (to be overly simple) seeing if it hits an Assert. In a quantum computer it might be possible to run it in parallel against a much denser set of inputs and see if any of those cases hit an Assert.

Like if the input to the algorithm were 128 bytes, or 1024 bits, there are 2^1024 or 10^308 possible different inputs. There is no way to test that many inputs on a conventional computer, but a quantum computer could try them all in parallel.

share|improve this answer
1  
Checking out Grover's Search Algorithm... OH GOD! I wasn't ready for that! –  Philip Aug 16 '12 at 19:00
    
@Philip: I know the math is pretty off-putting, but the key idea is the rotation about the mean, which has the effect of transferring probability to the answer state. Then you run back to the beginning and run forward and do it again, a certain number of times. Then if you do the observation, you've maximized the probability of seeing the answer state. –  Mike Dunlavey Aug 16 '12 at 19:38
    
You see, it's really not so bad when you say it like that. I guess I'm not familiar with the notation they're using or quantum circuits. The page on quantum algorithms is likewise intimidating. I believe that Qubit is the place to start. (Simple wikipedia has a page on Quantum computers, but it could use some work) –  Philip Aug 16 '12 at 19:53
    
@Philip: Suppose you have a 1024-entry table, so it takes 10 bits to index it. You have a 10-(qu)bit register, and it has 1024 possible states. OK, so you create a universe in which the register is 0, another in which it is 1, up to 1024 parallel universes. Then the quantum "instructions" operate on all of these in parallel. Each universe has an "amplitude vector", whose magnitude is its probability, but it also has a direction, and those are being manipulated. Since the collection of 1024 vectors has a non-zero average vector, the rotation makes one bigger, the rest smaller. –  Mike Dunlavey Aug 16 '12 at 20:02

In order to make the most effective possible use of a quantum computer, one needs to be able to deal with inputs and outputs that are states of a quantum register, for which there is really no classical analogue. Speaking from some years of experience in the field of quantum information, I must warn you that no one really has a good intuition for this beyond the abstract mathematics of C* algebras, and I'm told that even this intuition turns out to be inadequate if you start wondering about relativity theory.

The class of problems that are efficiently solvable on a quantum computer is known as BQP, for Bounded Quantum Polynomial. This is the quantum version of BPP, and you can find more information in this paper: http://www.scottaaronson.com/papers/bqpph.pdf

I was told just last night by a quantum algorithms researcher that there is a very important problem that is BQP-complete: solving a linear system of N equations. Classically, this is solvable in O(N) steps with Gaussian elimination. The Harrow-Hassidim-Lloyd algorithm (http://arxiv.org/abs/0811.3171) solves it in polylog(N), provided you are willing to accept an answer that has the solution encoded as a quantum state. If you want to make full use of a quantum computer, it therefore seems necessary for you to have a type corresponding to the state of a quantum register.

Though I am a little outside of my particular expertise right now, I would hazard a guess that you would be able to program a quantum computer as long as you had access to a type corresponding to magic states. That's a difficult concept, though, that requires quite some study of the subject.

Be warned that we are a very long time from having a quantum programming language, because we are at a very primitive stage of quantum computing research. Asking for a quantum C right now would be like going to Alan Turing and asking him to design Python. We haven't even got the quantum version of the vacuum tube yet!

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.