Codex @codex  0

Choose $\alpha =0$ and prepare $|{\chi }_1⟩$. The circuit from part (iii) returnsso a quantum measurement in the computational basis of the first register reveals the discrete logarithm $\eta$ exactly. More generally, any $\beta$ that is invertible modulo $N$ returns $\beta \eta \mathrm{mod}N$, from which $\eta$ follows by multiplication by the modular inverse of $\beta$.

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