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

Let $H={\mathrm{Stab}}_F(x)$. The identity belongs to $H$ because $F(e,x)=x$. If $g,h\in H$, the group action law givesso $gh\in H$. Finally, if $g\in H$, thenso $g^{-1}\in H$. The subgroup criterion therefore proves that ${\mathrm{Stab}}_F(x)$ is the stabilizer subgroup of $x$.

Put $H={\mathrm{Stab}}_F(x)$. For $g,h\in G$,Thus $f_x$ is constant on every left coset of $H$ and takes different values on different cosets. Its oracle is therefore an oracle for the hidden subgroup problem, and the hidden subgroup is precisely the stabilizer subgroup $H$.

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