The hidden subgroup problem asks whether a function hides a subgroup inside its repeated values. Quantum algorithms exploit superposition to create coset states, then use group Fourier transforms to turn hidden translation symmetry into algebraic constraints on the subgroup.
This framework unifies several landmark algorithms. Simon’s problem hides a two-element subgroup of the Boolean vector space Z₂ⁿ. Period finding hides an integer period. Shor’s order-finding algorithm is an Abelian hidden-subgroup problem after the relevant periodic structure is identified. The common pattern is not “quantum parallelism” by itself; it is Fourier analysis of symmetry.
Guide 9 owns the Quantum Fourier Transform and the Representation Mathematics estate owns finite-group harmonic analysis in general. This guide owns the oracle-algorithmic hidden-subgroup job: promise functions, coset-state preparation, Fourier sampling, reconstruction and the boundary where non-Abelian groups become difficult.
Oracle with hidden symmetry → superposition query → erase function value → coset state → Fourier transform → sample characters trivial on the subgroup → reconstruct the subgroup.
1. Hidden subgroup definition
Let G be a finite group and H≤G a subgroup.
A function
f:G→S
hides H when
- f is constant on each left coset gH;
- f takes distinct values on distinct cosets.
Equivalently,
f(g₁)=f(g₂) iff g₁H=g₂H.
The computational task is to determine generators or another description of H using oracle access to f.
2. Why cosets are the observable structure
The oracle does not label H directly. It labels equivalence classes defined by left cosets.
If one knew f(g), one would know which coset gH contains g but not which element of that coset is the subgroup identity shift.
Quantumly, querying f in superposition and measuring/discarding the output register projects the group register onto a uniform superposition over one random coset.
3. Coset-state preparation
Start from the uniform group superposition
|G⟩=(1/√|G|)Σ_{g∈G}|g⟩.
Query the oracle:
(1/√|G|)Σ_g |g⟩|0⟩ → (1/√|G|)Σ_g|g⟩|f(g)⟩.
Measuring the second register to some value f(g₀) leaves the first register in
|g₀H⟩=(1/√|H|)Σ_{h∈H}|g₀h⟩.
The random representative g₀ is nuisance information; the subgroup geometry is common to every coset state.
4. Abelian characters
For a finite Abelian group G, irreducible representations are one-dimensional characters χ:G→U(1).
The quantum Fourier transform maps
|g⟩ → (1/√|G|)Σ_χ χ(g)|χ⟩
up to complex-conjugation convention.
Characters convert translations in G into phases, just as ordinary Fourier modes diagonalise cyclic shifts.
5. Annihilator subgroup
Define the annihilator
H^⊥={χ∈Ĝ : χ(h)=1 for every h∈H}.
Apply the Abelian QFT to a coset state:
|g₀H⟩=(1/√|H|)Σ_{h∈H}|g₀h⟩.
The Fourier amplitude of χ is proportional to
χ(g₀)Σ_{h∈H}χ(h).
The subgroup character sum vanishes unless χ is trivial on H. Therefore Fourier measurement samples characters from H⊥.
6. Why the random coset representative disappears
The factor χ(g₀) has unit magnitude.
It changes only Fourier phase, not measurement probability.
Thus all random cosets yield the same Fourier-support distribution over H⊥.
This is the crucial symmetry extraction: measurement forgets where the coset sits while retaining which characters are compatible with its internal translations.
7. Simon’s problem
Let
f:{0,1}^n→S
satisfy the promise that for one secret nonzero bit string s,
f(x)=f(y) iff y=x or y=x⊕s.
The hidden subgroup is
H={0,s}
inside the Abelian group Z₂ⁿ under bitwise XOR.
Simon showed an exponential quantum query advantage over classical randomized algorithms in the black-box model.
8. Simon coset state
Prepare uniform x, query f and measure/discard the function register.
The input register becomes
(|x⟩+|x⊕s⟩)/√2.
Apply H⊗n, the QFT over Z₂ⁿ.
Using
H^{⊗n}|x⟩=(1/√2^n)Σ_y(−1)^{x·y}|y⟩,
the two branches interfere.
9. Derive Simon’s linear constraint
The Fourier amplitude for y is proportional to
(−1)^{x·y}[1+(−1)^{s·y}].
If s·y=1 mod2, the bracket is zero.
If s·y=0 mod2, the bracket is 2.
Therefore every measured y satisfies
y·s=0 (mod2).
Each run gives one homogeneous linear equation for the unknown bits of s.
10. Worked Simon reconstruction
Let n=3 and hidden string s=101.
Valid Fourier samples satisfy y₁+y₃=0 mod2.
Suppose two independent samples are
y^(1)=010, giving s₂=0;y^(2)=111, giving s₁+s₂+s₃=0.
With s₂=0, the second equation gives s₁=s₃.
The solutions are 000 and 101. The promise says s is nonzero, so
s=101.
11. Query complexity of Simon’s algorithm
Roughly n−1 independent equations determine a one-dimensional hidden subspace.
Random valid y vectors become independent quickly, so O(n) oracle queries suffice with high probability.
Classically, finding a collision f(x)=f(x⊕s) in a black-box two-to-one function requires exponentially many queries in n in the randomized oracle model.
This was one of the first clean exponential quantum query separations and directly inspired Shor’s periodicity algorithm.
12. Period finding as HSP
For an integer-periodic function f(x+r)=f(x), the hidden subgroup of Z is
H=rZ.
Z is infinite, so practical quantum algorithms work with large finite registers whose Fourier resolution approximates characters of the integer group.
Shor’s order finding is therefore closely related to an Abelian HSP over a cyclic/integer periodic structure.
13. HSP over Z_N
Let G=ZN and H be generated by d, where d divides N.
Then
H={0,d,2d,…} modN.
Characters are
χ_k(x)=e^{2πikx/N}.
χk is trivial on H when
kd≡0 modN.
Fourier samples therefore reveal multiples of N/d and determine the hidden subgroup through ordinary gcd/integer reconstruction.
14. General finite Abelian groups
Every finite Abelian group decomposes as a product of cyclic groups:
G≅Z_{N1}×…×Z_{Nk}.
The QFT factorises accordingly.
Fourier samples provide linear congruence constraints describing H⊥. Classical algebra then reconstructs generators for H.
This gives polynomial-time quantum algorithms for the finite Abelian hidden-subgroup problem under efficient group decomposition/operation assumptions.
15. Discrete logarithm as hidden linear structure
Suppose g generates a cyclic group and h=gx is given. We want x.
Define
f(a,b)=g^a h^{-b}=g^{a−bx}.
The function is constant along pairs differing by multiples of (x,1) in an appropriate product group.
Fourier sampling recovers linear relations that reveal x.
This is the structural reason Shor’s discrete-log algorithm parallels factoring/order finding.
16. Oracle model matters
Simon’s exponential separation is an oracle/query-complexity result.
An oracle query is treated as one operation even if implementing the function f might itself be expensive.
For end-to-end algorithms like Shor, modular arithmetic is explicit and polynomial-time implementable, so the quantum speedup survives beyond the black-box abstraction.
For arbitrary HSP instances, one must account for the cost of group operations, function evaluation and encoding.
17. Non-Abelian Fourier transform
For non-Abelian groups, irreducible representations can have dimension greater than one.
The Fourier transform no longer labels one-dimensional characters alone. It produces representation labels and matrix indices.
Weak Fourier sampling measures only the irreducible representation label. Strong Fourier sampling also resolves row/column information.
Neither automatically solves every non-Abelian HSP efficiently.
18. Dihedral hidden subgroup problem
The dihedral group HSP includes hidden reflections and is closely connected to lattice problems.
Kuperberg gave a subexponential quantum algorithm, faster than known generic classical approaches but not polynomial.
This demonstrates an important boundary: non-Abelian HSP can still yield quantum advantage without inheriting the clean polynomial-time Abelian solution.
19. Symmetric-group HSP and graph isomorphism
Graph isomorphism can be reduced to a hidden-subgroup-type problem over a symmetric group.
However, straightforward Fourier sampling does not provide a known efficient quantum solution.
This is one reason the hidden-subgroup framework is conceptual rather than a universal algorithm recipe.
20. Coset-state entanglement measurements
For difficult non-Abelian groups, information about H can be spread across many coset-state copies.
Collective entangled measurements on multiple copies can be information-theoretically powerful even when no efficient circuit implementing the optimal measurement is known.
This separates sample complexity from computational complexity: few quantum states may contain enough information, yet extracting it efficiently can remain hard.
21. Hidden shift problems
A related problem gives two functions f₀,f₁ with
f₁(x)=f₀(xs)
or an additive analogue and asks for hidden shift s.
Some hidden-shift problems reduce to HSPs in semidirect-product groups.
This links group-theoretic quantum algorithms to cryptographic hidden-shift assumptions and Boolean-function problems.
22. Common misconception: Fourier sampling reveals H directly in one shot
Each measurement gives one random constraint drawn from H⊥. Several independent samples and classical algebra are usually needed to reconstruct H.
23. Common misconception: every group Fourier transform makes HSP efficient
Efficiently implementing the QFT is only one requirement. The measured Fourier information must also identify H efficiently, which fails for important non-Abelian cases.
24. Common misconception: Simon and Shor are unrelated tricks
Both exploit hidden translation/period symmetry by preparing coset-like superpositions and Fourier sampling. Simon’s problem was a direct conceptual precursor to Shor’s algorithms.
25. Worked synthesis problem
Let G=Z₂³ and suppose an oracle hides H={000,101}.
Step 1: Coset. One measured oracle output leaves a state (|x⟩+|x⊕101⟩)/√2.
Step 2: Fourier transform. Apply H⊗3.
Step 3: Allowed samples. Only y satisfying y·101=0 mod2 have nonzero probability.
Step 4: Suppose y=010 and y=111 are observed. The equations are s₂=0 and s₁+s₂+s₃=0.
Step 5: Recover. Nonzero solution is s=101. The hidden subgroup is therefore generated by 101.
26. Practice set
- Define when f hides subgroup H.
- What state remains after querying f uniformly and measuring one oracle value?
- What is H⊥ for an Abelian group?
- Why do Fourier samples lie in H⊥?
- State Simon’s promise.
- What equation does each Simon Fourier sample satisfy?
- Why do O(n) Simon samples suffice?
- How is integer period finding an HSP?
- What changes in a non-Abelian Fourier transform?
- Why is graph isomorphism not solved merely by applying a symmetric-group QFT?
- What is the difference between sample complexity and computational complexity for coset states?
- Why does the oracle model need to be stated in speedup claims?
Answers
- f is constant on each left coset gH and distinct on different cosets.
- The uniform coset state
|gH⟩. - The characters χ that satisfy χ(h)=1 for every h∈H.
- The subgroup character sum cancels unless χ is trivial on H.
f(x)=f(y)exactly when y=x or y=x⊕s for one hidden nonzero s.y·s=0 mod2.- Each gives a random homogeneous linear constraint; about n−1 independent constraints determine the one-dimensional orthogonal complement.
- The hidden subgroup of Z is rZ when f(x+r)=f(x).
- Irreducible representations can be matrix valued, so Fourier basis labels include representation and matrix indices.
- The Fourier data obtained by feasible measurements do not reveal the hidden subgroup efficiently in known algorithms.
- Few copies may contain enough information in principle, while the required joint measurement can still be computationally inefficient.
- A black-box query may hide expensive function implementation, so oracle query count is not automatically end-to-end runtime.
Sources and further study
[1] Daniel R. Simon, On the Power of Quantum Computation, SIAM Journal on Computing 26, 1474–1483 (1997). The foundational hidden-XOR problem and exponential oracle separation.
[2] Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. Period finding and discrete-log algorithms built from Fourier sampling.
[3] Michele Mosca and Artur Ekert, The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer. Connects HSP structure with phase/eigenvalue estimation.
[4] Greg Kuperberg, A subexponential-time quantum algorithm for the dihedral hidden subgroup problem, SIAM Journal on Computing 35, 170–188 (2005).
Continue through Quantum Mathematics
Guide 65: Shor’s Algorithm, Order Finding, Period Finding, Modular Exponentiation and Integer Factoring is the central Abelian-period application. Guide 67: Quantum Gibbs-State Preparation, Thermal Sampling, Partition Functions and Quantum Metropolis Methods develops quantum sampling. Guide 68: Quantum Semidefinite Programming, Matrix Multiplicative Weights, Convex Optimisation and Quantum SDP Solvers develops convex optimisation.