The Hidden Subgroup Problem
The framework unifying Simon, Shor and their limits.
Deutsch's problem, Simon's algorithm, Shor's factoring and discrete-log algorithms, and Kitaev's abelian stabilizer algorithm are one algorithm: find a subgroup hidden by a function's symmetries, by Fourier sampling. The same framework shows where the exponential speedups stop. Graph isomorphism and lattice problems are hidden-subgroup problems too, over non-abelian groups, and there the method runs into walls nobody has found a way around.
What you’ll learn
- State the hidden subgroup problem and cast Simon's problem, order finding and discrete logarithms as instances.
- Prove that Fourier sampling on a coset state returns a uniformly random element of , and that samples determine .
- Explain weak and strong Fourier sampling over non-abelian groups and the Ettinger–Høyer–Knill query bound.
- Describe the dihedral and symmetric cases (lattices, graph isomorphism), Kuperberg's subexponential algorithm, and the known obstructions.
One problem behind many algorithms
| Problem | Group | Hidden subgroup | Quantum status |
|---|---|---|---|
| Deutsch's problem | (constant ) or (balanced) | one query | |
| Simon's problem | polynomial time | ||
| Order finding, factoring | (in practice ) | polynomial time (Shor) | |
| Discrete log | , | polynomial time (Shor) | |
| Pell's equation | , the regulator | polynomial time (Hallgren 2002) | |
| Graph isomorphism | open; strong lower bounds for coset-state methods | ||
| Unique-SVP (lattices) | dihedral | a reflection subgroup | subexponential (Kuperberg 2005) |
Fourier sampling solves the abelian case
The standard method has three moves. Query on a uniform superposition to get . Discard (or measure) the second register: the first is left in a uniformly random coset state , equivalently in the mixed state . Then Fourier transform over and measure. For abelian (written additively) the analysis is a few lines.
Linearity, and .
Restricted to , a character is a character of , and it sums to zero over unless it is trivial there.
The coset representative contributes only phases: the outcome is uniform on , which has elements.
is recovered from generators of by solving linear equations: mod 2 for Simon, via the Smith normal form in general.
and . How many distinct outcomes can Fourier sampling return?
Show the answer
8
: the multiples of 4. Each appears with probability .
Non-abelian groups: what breaks
For non-abelian the Fourier basis is labeled by irreducible representations (of dimension , with ) and matrix indices: . Efficient QFT circuits exist for many groups, including the symmetric group (Beals 1997). After transforming a coset state you may measure only the irrep label (weak Fourier sampling) or also the row and column in a basis of your choice (strong Fourier sampling).
Weak Fourier sampling suffices when is normal (Hallgren, Russell & Ta-Shma 2000), but it cannot distinguish from a conjugate : the label distribution depends on only through characters, which are class functions. Beyond normal subgroups, the story splits by group.
| Group | Why it matters | What is known |
|---|---|---|
| Dihedral | Regev (2004): solving the dihedral coset problem with suitable error tolerance would give a quantum algorithm for poly()-unique-SVP, a lattice problem | Kuperberg (2005): time, queries and space, by sieving many coset states; Regev: polynomial space at time |
| Symmetric | graph isomorphism | no efficient algorithm; strong Fourier sampling on single coset states fails (Moore, Russell & Schulman), and measurements entangling coset states are necessary (Hallgren, Moore, Rötteler, Russell & Sen) |
| Some semidirect products, Heisenberg groups, groups with small commutator subgroups | test cases for the theory | polynomial-time algorithms using special structure (e.g. Bacon, Childs & van Dam 2005) |
Which statement about the non-abelian HSP is established?
- Kuperberg's algorithm solves the dihedral HSP in polynomial time
- Strong Fourier sampling on single coset states solves the symmetric-group HSP
- Polynomially many coset states suffice information-theoretically for every finite group
- An efficient dihedral HSP algorithm is known to break all lattice-based cryptography
Show the answer
C. Polynomially many coset states suffice information-theoretically for every finite group
That is the Ettinger–Høyer–Knill theorem. The open problem is computational: implementing the measurement efficiently.
Beyond subgroups
The framework has natural relatives. In the hidden shift problem you are given and and must find ; for injective on an abelian group it is equivalent to an HSP in a generalized dihedral group, while for shifted multiplicative characters such as the Legendre symbol it is easy (van Dam, Hallgren & Ip 2003). Isogeny-based cryptosystems such as CSIDH rest on an abelian group action, a hidden-shift structure, which is why Kuperberg-type subexponential algorithms set their quantum security (Childs, Jao & Soukharev 2014). Infinite groups fit too: Hallgren's algorithm for Pell's equation finds an irrational period on , and later work computes unit groups of number fields of arbitrary degree.
Key takeaways
- HSP: is constant on cosets of and distinct across them. Deutsch, Simon, order finding, discrete logs and Pell's equation are abelian instances.
- Abelian Fourier sampling turns a coset state into a uniform sample of ; samples generate , and (Kitaev 1995).
- Non-abelian HSPs have polynomial query complexity (Ettinger–Høyer–Knill), but no efficient measurement is known in general; weak Fourier sampling cannot tell conjugates apart.
- Dihedral HSP (lattices): subexponential, (Kuperberg). Symmetric HSP (graph isomorphism): entangled measurements over coset states are required.
- The abelian/non-abelian boundary marks where Shor-type speedups end, and underpins the belief that lattice-based cryptography is quantum-safe.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Simon's problem is the HSP with and . What does one round of Fourier sampling return?
- The string itself
- A uniformly random element of
- A uniformly random with
- A uniformly random with
Show the answer
D. A uniformly random with
The characters of are , and . About samples span , and follows by Gaussian elimination.
For discrete logarithms, on with . Fourier sampling returns uniform on . Which relation holds?
Show the answer
A.
, and iff . If is invertible, .
Why can weak Fourier sampling never distinguish a subgroup from a conjugate ?
- Because conjugate subgroups have different orders
- Because the QFT over a non-abelian group is not unitary
- Because the label distribution depends on only through characters, which are class functions, so it is the same for conjugate subgroups
- Because weak Fourier sampling uses only one query
Show the answer
C. Because the label distribution depends on only through characters, which are class functions, so it is the same for conjugate subgroups
, and . Distinguishing conjugates requires the row and column information of strong Fourier sampling, or entangled measurements on several copies.
Kuperberg's algorithm for the dihedral HSP over runs in time
- : subexponential in , but superpolynomial
- , like Grover search
Show the answer
B. : subexponential in , but superpolynomial
Kuperberg combines many coset states through a sieve on their labels, reaching time, queries and space. That beats any algorithm but is not polynomial in the input size .
Further reading
- A. M. Childs & W. van Dam, "Quantum algorithms for algebraic problems", Rev. Mod. Phys. 82, 1 (2010).
- A. Yu. Kitaev, "Quantum measurements and the Abelian stabilizer problem", arXiv:quant-ph/9511026 (1995).
- M. Ettinger, P. Høyer & E. Knill, "The quantum query complexity of the hidden subgroup problem is polynomial", Inf. Process. Lett. 91, 43 (2004).
- G. Kuperberg, "A subexponential-time quantum algorithm for the dihedral hidden subgroup problem", SIAM J. Comput. 35, 170 (2005).
- O. Regev, "Quantum computation and lattice problems", SIAM J. Comput. 33, 738 (2004).