The Hidden Subgroup Problem

Several of the most celebrated quantum speedups — Deutsch–Jozsa, Simon's algorithm, and Shor's period-finding — look quite different on the surface. The Hidden Subgroup Problem (HSP) is the single abstract framework that unifies all of them.

Groups and hiding functions

Recall from the previous lesson that a group $(G, \cdot)$ is a set with an associative binary operation, an identity, and inverses. A subgroup $H \leq G$ is a subset closed under the same operation.

The HSP asks: given a black-box function $f : G \to S$ (where $S$ is just some set of labels), find the subgroup $H \leq G$ such that $f$ is constant on every left coset of $H$ and distinct on different cosets.

More precisely:

In other words, $f$ partitions $G$ into left cosets and assigns the same output to all elements within a coset. The subgroup $H$ is "hidden" because you can only probe $f$ by evaluating it on group elements — you cannot inspect its structure directly.

The quantum strategy

The standard quantum approach to the HSP follows three steps.

Step 1 — Uniform superposition over $G$.
Start from $|0\rangle$ and apply a quantum Fourier transform (or Hadamard layer) over $G$ to prepare

Step 2 — Query the oracle.
Apply the unitary $U_f : |g\rangle|0\rangle \mapsto |g\rangle|f(g)\rangle$. After querying and discarding (measuring) the second register the first register collapses to a uniform superposition over a single (random) coset $gH$:

This coset state encodes $H$ but the specific coset representative $g$ is random and unknown.

Step 3 — Fourier sampling.
Apply the quantum Fourier transform over $G$ to the coset state and measure. The resulting classical sample is drawn from the set of irreducible representations of $G$ that contain $H$ in their kernel. Repeating this polynomially many times and running a classical post-processing step recovers $H$.

Why this matters

The power of the HSP framework is that it explains why these algorithms are fast:

| Algorithm | Group $G$ | Hidden subgroup $H$ | |---|---|---| | Deutsch–Jozsa | $\mathbb{Z}_2^n$ | $\{0\}$ or $\mathbb{Z}_2^n$ | | Simon's algorithm | $\mathbb{Z}_2^n$ | $\{0, s\}$ for hidden string $s$ | | Shor's order-finding | $\mathbb{Z}_M$ ($M \geq N^2$, a power of 2) | $r\mathbb{Z}_M = \{0, r, 2r, \ldots\}$ | | Graph isomorphism (open) | $S_n$ (symmetric group) | stabilizer of a labeling |

The abelian cases ($G$ abelian) are solved efficiently by the quantum Fourier transform over $G$. The non-abelian cases — most famously the symmetric group $S_n$, which would yield an efficient graph-isomorphism algorithm — remain open. The weak Fourier sampling approach that works for abelian groups provably fails to distinguish enough coset states in the non-abelian setting (Hallgren et al., 2003; Moore and Russell, 2007, cited in de Wolf).

Complexity

For the abelian HSP over a group of order $N$, the quantum algorithm uses $O(\log N)$ oracle queries and $O(\text{poly}(\log N))$ additional gates, achieving an exponential improvement over the classical $\Omega(\sqrt{N})$ lower bound. This is because classical algorithms must sample many cosets at random before two share an element, a birthday-paradox argument requiring $\Omega(\sqrt{N/|H|})$ queries.

The key insight is that quantum superposition lets the algorithm query all group elements at once in step 1, and interference (via the Fourier transform in step 3) concentrates probability on representations that carry information about $H$.

Summary

The hidden subgroup problem asks for the subgroup $H$ of a group $G$ hidden by a function that is constant on each coset of $H$ and distinct across cosets. The quantum recipe — superpose, query, Fourier sample — solves the abelian case in polynomial time and unifies Deutsch–Jozsa, Simon, and Shor into a single framework. Whether the same approach can crack the non-abelian case is one of the central open questions in quantum algorithms.

Sign in on the full site to ask questions and join the discussion.