Simple Algorithm
Quantum Computing · Rydberg State · 32 min

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 H⊥H^\perp, and that O(log⁡∣G∣)\order{\log\abs G} samples determine HH.
  • 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

ProblemGroup GGHidden subgroup HHQuantum status
Deutsch's problemZ2\Z_2Z2\Z_2 (constant ff) or {0}\{0\} (balanced)one query
Simon's problemZ2n\Z_2^n{0,s}\{0,s\}polynomial time
Order finding, factoringZ\Z (in practice Z2t\Z_{2^t})rZr\Zpolynomial time (Shor)
Discrete log h=gℓh=g^\ellZr×Zr\Z_r\times\Z_r, f(a,b)=gahbf(a,b)=g^ah^b⟨(−ℓ,1)⟩\langle(-\ell,1)\ranglepolynomial time (Shor)
Pell's equationR\RRZR\Z, RR the regulatorpolynomial time (Hallgren 2002)
Graph isomorphismS2nS_{2n}Aut⁡(Γ1⊔Γ2)\operatorname{Aut}(\Gamma_1\sqcup\Gamma_2)open; strong lower bounds for coset-state methods
Unique-SVP (lattices)dihedral DND_Na reflection subgroup {e,(d,1)}\{e,(d,1)\}subexponential (Kuperberg 2005)
The abelian rows are solved by one method. The non-abelian rows are where it stalls.

Fourier sampling solves the abelian case

The standard method has three moves. Query ff on a uniform superposition to get 1∣G∣∑g∣g⟩∣f(g)⟩\frac{1}{\sqrt{\abs G}}\sum_g\ket g\ket{f(g)}. Discard (or measure) the second register: the first is left in a uniformly random coset state ∣gH⟩=1∣H∣∑h∈H∣gh⟩\ket{gH}=\frac{1}{\sqrt{\abs H}}\sum_{h\in H}\ket{gh}, equivalently in the mixed state ρH=1[G:H]∑gH∣gH⟩ ⁣⟨gH∣\rho_H=\frac{1}{[G:H]}\sum_{gH}\ketbra{gH}{gH}. Then Fourier transform over GG and measure. For abelian GG (written additively) the analysis is a few lines.

