The shift $S|x\rangle=|x-1\bmod Q\rangle$ acts on a Fourier state as
$$
\begin{aligned}
S\operatorname{QFT}_Q|a\rangle
&=\frac1{\sqrt Q}\sum_x\omega^{ax}|x-1\rangle\\
&=\omega^a\operatorname{QFT}_Q|a\rangle.
\end{aligned}
$$
Thus $\operatorname{QFT}_Q|a\rangle$ 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:
$$
\boxed{
|0^m\rangle\operatorname{QFT}_Q|a\rangle
\longmapsto
|a\rangle\operatorname{QFT}_Q|a\rangle}.
$$

Solution

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

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2025/iii/paper-324/3/b/solution