Solution
= Solution
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.