The Hidden Subgroup Problem

Stand back from the individual quantum algorithms for a moment and a startling pattern comes into focus: nearly every exponential quantum speedup we know is secretly the same problem in disguise. Deutsch–Jozsa, Bernstein–Vazirani, Simon's algorithm, order-finding, Shor's factoring, discrete logarithm — peel back the story and each one is asking you to uncover a hidden subgroup of some group G. This single template is the Hidden Subgroup Problem (HSP), and it is the closest thing we have to a grand unified theory of quantum advantage. Learn it once and you understand the engine behind them all — and, just as importantly, you learn exactly where that engine stalls.

The setup: a function that is blind to a subgroup

Fix a group G. Hidden inside it is a subgroup H \le G that you cannot see. What you are given is an oracle for a function f : G \to X (into some set of labels X) with one special property: f is constant on each coset of H and distinct across different cosets. In symbols,

f(g) = f(g') \iff gH = g'H.

Picture H tiling G into parallel cosets; f paints every element of one coset the same colour, and paints different cosets different colours. It hides H precisely because it never distinguishes two elements that differ by something in H. Your goal is to recover H — typically a small set of generators — using as few oracle queries as possible.

The quantum recipe (one shape fits every instance)

Remarkably, the same four-move circuit attacks any HSP; only the group G (and hence the meaning of "the Fourier transform over G") changes:

  1. Superpose. Build the uniform superposition over the whole group, \frac{1}{\sqrt{|G|}}\sum_{g\in G}|g\rangle\,|0\rangle.
  2. Query. One call to f entangles value with input: \;\frac{1}{\sqrt{|G|}}\sum_{g}|g\rangle\,|f(g)\rangle.
  3. Collapse to a coset. Measure the value register. You read some colour f(c), and the input register collapses onto exactly the coset painted that colour — a uniform superposition over a single coset \frac{1}{\sqrt{|H|}}\sum_{h\in H}|c+h\rangle. Which coset (the offset c) is random, and that randomness is the whole difficulty: you cannot read c off directly.
  4. Fourier & sample. Apply the QFT over G and measure. The Fourier transform is blind to the random offset c (it only reshuffles phases), so what you sample is a character constraint on H itself. Repeat a handful of times and the constraints pin H down.

That step 4 is the magic word. The Fourier transform converts "a coset sitting at an unknown location" into "a clean, location-independent fingerprint of the subgroup." Everything hard has been laundered away by the QFT.

The circuit, at a glance

Here is the whole recipe as one circuit. The top wire carries the register over G; the bottom wire is the value register. Step through it: superpose, query, measure the value register to fall onto a coset, then the \text{QFT}_G and a sample.

Worked example 1: Simon's algorithm is HSP over (\mathbb{Z}_2)^n

In Simon's problem you are promised a function f:\{0,1\}^n \to \{0,1\}^n with a hidden string s such that f(x)=f(y) exactly when y = x \oplus s. Cast it as an HSP by taking the group to be the bit-strings under XOR,

G = (\mathbb{Z}_2)^n \quad(\text{addition} = \text{bitwise XOR}), \qquad H = \{0,\, s\}.

Check the promise against the HSP condition: H=\{0,s\} is a subgroup (it's closed — s\oplus s = 0), its cosets are exactly the pairs \{x,\,x\oplus s\}, and Simon's promise says f is constant on each such pair and distinct across them. That is precisely "f(x)=f(y)\iff xH=yH." So Simon's algorithm is nothing but the generic recipe with G=(\mathbb{Z}_2)^n: the superposition is H^{\otimes n}, and the "QFT over (\mathbb{Z}_2)^n" is again just H^{\otimes n}. Each run samples a string y orthogonal to s (y\cdot s = 0) — a linear constraint on H — and about n-1 such constraints solve for s. The same story tells you Deutsch–Jozsa and Bernstein–Vazirani are HSP over (\mathbb{Z}_2)^n too.

Worked example 2: order-finding (and Shor) is HSP over \mathbb{Z}

To factor N, Shor's algorithm reduces to order-finding: given a coprime to N, find the least r>0 with a^{r}\equiv 1 \pmod N. Define f:\mathbb{Z}\to\mathbb{Z}_N by

f(x) = a^{x} \bmod N.

Then f(x)=f(y) iff a^{x-y}\equiv 1 iff r \mid (x-y) iff x-y \in r\mathbb{Z}. So f is constant exactly on the cosets of

G = \mathbb{Z}, \qquad H = r\mathbb{Z} = \{\dots,-2r,-r,0,r,2r,\dots\}.

The period of the function is the hidden subgroup. Order-finding is therefore HSP over \mathbb{Z}: the recipe superposes over a large window of integers, queries f, collapses onto a coset c + r\mathbb{Z}, and then the QFT over \mathbb{Z}_N (a finite stand-in for the infinite group) concentrates amplitude near multiples of N/r. Sampling and a little continued-fractions arithmetic recover r, hence a factor of N. Push the group up to \mathbb{Z}_N\times\mathbb{Z}_N and the very same machine solves discrete logarithm — which is why elliptic-curve and Diffie–Hellman cryptography also fall. Order-finding and Shor's algorithm works this out in full.

It is hard to overstate how much of quantum computing collapses into this one picture. The reason Shor's algorithm and Simon's algorithm feel like cousins is that they are cousins: same circuit skeleton, different group. And the reason the whole family works is a single fact from representation theory — for an abelian group, the Fourier transform diagonalises the coset states, so a random coset offset becomes invisible and the subgroup's fingerprint pops out. The abelian HSP is, in this sense, finished: we know how to solve it efficiently, and that single result is the source of essentially every exponential speedup in the textbooks.

The frontier lies just past the abelian border. Solve the HSP over the symmetric group S_n and you would solve graph isomorphism. Solve it over the dihedral group and you would crack certain lattice problems — the hardness assumptions underpinning most post-quantum cryptography. These are among the biggest open questions in the field: not "can a quantum computer do it in principle" but "does the beautiful abelian trick have any non-abelian analogue at all?" So far, decades of effort say: we don't know.

The most common over-claim is "quantum computers solve the hidden subgroup problem." They solve the abelian hidden subgroup problem — when the group G is commutative, the \text{QFT}_G does the job in polynomial time. For a non-abelian group there is no known efficient quantum algorithm in general. The naive recipe still produces a coset state, but the Fourier transform over a non-abelian group no longer hands you clean, measurable constraints on H — the coset offset does not simply wash out.

This is not a footnote; it is exactly why quantum computers are not known to break lattice-based post-quantum cryptography (the dihedral HSP) and not known to solve graph isomorphism (the symmetric-group HSP). If someone tells you a quantum computer will trivially defeat the new post-quantum standards, they are quietly assuming a solution to an open problem. The line between "solved" and "open" in quantum algorithms runs almost precisely along the border between abelian and non-abelian.