= Solution
Use the positive-sign <quantum Fourier transform>
$$
F_N|x\rangle=\frac1{\sqrt N}\sum_{j=0}^{N-1}e^{2\pi ijx/N}|j\rangle.
$$
Orthogonality of the finite-group characters makes $F_N$ a <unitary operator>. Here $r$ is the least positive period. The injectivity within one period implies $r\mid N$: write $N=qr+s$, $0\leq s<r$. Periodicity gives $f(s)=f(N)=f(0)$, and injectivity forces $s=0$. Put $L=N/r$.
Start with two available <computational basis> states $|0\rangle|0\rangle$. Apply $F_N$ to the first register and query the <modular-addition quantum oracle>:
$$
|0\rangle|0\rangle\longmapsto\frac1{\sqrt N}\sum_x|x\rangle|0\rangle
\longmapsto\frac1{\sqrt N}\sum_x|x\rangle|f(x)\rangle.
$$
Measure the second register. For some $t\in\{0,\ldots,r-1\}$, the first register becomes the normalized coset state
$$
\frac1{\sqrt L}\sum_{h=0}^{L-1}|t+hr\rangle.
$$
The <quantum Fourier transform of a periodic coset state> is
$$
\frac1{\sqrt r}\sum_{s=0}^{r-1}e^{2\pi ist/r}\left|\frac{sN}{r}\right\rangle.
$$
Indeed, the inner geometric sum vanishes unless the Fourier label is a multiple of $N/r$. Measuring that label gives $j=sN/r$ for a uniformly random $s$. Compute, by the <Euclidean algorithm>,
$$
R=\frac{N}{\gcd(j,N)}=\frac{r}{\gcd(s,r)}.
$$
Thus <exact period recovery from a Fourier sample> succeeds whenever $s$ is <coprime> to $r$, and
$$
\boxed{\Pr(R=r)=\frac{\varphi(r)}r=\Omega\!\left(\frac1{\log\log N}\right)}.
$$
Here $\varphi$ is the <Euler totient function>. The classical number-theory input is the <totient lower bound from the Mertens product>: for sufficiently large $m$, $\varphi(m)/m\geq c/\log\log m$ for an absolute $c>0$, with the finitely many small cases handled separately. For $r=1$ recovery is certain; for $r=2$ its probability is $1/2$. The useful asymptotic probability statement is a lower bound, hence $\Omega$ notation; it can be much larger for particular periods, for example a prime period.
There is one oracle query, two Fourier transforms and two measurements. The final <greatest common divisor> and division use <polynomial time> in $\log N$. This meets the specified primitive-operation model without assuming that an arbitrary-$N$ Fourier gate is free in another gate model. If a constant success probability is wanted, repeat independently $O(\log\log N)$ times and return the <least common multiple> of the candidates: each candidate divides $r$, and one successful sample makes that <least common multiple> exactly $r$.
Back to article page
