Quantum period finding

For a function of period $r$ dividing $N$, prepare a uniform superposition of inputs, evaluate the function into a second register, and measure that register. The first register becomes a periodic coset state. Applying the quantum Fourier transform and measuring gives

For the exact sample $c=sN/r$, reducingrecovers denominator $r/\gcd (s,r)$. Thus one sample reveals the full period exactly when $s$ is coprime to $r$; otherwise it reveals only a proper divisor and the algorithm must obtain more information.

Suppose a function has least period $r\mid N$ and distinct values on distinct period cosets. Two independent Fourier samples have the form $c_j=s_{j}N/r$ with uniform $s_j\in {\mathbb{Z}}_r$. The displayed candidate is $r/\gcd (r,s_1,s_2)$, so exact recovery occurs when no prime divisor of $r$ divides both residues. The Chinese remainder theorem gives probability ${\prod }_{\ell \mid r}(1-{\ell }^{-2})\ge 1/\zeta (2)=6/{\pi }^2$, using the Euler product. Unlike a single-sample coprimality probability, this bound is uniformly greater than one half. A candidate-period test makes successful recovery heralded when such a test is available.

Suppose a function on ${\mathbb{Z}}_N$ has least period $r\mid N$ and is injective on each period. A Fourier sample $c=sN/r$ gives the candidate denominator $q=r/\gcd (s,r)$. If equality of function values can be tested efficiently, then $q$ is the full period exactly when $f(q)=f(0)$, so each successful run is certified. A sample succeeds with probability $\phi (r)/r$, and an inverse-polylogarithmic lower bound for this ratio permits amplification to constant success probability with polynomially many repetitions.

The function $f(x)=3^x\mathrm{mod}10$ on ${\mathbb{Z}}_{12}$ has period four. Measuring function value $3$ in its uniform input-output state leaves $(|1⟩+|5⟩+|9⟩)/\sqrt{3}$. The quantum Fourier transform modulo twelve then returns each of $0,3,6,9$ with probability $1/4$.