Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 3 / 15D (Quantum Information and Computation)

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$.

Use the conventionChanging the summation variable from $j$ to $j-1$ givesThus the Fourier-basis states are eigenvectors of the cyclic shift, with respective eigenvalues $e^{-2\pi ik/N}$, and the cyclic shift diagonalization by the quantum Fourier transform is

For $N=4$, write $k=2x+y$ with $x,y\in \{0,1\}$. ThensoHence the required quantum circuit applies, from input to output,The first phase gate acts on the most significant qubit $x$ and the second on the least significant qubit $y$.