= Solution
Cyclic periodicity on $\mathbb Z_N$ implies that the least positive period $r$ divides $N$: the shifts preserving the <function> form a <subgroup> of the cyclic group. Injectivity within one period says that distinct residue classes modulo $r$ have distinct function values. Write $L=N/r$.
Prepare the <uniform superposition state> by applying the <quantum Fourier transform> to $|0\rangle$, and evaluate $f$ reversibly into a second <quantum register>. This is efficient because the given classical <Boolean circuit> can be converted into a <reversible circuit>, with its workspace cleaned by <uncomputation>. The resulting <quantum state> is
$$
\frac1{\sqrt N}\sum_{x=0}^{N-1}|x\rangle|f(x)\rangle.
$$
Measuring the function <quantum register> leaves a uniform <coset> state $L^{-1/2}\sum_{j=0}^{L-1}|x_0+jr\rangle$ for some $0\le x_0<r$. The amplitude at $c$ after a <quantum Fourier transform> is
$$
\frac{e^{2\pi icx_0/N}}{\sqrt{NL}}\sum_{j=0}^{L-1}e^{2\pi icj/L}.
$$
The <finite geometric series> is zero unless $c$ is a multiple of $L$, and then equals $L$. Thus a <computational-basis measurement> produces a uniform <Fourier sample>
$$
\boxed{c=s\frac Nr,\qquad s\in\{0,\ldots,r-1\}.}
$$
The <exact period recovery from a Fourier sample> computes
$$
\widehat r=\frac N{\gcd(c,N)}=\frac r{\gcd(s,r)}.
$$
A <greatest common divisor> is computable in time polynomial in $\log N$. The candidate is always a divisor of the true period, and equals it precisely when $s$ is coprime to $r$.
For the success flag, compute $f(\widehat r\bmod N)$ and compare with $f(0)$. If $\widehat r<r$, injectivity within the first period makes these unequal. If $\widehat r=r$, periodicity makes them equal, including $r=N$. Hence \b[accept and output $\widehat r$ exactly when this comparison succeeds; otherwise report failure]. This is <heralded exact quantum period finding when the period divides the register size>, with no false acceptance. The case $r=1$ succeeds even on the sample $c=0$.
The exact success <probability> is
$$
\boxed{P_{\rm success}=\frac{\varphi(r)}r,}
$$
where $\varphi$ is the <Euler totient function>. For $r\mid N$, the prime-product formula gives $\varphi(r)/r\ge\varphi(N)/N$. A <Rosser–Schoenfeld totient bound> supplies the needed lower bound $\varphi(N)/N=\Omega(1/\log\log N)$ for large $N$. Every single attempt, including verification, has the assumed polynomial-in-$\log N$ gate cost. Repeating $O(\log\log N)$ times gives constant success <probability> with a certified result whenever one is found.
\b[The printed $O$ in the totient hint should be a lower-bound statement, $\Omega$.] Literally, $\varphi(N)=O(N/\log\log N)$ is false: at primes $N$, $\varphi(N)=N-1$. Likewise the exact single-sample success <probability> need not be $O(1/\log\log N)$; for prime period it tends to one. The useful intended guarantee is the displayed inverse-log-log lower bound, not a universal upper bound. If an algorithm satisfying the literal success upper bound is desired, one can additionally accept an otherwise certified run only when $k=\lceil\log\log N\rceil$ independent fair bits are all zero. This retains a detectable failure flag and polynomial runtime, and has success at most $2^{-k}=O(1/\log\log N)$, but deliberately weakens the useful guarantee. The standard unsuppressed algorithm above gives the stronger intended performance. Small $N$ can be handled directly. Primary evidence for the totient lower bound is Theorem 15, equations (3.41)–(3.42), in https://denisevellachemla.eu/Rosser-Schoenfeld-1962.pdf .
Back to article page
