= Solution
Use the positive-exponent <quantum Fourier transform> convention $F_N|x\rangle=N^{-1/2}\sum_t e^{2\pi ixt/N}|t\rangle$. The <period of a function> here is the least positive translation leaving the function unchanged on the <cyclic group> $\mathbb Z_N$. The <injective> promise means $f(x)=f(x')$ exactly when $x\equiv x'\pmod r$. In particular $r\mid N$: the subgroup of period translations is generated by $r$, and wrapping the argument by $N$ preserves its value. This is exact <quantum period finding> on a <finite cyclic group>, rather than the truncated, nondividing-period version requiring <continued fractions>.
Prepare a <uniform superposition state> in the first <quantum register> using $F_N|0\rangle$, and perform a <reversible computation> of the function into a second <quantum register>, cleaning its workspace by <uncomputation>:
$$
\frac1{\sqrt N}\sum_{x=0}^{N-1}|x\rangle|0\rangle\longmapsto\frac1{\sqrt N}\sum_{x=0}^{N-1}|x\rangle|f(x)\rangle.
$$
A <quantum measurement in the computational basis> of the second <quantum register> leaves a <periodic coset state> in the first:
$$
|C_a\rangle=\sqrt{\frac rN}\sum_{j=0}^{N/r-1}|a+jr\rangle,\qquad 0\leq a<r.
$$
For the <quantum Fourier transform> of this <periodic coset state>, the <finite geometric series> vanishes unless the measured label is $t=mN/r$. On those labels its normalized amplitude is $r^{-1/2}e^{2\pi iam/r}$. Thus $m$ has the <uniform distribution on a finite set> on $\{0,\ldots,r-1\}$, irrespective of $a$.
Compute the <greatest common divisor> by the <Euclidean algorithm>, and set $q=N/\gcd(t,N)$, with $\gcd(0,N)=N$. Since $t=mN/r$,
$$
q=\frac r{\gcd(m,r)}.
$$
The <exact period recovery from a Fourier sample> is therefore certified by testing $f(q\bmod N)=f(0)$. Every candidate $q$ divides $r$ and lies between $1$ and $r$, so the <injective> promise makes that equality equivalent to $q=r$. This includes $r=N$, where the test uses input $0$, and $r=1$, which always succeeds. The test does not assert that an arbitrary equality of function values certifies an arbitrary period; the Fourier-derived divisor restriction is essential.
The concise result is
$$
\boxed{q=\frac N{\gcd(t,N)},\quad \text{accept iff }f(q\bmod N)=f(0),\quad P_{\mathrm{accept}}=\frac{\varphi(r)}r.}
$$
Here $\varphi$ is the <Euler totient function>, with $\varphi(1)=1$. The <totient lower bound from the Mertens product> gives $\varphi(r)/r=\Omega(1/\max\{1,\log\log N\})$ for $r\leq N$. Each trial uses <polynomial time> <quantum Fourier transforms>, function evaluations and <Euclidean algorithm> arithmetic in $\log N$. Repeating $O(\max\{1,\log\log N\})$ independent trials gives constant success probability; the herald accepts only correct answers.
\b[The printed asymptotic bound has the wrong direction for this argument.] In <Big O notation>, the stated upper bound on the number of <coprime integers> supplies no success lower bound and is itself false uniformly: for prime $N$, $\varphi(N)=N-1$, not $O(N/\log\log N)$. Likewise the single-trial success need not be $O(1/\log\log N)$, since it tends to one for $r=N$ prime. The meaningful corrected guarantee is the lower bound above. If an upper-bounded success rate is literally required, one may deliberately retain an accepted result with an independent probability proportional to $1/\max\{1,\log\log N\}$; this discards useful successes and is unnecessary for efficient recovery.
Back to article page
