How is programming a quantum algorithm different? What would a C like language look like if it was designed for qubits? Would types change?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.
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.
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.
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!