Past exam of the mathematics course of the University of Cambridge / 2005 / iii / Paper 58 / 2

Put $N=2^t$ and write $U|u⟩=e^{i\varphi }|u⟩$, with $|u⟩$ normalized. The Hadamard gates prepare the control register in $N^{-1/2}{\sum }_{k=0}^{N-1}|k⟩$. Controlled powers of the unitary operator then give quantum phase kickback:Thus the register quantum state is $N^{-1/2}{\sum }_k{e}^{ik\varphi }|k⟩$, while the target remains $|u⟩$. Define the quantum Fourier transform by $F_N|m⟩=N^{-1/2}{\sum }_k{e}^{2\pi ikm/N}|k⟩$. Its inverse givesWhen $\varphi =2\pi n/N$, the inner finite geometric series equals $N$ if $m\equiv n(\mathrm{mod}N)$ and zero otherwise. Therefore exact quantum phase estimation givesThe quantum phase, rather than an unrestricted integer $n$, is recovered modulo $2\pi$.

The printed circuit has no bit-reversal swaps. Its top control uses $U^{2^{t-1}}$, and its measured top wire gives the least significant output bit. Write $n\mathrm{mod}N={\sum }_{j=0}^{t-1}{2}^j{b}_j$. Before the top wire's final Hadamard gate, its relative quantum phase is $2^{t-1}\varphi =\pi n$, so that gate produces $b_0$. The controlled inverse quantum phase gates then subtract its contribution from lower wires. More generally, before the final Hadamard gate on wire $j$, the relative quantum phase isso that wire gives $b_j$ deterministically. For the three-wire drawing, the correct interpretation isEquivalently, its Fourier-inversion circuit is $R{F}_N^{†}$, where $R$ reverses the register bits. Relabeling the measured bits or appending swaps gives the usual integer output. This bit convention matters, for example, when quantum phase $\pi$ produces top-to-bottom bits $001$, representing the label four rather than one.

Write $\varphi =2\pi n/N+ϵ$, with $|ϵ|\le \delta \ll 2\pi /N$. Decode the measured bits as above. The probability amplitude of label $m$ isUsing the finite geometric series,Interpret removable singularities by continuity. In particular, near-grid quantum phase estimation returns the nearby exact label $n\mathrm{mod}N$ with probabilityThis is near one under the stated small-offset assumption, but not exactly one when $ϵ\ne 0$.

There is also a rigorous error bound. Taking the squared modulus of the sum giveswhere $1-\cos x\le x^2/2$ and the elementary sums of $k$ and $k^2$ evaluate the last expression. HenceOn that event the circular quantum phase error is at most $\delta$. For other labels, the exact probabilities areTheir total is $1-P(n)=O(N^2{\delta }^2)$, describing the leakage from the perfect solution. The physical output bit string remains reversed in the printed circuit; this changes its decoding, not these probabilities.

A central application is quantum order finding, which supplies the quantum step in the Shor algorithm for factoring an integer $M$. Choose an integer $a$ coprime to $M$, and let $r$ be its multiplicative order modulo $M$. On valid residue quantum states define the reversible modular-multiplication unitary operator $U_a|x⟩=|ax\mathrm{mod}M⟩$, extending it reversibly to any unused computational basis quantum states.

The orbit $|1⟩,|a⟩,\dots ,|a^{r-1}⟩$ has the orthonormal eigenstatesfor $s=0,\dots ,r-1$. One need not know $r$ to prepare an eigenstate: the easy input $|1⟩=r^{-1/2}{\sum }_s|u_s⟩$ makes quantum phase estimation sample one of these eigenphases. Its control register estimates $s/r$. With $N=2^t$ chosen at least of order $M^2$, the nearest quantum phase label has rational approximation error small enough for continued-fraction recovery in quantum order finding. For instance, $N>2M^2$ gives $|m/N-s/r|<1/(2r^2)$ on the nearest-label event. If $s$ and $r$ are coprime, the recovered denominator is $r$; otherwise one obtains a divisor and can repeat, combine candidates and verify them by modular exponentiation.

When the verified order is even and $a^{r/2}\not\equiv -1(\mathrm{mod}M)$, the greatest common divisorsgive nontrivial factors: their product is divisible by $M$, while neither factor inside the gcd is zero modulo $M$. Unsuccessful choices of $a$ or quantum phase samples are handled by repetition and classical verification. Controlled powers of $U_a$ are implemented by efficient reversible modular arithmetic, rather than by naively applying $U_a$ exponentially many times.

Quantum phase estimation turns modular-multiplication eigenphases into an efficiently usable period, enabling quantum factoring in time polynomial in the bit length of the integer. Factoring is important to public-key cryptography, and this is a major example of a quantum algorithm improving on known classical methods. Another use is extracting energy eigenvalues by applying quantum phase estimation to a controlled time-evolution operator, with care to avoid energy aliasing and to prepare an input having overlap with the desired eigenstate.