Prepare $|\xi\rangle=Q^{-1/2}\sum_b|b\rangle$ in the second register by part (ii), while preserving the first register $|a\rangle$. Applying the diagonal unitary $V$ from part (iii) gives
$$
V|a\rangle|\xi\rangle
=|a\rangle\frac1{\sqrt Q}\sum_{b=0}^{Q-1}\omega^{ab}|b\rangle
=\boxed{|a\rangle\operatorname{QFT}_Q|a\rangle}.
$$
The preparation can be made coherent using <amplitude amplification> in place of postselection when this map is needed as a subroutine.

Solution

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

 Solution

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