= Solution
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}.
$$
Back to article page
