Abelian vs Non-Abelian HSP

The Hidden Subgroup Problem (HSP) is the single framework that unifies Simon's algorithm, Shor's factoring algorithm, and the discrete logarithm algorithm. All of those algorithms exploit the same structural idea: use quantum Fourier sampling to distinguish a hidden subgroup $H$ of a group $G$ from the whole group. Whether a quantum computer can solve a given HSP instance efficiently depends critically on one property of the group: whether it is abelian (commutative) or non-abelian (non-commutative).

Recall: what is the HSP?

Given a group $G$ and a function $f : G \to S$ that is constant and distinct on left cosets of some hidden subgroup $H \leq G$ , the goal is to identify $H$ . In equations:

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

The quantum strategy is always the same three-step template:

Prepare a uniform superposition over all group elements: $\frac{1}{\sqrt{|G|}} \sum_{g \in G} |g\rangle|0\rangle$ .
Compute $f$ in superposition: $\frac{1}{\sqrt{|G|}} \sum_{g \in G} |g\rangle|f(g)\rangle$ .
Measure the second register, collapsing the first into a uniform superposition over one coset of $H$ , then apply a Fourier transform on $G$ and sample.

The difficulty lies entirely in step 3: extracting information about $H$ from the coset state.

The abelian case: fully solved

When $G$ is abelian — meaning $g \cdot g' = g' \cdot g$ for all $g, g' \in G$ — the quantum Fourier transform over $G$ has a beautiful property: its output distribution concentrates on the dual subgroup $H^{\perp}$ , the set of characters $\chi$ of $G$ that are trivial on $H$ . Measuring the Fourier register yields a uniformly random element of $H^{\perp}$ , and after $O(\log |G|)$ samples the subgroup $H$ can be reconstructed classically with high probability.

For any finite abelian group $G$ the abelian HSP has an efficient quantum algorithm running in $\text{poly}(\log |G|)$ time. This is one of the landmark results of quantum complexity theory.

The non-abelian case: mostly open

When the group $G$ is non-abelian, left cosets and right cosets of $H$ need not coincide, and the Fourier transform on $G$ becomes a transform over non-commutative representations. The standard coset sampling strategy yields the weak Fourier sampling distribution, which is known to be information-theoretically insufficient to identify $H$ for many non-abelian groups.

The canonical hard case is the symmetric group $S_n$ . The Graph Isomorphism problem (GI) reduces to the HSP over $S_n$ via the hidden subgroup being the automorphism group of one of two graphs. Despite sustained effort, no polynomial-time quantum algorithm is known for the $S_n$ -HSP, and information-theoretic lower bounds show that weak Fourier sampling alone cannot solve it. Strong Fourier sampling — measuring in a basis adapted to the irreducible representations of $G$ — might in principle carry more information, but implementing it efficiently remains an open research problem.

The table below summarises the landscape:

| Group $G$ | HSP instance | Status | |---|---|---| | $\mathbb{Z}_2^n$ | Simon's problem | Efficient quantum algorithm (Simon 1994) | | $\mathbb{Z}_N$ | Shor's factoring / discrete log | Efficient quantum algorithm (Shor 1994) | | Any finite abelian group | General abelian HSP | Efficient quantum algorithm (Kitaev 1995) | | $S_n$ (symmetric group) | Graph Isomorphism | Open — weak Fourier sampling insufficient | | Dihedral group $D_N$ | Unique Shortest Vector (lattice) | $\exp(O(\sqrt{n}))$ quantum, open for poly |

Why commutativity matters so deeply

In the abelian case the characters of $G$ — the one-dimensional unitary representations $\chi : G \to \mathbb{C}^{\times}$ — form a group that is isomorphic to $G$ itself. This lets the quantum Fourier transform diagonalise every element of $G$ simultaneously, and coset states become eigenstates of the Fourier transform in a very clean sense.

In the non-abelian case irreducible representations are multi-dimensional. A coset state $|gH\rangle$ does not project neatly onto a single representation; information about $H$ is spread across the full matrix of the representation, not just its eigenvalue. Recovering that information requires tomography on a high-dimensional object — and doing so in polynomial time is believed to be hard.

Implications for quantum advantage

The abelian HSP boundary is the precise frontier where we know quantum computers have a super-polynomial advantage over classical ones (under standard complexity assumptions). It encompasses the problems that motivated much of early quantum computing research.

The non-abelian HSP, by contrast, represents a zone where quantum algorithms might still outperform classical ones, but where the evidence is far thinner. Graph Isomorphism is not known to be NP-hard, so even a classical polynomial-time algorithm remains possible. The separation between abelian and non-abelian difficulty is therefore both a mathematical fact about group theory and a practical guide for researchers seeking new quantum speedups: look for structure that maps onto an abelian group, or develop genuinely new ideas beyond Fourier sampling for the non-abelian regime.