The type of quantum computer discussed at the site of the OpenQbit project, now defunct, incorporates another new computer idea: reversible computation. I was very skeptical when I first heard of this idea: that computations which do not destroy information can be made to run without using energy. But while that would be difficult to do on a conventional scale, that it could be achieved in a quantum system makes more sense. If a quantum computer is to perform an extensive computation, since it must be isolated from the environment during the entire calculation, avoiding any heat dissipation is essential.
However, a quantum computer's memory is zeroed before starting a computation, and when the right result is found, it stops; these operations do consume energy, but their number is limited, and they do not occur during computations.
This may be oversimplified, but here is a set of possible instructions for a quantum computer:
Incidentally, these operations have some resemblance to the operations allowed when one is inverting a matrix by pivoting. And they can be generalized to allow more elaborate invertible operations, thus making programs easier to write:
The program counter can operate invertibly if it is set up as a ring counter, but that may not be needed; incrementing a counter normally is also invertible.
The main distinguishing feature of this kind of computer is that some common operations will use up memory space initialized to zero. Sometimes, after copying the result to some blank memory, a computation can be run in reverse to clean up the mess made by intermediate results.
Another important fact about a quantum computer is that since it is started, and maintained externally in a superposition of equally probable states, the one "right" state, where the computation has started out trying the right possible key, and found it to be correct, even if it executes an instruction that tells it to signal the outside world and thereby break up the computer's isolation, that doesn't guarantee that anything will happen.
Thus, the program used has to be changed, so that if the wrong key is tried, the program continues by trying the next key.
The good news is that since a quantum system does behave as if it is in all of its superposed states, it doesn't just choose one of them and stay in that state. So the "right" state has more than one opportunity to be randomly selected. As the other states gradually find the right key, and decide in turn to do something noticeable, we have that the number of states that have the right answer grows proportionally to the time, and the number of chances each state has to be noticed if it is right also grows proportionally to the time.
The probability of us recieving the answer is a fraction of the total number of states, which equals the total number of possible keys. Hence, instead of giving us the answer in the time taken to try one key, as would have been hoped for from the initial oversimplified picture of a quantum computer, or in the time taken to try all (or half, on average) the keys, like a conventional computer, the time required (which can vary randomly) is actually proportional to the square root of the number of keys. A recent paper has been published with a proof a quantum computer cannot do better than this on problems of searching.