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

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.