Quantum order finding

Quantum order finding Fourier-transforms a superposition of arguments having the same modular-exponentiation value, producing peaks near multiples of the reciprocal period.

In quantum order finding, a phase $s/r$ produces amplitude $Q^{-1}{\sum }_{x=0}^{Q-1}{e}^{2\pi ix(s/r-j/Q)}$ after an inverse quantum Fourier transform. Its nearest grid point has probability at least $4/{\pi }^2$, by bounding the sine ratio of this finite geometric Fourier amplitude. The initial modular orbit state is an equal-weight superposition of the $r$ phase eigenstates, so the phase label is uniform.

Quantum modular exponentiation is the reversible computation that mapsIt can be implemented in polynomial time in the bit lengths of $x$ and $N$ by repeated squaring and controlled modular multiplication.

The Fourier amplitude of equally spaced basis states is a finite geometric sum with peaks where the Fourier phase increment is nearly one.

For $A$ terms with phase ratio $q$, the amplitude factor is $(1-q^A)/(1-q)$, with limiting value $A$ when $q=1$.

If a measured ratio approximates a reduced $k/r$ within $1/(2r^2)$, continued-fraction convergents recover the candidate denominator $r$.

Two distinct reduced fractions with denominators below $N$ differ by more than $1/N^2$, so an interval of radius $1/(2N^2)$ contains at most one.