The Quantum States of Shor's Algorithm

Shor's algorithm uses two registers. We describe the state of the algorithm at any time by associating a complex number called an amplitude to each possible pair of values the two registers might take. (This is analagous to describing the state of a probabilistic algorithm by associating a real number - the probability - with each possible deterministic state.) The amplitude is the "arrow" (as Feynman calls it in his book QED) associated with the corresponding event.

The first rule regarding amplitudes is that, if the system were to be fully observed at any time, then the probability of finding a particular outcome (i.e., a particular pair of register values) would be equal to the squared length of its current amplitude. The second rule ("adding arrows") is that, if there are several alternative ways for an outcome (again, a pair of register values) to arise, then the amplitude for the event is the sum of the amplitudes of the alternatives. Since amplitudes can cancel, this is the mechanism for destructive interference, which is in turn what allows the Fourier transform to be computed.

1. In the initial state, each pair of values (A, X^A mod N), where A ranges from 0 to Q-1, has amplitude 1/sqrt(Q), where Q is the smallest power of two larger than N².

   The quantum computation that achieves this is analagous to a probabilistic computation that chooses a random A for the first register and then computes the corresponding value X^A mod N for the second register.

2. Observe the second register. (We differ here from Shor for pedagogical purposes.) This partially "collapses" the state of the computation so that the only values A of the first register associated with non-zero amplitudes are those such that X^A mod N agree with the observed value. That is, the sequence of amplitudes as A ranges from 0 to Q-1 is non-zero only on every Rth value.

   For instance, if R was 4, the resulting sequence might be 0,S,0,0,0,S,0,0,0,S,0,0,0,S,0,0,..., where the sequence is Q numbers long and S is approximately 1/sqrt(Q/R).

3. Perform a discrete Fourier transform on the aforementioned sequence of amplitudes. This is the key step. The Fourier transform of such a sequence with period R and Q elements is essentially a similar sequence, but with period Q/R and starting at the first element. That is, the non-zero amplitudes are now associated with those values of the first register that are (very close to) multiples of Q/R. See here for elaboration.

4. Observe the first register. We will see a value C that is (very close to) one of the first R multiples of Q/R and each such multiple will occur with roughly equal probability. Compute C/Q, which will be very close to one of the first R multiples of 1/R, say D/R. Next, compute the ratio D/R (using the fact that among all fractions expressible as ratios with denominator N or less, it is the one closest to C/Q).

   At this point, we know the ratio D/R - we don't yet know D or R. However, we can easily compute relatively prime A and B such that A/B = D/R. If D is relatively prime to R, then B will be R. Since each non-negative integer smaller than R is roughly equally likely to be D, and at least a fraction proportional to 1/log(log(R)) of these values are relatively prime to R (for any R), we find R with probability proportional to at least 1/log(log(R)).