Past exam of the mathematics course of the University of Cambridge / 2019 / ii / Paper 4 / 10D / b / Solution

Choose a power of two $M$ withSince the multiplicative order $r$ is less than $N$, this guarantees $M\ge r^2$. Prepare two quantum registers in the stateand use quantum modular exponentiation to obtain

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 cosetwhere $K$ is the largest integer for which $x_0+(K-1)r<M$.

Apply the quantum Fourier transform ${\mathrm{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,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\equiv 1(\mathrm{mod}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.