Period finding and continued fractions
N. David Mermin · 2007
We illustrate here the mathematics of the final (post-quantum-computational) stage of Shor's period-finding procedure. The final measurement produces (with high probability) an integer y that is within ½ of an integral multiple of 2 n / r , where n is the number of Qbits in the input register, satisfying 2 n > N 2 > r 2 . Deducing the period r of the function f from such an integer y makes use of the theorem that if x is an estimate for the fraction j/r that differs from it by less than ½ r 2 , then j/r will appear as one of the partial sums in the continued-fraction expansion of x . In the case of Shor's period finding algorithm x = y /2 n . If j and r happen to have no factors in common, r is given by the denominator of the partial sum with the largest denominator less than N . Otherwise the continued-fraction expansion of x gives r 0 : r divided by whatever factor it has in common with the random integer j . If several small multiples of r 0 fail to be a period of f , one repeats the whole procedure, getting a different submultiple r 1 of r . There is a good chance that r will be the least common multiple of r 0 and r 1 , or a not terribly large multiple of it. If not, one repeats the whole procedure a few more times until one succeeds in finding a period of f .