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

Measure the second register of $|f⟩$. If the result is $f(x_0)$, injectivity within one period collapses the first register to the periodic coset stateApply ${\mathrm{QFT}}_N$ and measure the first register. By the stated transform identity, the outcome isfor a uniformly random $l\in \{0,\dots ,r-1\}$.

Reduce the rational numberto lowest terms and call its denominator $q$. The exact period recovery from a Fourier sample givesThus $q=r$ exactly when $l$ is coprime to $r$.

The success can be certified with two classical function evaluations. Compute $f(0)$ and $f(q)$. Since $q\mid r$ and $0\le q\le r$, periodicity and injectivity within a period implyReport $q$ only when this equality holds; otherwise report failure. The success probability isusing the standard lower bound for the Euler totient function. This is heralded exact quantum period finding when the period divides the register size.