Period finding and continued fractions

TL;DRAbstract

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 2n/r, where n is the number of Qbits in the input register, satisfying 2n > N2 > r2. 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 ½r2, 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/2n. 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 r0: r divided by whatever factor it has in common with the random integer j. If several small multiples of r0 fail to be a period of f, one repeats the whole procedure, ge

Chat with Paper

AI Agents for this Paper