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

The hidden subgroup problem for a group $G$ is specified by an oracle $f:G\to S$ that hides an unknown subgroup $H\le G$: it is constant on each left coset of $H$ and takes distinct values on distinct cosets. The task is to determine $H$, usually by finding a generating set for it.

A shift-invariant basis is a common eigenbasis of all cyclic shift operators $U(\gamma )$. For the displayed Fourier states, orthonormality follows from the root-of-unity filter:There are $N$ vectors in this orthonormal set in the $N$-dimensional Hilbert space, so they form a basis. Reindexing the finite sum givesThus every $|{\xi }_{\alpha }⟩$ is simultaneously an eigenvector of every shift, with eigenvalue ${\omega }^{\alpha \gamma }$ for $U(\gamma )$.

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