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

For each fixed $\alpha$, right multiplication by $x^{-\alpha }$ is a bijection of $G$, whose inverse is right multiplication by $x^{\alpha }$. Therefore $D_x$ permutes the displayed orthonormal basis of the tensor-product space. It is consequently a unitary operator, with

Write $x=g^{\eta }$. Applying $D_x$ and then changing the summation variable from $k$ to $\ell =k-\alpha \eta$ givesHence this state is an eigenvector of $D_x$ with eigenvalue $\boxed{{\omega }^{\alpha \beta \eta }}$.

Using the conventionpart (ii) applies the extra phase ${\omega }^{j\beta \eta }$ to term $j$. The resulting first register is the quantum Fourier transform of $|\alpha +\beta \eta \mathrm{mod}N⟩$. Applying its inverse therefore produces

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