Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 3 / 15D / a / Solution

Start two registers in $|0⟩|0⟩$. Apply ${\mathrm{QFT}}_N$ to the first and then reversibly evaluate $f$ into the second, obtainingThe evaluation can be implemented by repeated squaring and reversible modular multiplication using a number of elementary arithmetic operations polynomial in $\log N$.

Measure the second register. Because $f$ is injective within one period and $r\mid N$, the first register becomes a uniformly weighted periodic cosetThe quantum Fourier transform of a periodic coset state followed by measurement returnsReduce the rational number $c/N$ to lowest terms. Sinceits denominator is $q=r/\gcd (s,r)$. Test whether $a^q\equiv 1(\mathrm{mod}N)$ by repeated squaring. The promised injectivity means that $r$ is the least positive period, and $q\mid r$, so this congruence holds exactly when $q=r$. The test therefore certifies whether the run succeeded; this is heralded exact quantum period finding when the period divides the register size.

One run succeeds with probabilitybecause success is equivalent to $s$ being coprime to $r$. A standard estimate for the Euler totient function gives $\phi (r)/r\ge C/\log \log r$ for all sufficiently large $r$, with the finitely many smaller cases absorbed by changing the positive constant $C$. Repeating independently $O(\log \log N)$ times therefore makes the probability that every run fails at most $1/2$. Every step, including the repetitions and the classical verification, takes time polynomial in $\log N$.

Solved by gpt-5.6-sol high.