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

The hidden subgroup problem is to recover a subgroup $K\le G$, usually by giving generators of a group, from an oracle machine providing $f:G\to Y$ with the promiseThus $f$ is constant on each left coset and distinguishes different left cosets. The input includes an effective representation of elements of the group and access to the group operations; the desired efficiency is measured against the number of bits describing an element, rather than necessarily against $|G|$.

Write the finite abelian group additively. Its group shift operator isThese unitary operators form the regular representation and commute. The representation-theoretic facts we use are that every irreducible representation of a finite abelian group is one-dimensional, there are $|G|$ such characters of a representation, and their character orthogonality gives an orthonormal basis of functions on $G$. Each linear character here is a group homomorphism $\chi :G\to U(1)$, with $|\chi (g)|=1$.

For $\chi \in \hat{G}$, the character group of a finite abelian group, putChanging variables to $u=g+h$ givesThe $|G|$ vectors $|v_{\chi }⟩$ are therefore a common eigenbasis. Using $\chi (g)$ instead of its complex conjugate in their definition reverses every eigenphase; this is merely the quantum Fourier transform sign convention.

Measure the coset state in the common eigenbasis $\{|v_{\chi }⟩\}$ of the group shift operators. Its overlap isThe character-sum cancellation lemma makes this sum $|K|$ when $\chi$ is trivial on $K$, and zero otherwise. Hence, with $K^{\perp }$ the annihilator of a subgroup of a finite abelian group,Since $|K^{\perp }|=|G|/|K|$, this is the uniform distribution on a finite set $K^{\perp }$. The factor $\chi (g_0)$ has modulus one, so the distribution is independent of $g_0$. This is abelian hidden-subgroup Fourier sampling.

The distinct values in one period imply that $r$ is the least positive period, $r\mid N$, and $|Y|=r$. Write $x=j+tr$, where $0\le j<r$ and $0\le t<N/r$. Use the positive-exponent quantum Fourier transform convention already used in the concept article. The amplitude of first-register value $y$ isBy the root-of-unity filter, the inner sum vanishes unless $y=mN/r$. DefineThe distinct $f(j)$ give an orthonormal basis of the second register, and the transformed state isReindexing $j+l$ modulo $r$ showsConsequently measurement in this common eigenbasis returns each $m$ with probability $1/r$; the corresponding eigenvalue of $U_1$ is a uniformly sampled $r$th root of unity. A single measured phase $-m/r$ reveals the denominator $r/\gcd (m,r)$, which need not be $r$. Repeated samples permit exact period recovery from a Fourier sample, for example by taking the least common multiple of their reduced denominators. The simultaneous eigenspaces and their probabilities depend on $r$, not on the particular labels $f(j)$.