= Solution
Use $|1\rangle$ as the target register for <quantum phase estimation> of $U_a$. By part (iii), it is the equal superposition $r^{-1/2}\sum_s|\psi_s\rangle$ of eigenvectors with phases $s/r$. Controlled modular multiplications implement the required powers $U_a^{2^j}$ efficiently. The phase-estimation circuit produces
$$
\frac1{\sqrt r}\sum_{s=0}^{r-1}
|\widetilde{s/r}\rangle|\psi_s\rangle,
$$
where the first register contains an $m$-bit approximation with constant success probability. A <quantum measurement in the computational basis> therefore outputs an approximation to $s/r$, with $s$ uniformly distributed over $\{0,\ldots,r-1\}$.
Back to article page
