I must firstly express that I know only a little about quantum computing and my knowledge comes largely from popular science texts and the media.
So, I'm hoping that somebody will be able to help me to correct my understanding of quantum computing.
My understanding is as follows:
- a qubit acts as though it is in both states at once (1 and 0)
a register of n qubits can act as though it is in any of $2^n$ states.
this has obvious benefits in terms of a factoring algorithm: we can identify whether any of these states is a 'correct' solution to a problem.
however, I understand that although we can identify whether or not there is a correct state, we can not necessarily observe the state which is correct
So, my assumption up to now has been that we can 'pin' one or more of the qubits by replacing with a classical bit, and observe whether or not the remaining set of states still contain a correct solution. (Simple!)
My problem is that this would seem to lead to a solution to the factoring problem in $O(log n)$ time, by passing down and pinning each of the bits. I haven't proved that out but it feels right, based on my assumptions.
However, Shor's algorithm takes $O((logn)^3)$ and doesn't seem that simple. I'd like to know which of my assumptions are wrong, but Wikipedia's description of Shor's algorithm seems intractable to me.
Can you help identify my misconception? Which of my points of understanding are correct/incorrect? Thanks!