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

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.