 Solution

Use $|1⟩$ 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⟩$ of eigenvectors with phases $s/r$. Controlled modular multiplications implement the required powers $U_a^{2^j}$ efficiently. The phase-estimation circuit produceswhere 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,\dots ,r-1\}$.