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

Since $\gcd (x,N)=1$, multiplication by $x$ modulo $N$ is a bijection of ${\mathbb{Z}}_N$, with inverse multiplication by the modular inverse $x^{-1}$. Hence $U_x$ permutes the standard orthonormal basis. It preserves all inner products and satisfiesso $U_x$ is a unitary operator.

The multiplicative order $r$ makes the states $|a^k\mathrm{mod}N⟩$, $0\le k<r$, distinct and cyclic under $U_a$. ThereforeThus each $|{\psi }_s⟩$ is an eigenvector withThese are the Fourier eigenvectors of the cyclic modular-multiplication orbit.

Summing the eigenvectors and reversing the finite sums givesThe root-of-unity filter makes the inner sum equal to $r$ for $k=0$ and zero otherwise. Since $a^0=1$,

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