= Solution
Measure the second register of $|f\rangle$. If the result is $f(x_0)$, injectivity within one period collapses the first register to the <periodic coset state>
$$
|\alpha\rangle=\frac1{\sqrt A}\sum_{k=0}^{A-1}|x_0+kr\rangle,
\qquad A=\frac Nr.
$$
Apply $\operatorname{QFT}_N$ and measure the first register. By the stated transform identity, the outcome is
$$
c=lA=\frac{lN}{r}
$$
for a uniformly random $l\in\{0,\ldots,r-1\}$.
Reduce the rational number
$$
\frac cN=\frac lr
$$
to lowest terms and call its denominator $q$. The <exact period recovery from a Fourier sample> gives
$$
q=\frac r{\gcd(l,r)}.
$$
Thus $q=r$ exactly when $l$ is coprime to $r$.
The success can be certified with two classical function evaluations. Compute $f(0)$ and $f(q)$. Since $q\mid r$ and $0\leq q\leq r$, periodicity and injectivity within a period imply
$$
f(q)=f(0)\iff q=r.
$$
Report $q$ only when this equality holds; otherwise report failure. The success probability is
$$
\boxed{\frac{\varphi(r)}r=\Omega\left(\frac1{\log\log N}\right),}
$$
using the standard lower bound for the <Euler totient function>. This is <heralded exact quantum period finding when the period divides the register size>.
Back to article page