DerivationAbelian Fourier sampling
  1. FG∣g+H⟩=1∣G∣∣H∣∑χ∈G^χ(g)(∑h∈Hχ(h))∣χ⟩F_G\ket{g+H}=\frac{1}{\sqrt{\abs G\abs H}}\sum_{\chi\in\widehat G}\chi(g)\Bigl(\sum_{h\in H}\chi(h)\Bigr)\ket\chi

    Linearity, and χ(g+h)=χ(g)χ(h)\chi(g+h)=\chi(g)\chi(h).

  2. ∑h∈Hχ(h)={∣H∣χ∈H⊥0otherwise,H⊥={χ:χ(h)=1 ∀h∈H}\sum_{h\in H}\chi(h)=\begin{cases}\abs H&\chi\in H^\perp\\0&\text{otherwise}\end{cases},\qquad H^\perp=\{\chi:\chi(h)=1\ \forall h\in H\}

    Restricted to HH, a character is a character of HH, and it sums to zero over HH unless it is trivial there.

  3. FG∣g+H⟩=∣H∣∣G∣∑χ∈H⊥χ(g)∣χ⟩F_G\ket{g+H}=\sqrt{\frac{\abs H}{\abs G}}\sum_{\chi\in H^\perp}\chi(g)\ket\chi

    The coset representative contributes only phases: the outcome is uniform on H⊥H^\perp, which has ∣G∣/∣H∣\abs G/\abs H elements.

  4. H={h∈G: χ(h)=1  ∀χ∈H⊥}H=\{h\in G:\ \chi(h)=1\ \ \forall\chi\in H^\perp\}

    HH is recovered from generators of H⊥H^\perp by solving linear equations: mod 2 for Simon, via the Smith normal form in general.

Predict before you look

G=Z32G=\Z_{32} and H=⟨8⟩={0,8,16,24}H=\langle8\rangle=\{0,8,16,24\}. How many distinct outcomes can Fourier sampling return?

Show the answer

8

∣H⊥∣=∣G∣/∣H∣=32/4=8\abs{H^\perp}=\abs G/\abs H=32/4=8: the multiples of 4. Each appears with probability 1/81/8.

Non-abelian groups: what breaks

For non-abelian GG the Fourier basis is labeled by irreducible representations σ\sigma (of dimension dσd_\sigma, with ∑σdσ2=∣G∣\sum_\sigma d_\sigma^2=\abs G) and matrix indices: FG∣g⟩=∑σdσ/∣G∣∑i,jσ(g)ij∣σ,i,j⟩F_G\ket g=\sum_{\sigma}\sqrt{d_\sigma/\abs G}\sum_{i,j}\sigma(g)_{ij}\ket{\sigma,i,j}. 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 σ\sigma (weak Fourier sampling) or also the row and column in a basis of your choice (strong Fourier sampling).

Weak Fourier sampling suffices when HH is normal (Hallgren, Russell & Ta-Shma 2000), but it cannot distinguish HH from a conjugate gHg−1gHg^{-1}: the label distribution P(σ)=dσ∣H∣∣G∣∑h∈Hχσ(h)P(\sigma)=\frac{d_\sigma\abs H}{\abs G}\sum_{h\in H}\chi_\sigma(h) depends on HH only through characters, which are class functions. Beyond normal subgroups, the story splits by group.

GroupWhy it mattersWhat is known
Dihedral DN=ZN⋊Z2D_N=\Z_N\rtimes\Z_2Regev (2004): solving the dihedral coset problem with suitable error tolerance would give a quantum algorithm for poly(nn)-unique-SVP, a lattice problemKuperberg (2005): 2O(log⁡N)2^{\order{\sqrt{\log N}}} time, queries and space, by sieving many coset states; Regev: polynomial space at 2O(log⁡Nlog⁡log⁡N)2^{\order{\sqrt{\log N\log\log N}}} time
Symmetric SnS_ngraph isomorphismno efficient algorithm; strong Fourier sampling on single coset states fails (Moore, Russell & Schulman), and measurements entangling Ω(nlog⁡n)\Omega(n\log n) coset states are necessary (Hallgren, Moore, Rötteler, Russell & Sen)
Some semidirect products, Heisenberg groups, groups with small commutator subgroupstest cases for the theorypolynomial-time algorithms using special structure (e.g. Bacon, Childs & van Dam 2005)
Check your understanding

Which statement about the non-abelian HSP is established?

  1. Kuperberg's algorithm solves the dihedral HSP in polynomial time
  2. Strong Fourier sampling on single coset states solves the symmetric-group HSP
  3. Polynomially many coset states suffice information-theoretically for every finite group
  4. 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 ff and g(x)=f(x+s)g(x)=f(x+s) and must find ss; for injective ff 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 R\R, and later work computes unit groups of number fields of arbitrary degree.

Key takeaways

  • HSP: ff is constant on cosets of HH 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 H⊥H^\perp; O(log⁡∣G∣)\order{\log\abs G} samples generate H⊥H^\perp, and H=(H⊥)⊥H=(H^\perp)^\perp (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, 2O(log⁡N)2^{\order{\sqrt{\log N}}} (Kuperberg). Symmetric HSP (graph isomorphism): entangled measurements over Ω(nlog⁡n)\Omega(n\log n) 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.

Question 1

Simon's problem is the HSP with G=Z2nG=\Z_2^n and H={0,s}H=\{0,s\}. What does one round of Fourier sampling return?

  1. The string ss itself
  2. A uniformly random element of HH
  3. A uniformly random yy with y⋅s=1y\cdot s=1
  4. A uniformly random yy with y⋅s=0(mod2)y\cdot s=0\pmod2
Show the answer

D. A uniformly random yy with y⋅s=0(mod2)y\cdot s=0\pmod2

The characters of Z2n\Z_2^n are χy(x)=(−1)y⋅x\chi_y(x)=(-1)^{y\cdot x}, and H⊥={y:χy(s)=1}={y:y⋅s=0}H^\perp=\{y:\chi_y(s)=1\}=\{y:y\cdot s=0\}. About nn samples span H⊥H^\perp, and ss follows by Gaussian elimination.

Question 2

For discrete logarithms, f(a,b)=gahbf(a,b)=g^ah^b on Zr×Zr\Z_r\times\Z_r with h=gℓh=g^\ell. Fourier sampling returns (c,d)(c,d) uniform on H⊥H^\perp. Which relation holds?

  1. d≡ℓc(modr)d\equiv\ell c\pmod r
  2. c≡ℓd(modr)c\equiv\ell d\pmod r
  3. c+d≡ℓ(modr)c+d\equiv\ell\pmod r
  4. cd≡ℓ(modr)cd\equiv\ell\pmod r
Show the answer

A. d≡ℓc(modr)d\equiv\ell c\pmod r

H=⟨(−ℓ,1)⟩H=\langle(-\ell,1)\rangle, and χ(c,d)(−ℓ,1)=ωr−cℓ+d=1\chi_{(c,d)}(-\ell,1)=\omega_r^{-c\ell+d}=1 iff d≡ℓcd\equiv\ell c. If cc is invertible, ℓ=dc−1 mod r\ell=dc^{-1}\bmod r.

Question 3

Why can weak Fourier sampling never distinguish a subgroup HH from a conjugate gHg−1gHg^{-1}?

  1. Because conjugate subgroups have different orders
  2. Because the QFT over a non-abelian group is not unitary
  3. Because the label distribution depends on HH only through characters, which are class functions, so it is the same for conjugate subgroups
  4. Because weak Fourier sampling uses only one query
Show the answer

C. Because the label distribution depends on HH only through characters, which are class functions, so it is the same for conjugate subgroups

P(σ)∝dσ∑h∈Hχσ(h)P(\sigma)\propto d_\sigma\sum_{h\in H}\chi_\sigma(h), and χσ(ghg−1)=χσ(h)\chi_\sigma(ghg^{-1})=\chi_\sigma(h). Distinguishing conjugates requires the row and column information of strong Fourier sampling, or entangled measurements on several copies.

Question 4

Kuperberg's algorithm for the dihedral HSP over DND_N runs in time

  1. poly⁡(log⁡N)\poly(\log N)
  2. 2O(log⁡N)2^{\order{\sqrt{\log N}}}: subexponential in log⁡N\log N, but superpolynomial
  3. O(N)\order{\sqrt N}, like Grover search
  4. O(N)\order{N}
Show the answer

B. 2O(log⁡N)2^{\order{\sqrt{\log N}}}: subexponential in log⁡N\log N, but superpolynomial

Kuperberg combines many coset states through a sieve on their labels, reaching 2O(log⁡N)2^{\order{\sqrt{\log N}}} time, queries and space. That beats any poly⁡(N)\poly(N) algorithm but is not polynomial in the input size log⁡N\log N.

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).