= Solution
Choose a power of two $M$ with
$$
N^2\leq M<2N^2.
$$
Since the <multiplicative order> $r$ is less than $N$, this guarantees $M\geq r^2$. Prepare two quantum registers in the state
$$
\frac1{\sqrt M}\sum_{x=0}^{M-1}|x\rangle|0\rangle,
$$
and use <quantum modular exponentiation> to obtain
$$
\frac1{\sqrt M}\sum_{x=0}^{M-1}|x\rangle|\alpha^x\bmod N\rangle.
$$
Measure the second register. The <order as the exact period of modular exponentiation> implies that, conditional on the measured value, the first register is a normalized truncated periodic coset
$$
\frac1{\sqrt K}\sum_{k=0}^{K-1}|x_0+kr\rangle,
$$
where $K$ is the largest integer for which $x_0+(K-1)r<M$.
Apply the <quantum Fourier transform> $\operatorname{QFT}_M$ to the first register and measure it, obtaining $c$. The supplied Fourier-transform theorem states that, with probability of order $1/\log\log r$, $c$ is an integer nearest to $jM/r$ for some $j$ coprime to $r$. On that event,
$$
\left|\frac cM-\frac jr\right|
\leq\frac1{2M}
\leq\frac1{2r^2}.
$$
The supplied continued-fraction theorem, applied through <continued-fraction recovery in quantum order finding>, therefore recovers the reduced fraction $j/r$ from $c/M$. Because $j$ and $r$ are coprime, its denominator is the exact order $r$. The candidate is checked classically by verifying $\alpha^r\equiv1\pmod N$.
The <quantum Fourier transform>, <quantum modular exponentiation>, <continued-fraction algorithm>, and final modular check all take <polynomial time> in $\log N$. Since $r<N$, the successful event has probability of order $1/\log\log N$, as required.
Back to article page
