The most repeated sentence about quantum computing is also the most misleading: "it tries all the possibilities at the same time". Let me give a more careful picture.
A register of n qubits is described by 2^n complex amplitudes. That is the "all possibilities" part: the state is a superposition over every bit string. But when you measure, you get just one n-bit string, chosen at random with probability equal to the squared magnitude of its amplitude. You do not get to read the whole list of amplitudes.
So a quantum algorithm is not "compute everything, then pick the best". It is a trick to arrange the amplitudes so that the wrong answers cancel out (destructive interference) and the right ones add up, so that measuring gives the right answer with high probability. That is hard to do, and it works only for problems that have the right structure.
Two consequences:
- There is no general speedup for "try all the candidates". For unstructured search the best you can get is a quadratic improvement, not an exponential one.
- The information you can extract is limited:
nqubits can carry at mostnclassical bits out, however large the state space is.
If a description makes it sound easy, it left out the interference.