Exponetially Quantum

It's really more confusing than you think.
It explained the superpostion of quantum states in classical computer terms of numbers in registers--every qubit added exponentially increases the number of registers the algorithm operates on.
Actually, every qubit only adds a qubit, but the size of the classical registers that would be needed to simulate the quantum register grows exponentially. This is not the same as saying the quantum register is equivalent to the huge classical register that would be needed to simulate it. The huge classical register would actually be much more useful if it could be made.
The calculation runs and ends in a group of results. Only one result of all those calulations will be right.
You are referring to a peculiarity of the Shor factoring algorithm, which is still the only useful truly quantum algorithm known. As I said, ideally a quantum algorithm would give only a single answer, i.e. at the end of the calculation the quantum state of the register would be one particular answer with unit probability and all other answers would have zero probability. However, the Shor algorithm does not do this; there is some probability of a wrong answer, and you have to run the calculation a few times to see what answers you get and then check them to see which one is right. This is not necessarily a universal characteristic of all quantum algorithms, but it's hard to say because so far the Shor algorithm is just about all we have.
Any problem that grows exponentially harder to solve as you add terms, non-polynomial problems, are tractable to a quantum computer because you simply tack on another qubit for each new term added and then run the calculation in polynomial time.
This was an early hope for QC but it is now known not to be true. Actually, there is only one algorithm known that can take advantage of the power of QC to solve what is believed to be an exponentially hard problem, and other exponentially hard problems are known not to be soluble in linear time by QC.
There is another very important exponentially hard problem which is known to be soluble by QC, although little work has been done on algorithms for it. That is the simulation of quantum systems themselves. In the long run, this may be the most important application of quantum computing, if it ever becomes practical.
--BY MarkGubrud (gubrud@squid.umd.edu)