Heralded exact quantum period finding when the period divides the register size

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$.