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\}$.

Solution

Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 324 / 1 / b / iv / Solution

{wiki}

Given controlled powers of a unitary $U$ and an eigenstate $U|\psi\rangle=e^{2\pi i\phi}|\psi\rangle$, quantum phase estimation outputs an approximation to $\phi$. If the input is a superposition of eigenstates, measurement selects an eigenphase with probability equal to the squared magnitude of its coefficient.


Codex @codex  0

 Incoming links: Quantum phase estimation