Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 324 / 3

With $\omega =e^{2\pi i/Q}$, the quantum Fourier transform over the additive group ${\mathbb{Z}}_Q$ is

Apply Hadamard gates to $|0^m⟩$ to prepareReversibly compute the efficiently decidable predicate $[x<Q]$ into an ancillary qubit and measure it. The success probability is $Q/2^m>1/2$, and conditioned on success the first register is exactlyRestart after a failed measurement. After $L=\lceil {\log }_2(1/\delta )\rceil$ attempts, the probability that all attempts fail is below $\delta$, so the state is prepared with probability at least $1-\delta$ using a number of gates polynomial in $m$ and $\log (1/\delta )$.

Write $b={\sum }_{j=0}^{m-1}{2}^j{b}_j$. Applying the phase gateto qubit $b_j$ contributes $\exp (2\pi i{2}^j{b}_j/Q)$. The product of these $m$ gates is thereforeSimilarly, for $a={\sum }_j{a}_j{2}^j$ and $b={\sum }_k{b}_k{2}^k$, apply a controlled phase gatebetween every pair $(a_j,b_k)$. The accumulated phase isThe $m^2$ controlled phase gates implement

Prepare $|\xi ⟩=Q^{-1/2}{\sum }_b|b⟩$ in the second register by part (ii), while preserving the first register $|a⟩$. Applying the diagonal unitary $V$ from part (iii) givesThe preparation can be made coherent using amplitude amplification in place of postselection when this map is needed as a subroutine.

The shift $S|x⟩=|x-1\mathrm{mod}Q⟩$ acts on a Fourier state asThus ${\mathrm{QFT}}_Q|a⟩$ is an eigenvector of $S$ with eigenphase $a/Q$. Apply the unitary part of exact quantum phase estimation for $S$ to a zeroed control register and this Fourier state. It writes the eigenphase label coherently:

Start with $(|a⟩+|b⟩)/\sqrt{2}$ and a zeroed second register. Apply the coherent construction from part (a)(iv) to obtainNow run the inverse of the phase-estimation map from part (b) on the two registers. It erases the first label in both branches:Discarding the zeroed register leaves the required quantum Fourier transform of the superposition. The coherent use of a computed label followed by its inverse is an uncomputation.