The Hidden Subgroup Problem

You have already met three quantum algorithms built around oracle access to a mystery function: Deutsch decides "constant vs balanced" in one query, Bernstein-Vazirani extracts a hidden bit string s from a linear function in one query, and Simon's finds a hidden XOR-period s in polynomially many queries. Soon you will meet Shor's algorithm, which finds the period of modular exponentiation and so breaks RSA. Those are four different algorithms for four different problems — but they feel oddly related, and not just because they all start "prepare a superposition, query the oracle, do a Fourier-like transform, measure."

They are related. Each one is a special case of a single problem. That problem is the Hidden Subgroup Problem, and once you see the algorithms as instances of it, you stop learning them one at a time. You specialise the general template to each group G, and the algorithm falls out.

HSP is not a minor bit of theoretical tidying. It is the reason Peter Shor could write down his factoring algorithm within a year of Simon's period-finding result: Simon had solved the HSP instance for \mathbb{Z}_2^n, and Shor saw that factoring reduced to the HSP instance for \mathbb{Z} — with essentially the same circuit shape, just a different Fourier transform at the end. HSP is the map of where exponential quantum speedups live, what territory has been explored, and what territory — most of it non-abelian — is still uncharted three decades after the original results.

The setup — groups, subgroups, cosets, and a promise

Before stating HSP cleanly, pin down the four objects it refers to.

A group G is a set with a binary operation (written multiplicatively or additively depending on convention), an identity element, and inverses for every element, such that the operation is associative. You have seen several:

• \mathbb{Z}_2 = \{0, 1\} under addition mod 2.
• \mathbb{Z}_2^n — n-bit strings under bitwise XOR.
• \mathbb{Z}_N = \{0, 1, \ldots, N-1\} under addition mod N.
• \mathbb{Z} — all integers under ordinary addition.
• \mathbb{Z}_p^* = \{1, 2, \ldots, p-1\} — nonzero residues mod a prime p, under multiplication.
• S_n — the symmetric group, permutations of n objects, under composition.
• D_n — the dihedral group, symmetries of a regular n-gon.

The first five are abelian (the operation commutes: g \cdot h = h \cdot g). The last two are non-abelian. This distinction will matter enormously.

A subgroup H \le G is a subset of G that is closed under the group operation and inverses — a group in its own right, sitting inside G. For \mathbb{Z}_2^n, any XOR-closed subset is a subgroup (for instance \{0, s\} for a fixed string s is a two-element subgroup, provided s \ne 0). For \mathbb{Z}, every subgroup is of the form r\mathbb{Z} = \{0, \pm r, \pm 2r, \ldots\} for some non-negative integer r. Subgroups are specified either by listing their elements (for small groups) or by giving a set of generators whose products give every element of the subgroup.

A coset of H in G is a set of the form gH = \{gh : h \in H\} for a specific g \in G. Cosets partition G into equal-sized blocks. Two elements g, g' are in the same coset if and only if g^{-1}g' \in H (in additive notation, g' - g \in H). The subgroup H itself is one coset (the one containing the identity); all other cosets are disjoint translates.

Why cosets matter here: the HSP promise says f takes the same value on every element of a single coset and different values on different cosets. So f is constant on each "layer" and the layers are labelled by the distinct values of f. If you could only learn which-coset-a-random-g-is-in, you could read off H by comparing elements — but reading that off classically requires finding collisions among f-values, which is the expensive part.

The promise. Fix a group G. A function f: G \to X (where X is some "label set" — could be \{0,1\}^n, or the integers, or anything) hides the subgroup H if:

In additive notation (which you will use for \mathbb{Z}_2^n and \mathbb{Z}): f(g) = f(h) \iff g - h \in H, i.e. g and h are in the same coset of H.

The problem. You are given oracle access to f. Find H — say, by returning a set of generators — using as few oracle queries as possible. The running time should be polynomial in \log |G| where possible.

That is HSP. The drama is all in the choice of G.

The four instances you already know

Before the general algorithm, see how four familiar algorithms fit this template.

Deutsch — G = \mathbb{Z}_2

The function is f: \{0, 1\} \to \{0, 1\}. The hidden subgroup is either:

• H = \{0, 1\} = \mathbb{Z}_2 itself, if f is constant (there is only one coset, which is all of G, and f is the same on both elements).
• H = \{0\}, the trivial subgroup, if f is balanced (each coset is a single element, and the two elements get different values).

Finding H is literally the Deutsch problem: distinguish constant from balanced. One quantum query does it.

Bernstein-Vazirani — G = \mathbb{Z}_2^n, hiding a hyperplane

The function is f(x) = s \cdot x \pmod 2 for a hidden n-bit string s. Here f is constant on the hyperplane H = \{x : s \cdot x = 0\} (a subgroup of \mathbb{Z}_2^n of size 2^{n-1}) and takes the opposite value on the other coset. So the hidden subgroup is \{x : s \cdot x = 0\} and BV's algorithm recovers s — equivalently, a generator of H^\perp, the "orthogonal complement" of H.

Simon — G = \mathbb{Z}_2^n, hiding a period

The function f: \mathbb{Z}_2^n \to X satisfies f(x) = f(y) \iff x \oplus y \in \{0, s\}. The hidden subgroup is H = \{0, s\}, a size-2 subgroup of \mathbb{Z}_2^n. Simon's algorithm finds s in O(n) quantum queries, while classical needs \Omega(2^{n/2}). The template is exactly HSP over \mathbb{Z}_2^n — Simon's algorithm is what the general abelian HSP algorithm looks like when you write it out for the group \mathbb{Z}_2^n.

Shor's order-finding — G = \mathbb{Z}, hiding a period

Fix a positive integer N and an element a with \gcd(a, N) = 1. Define f: \mathbb{Z} \to \mathbb{Z}_N by f(k) = a^k \bmod N. This function has a period r — the order of a modulo N — such that f(k) = f(\ell) \iff k \equiv \ell \pmod r, i.e. k - \ell \in r\mathbb{Z}. So the hidden subgroup is H = r\mathbb{Z}, and finding r is exactly HSP over \mathbb{Z}.

Finding the order r lets you factor N with high probability (via a classical reduction going back to the 1970s). So factoring ≡ HSP over \mathbb{Z}. Shor's algorithm uses a quantum Fourier transform over \mathbb{Z}_Q (for Q \approx N^2) to implement the general HSP algorithm specialised to this instance.

One more abelian instance worth naming: the discrete-logarithm problem, central to public-key cryptography (Diffie-Hellman, ECC), is HSP for the group G = \mathbb{Z}_{p-1} \times \mathbb{Z}_{p-1}. Shor's algorithm handles this too. Taking Diffie-Hellman and ECC off the table alongside RSA is why "post-quantum cryptography" is a policy topic at the Government of India's National Quantum Mission.

The general abelian HSP algorithm

Every abelian HSP instance is solved by the same quantum algorithm — the specialisation just changes which Fourier transform you use at the end.

The recipe, in five steps.

1. Prepare a uniform superposition over G in a "coset register":

1. Query the oracle U_f|g\rangle|y\rangle = |g\rangle|y \oplus f(g)\rangle to load f into the second register:

1. Measure the second register. It collapses to some specific value f(g_0). Because f is constant on cosets and distinct across cosets, the first register collapses onto the unique coset g_0 H:

1. Apply the quantum Fourier transform over G to the first register. For the abelian group G, the QFT takes a uniform superposition over a coset of H to a uniform superposition over the character subgroup H^\perp — the characters of G that are trivial on H.

2. Measure the first register. You get a random element of H^\perp. Repeat the whole procedure O(\log |G|) times, collect the samples, and solve a linear-algebra problem over the appropriate ring to determine H.

Why the QFT does the work: characters of an abelian group G are the group homomorphisms \chi: G \to \mathbb{C}^\times landing in the unit circle. The QFT over G is exactly the change of basis from "group elements" to "characters." For a coset g_0 H, the characters that vanish on H survive the Fourier transform; the others cancel by interference. This is the same constructive/destructive-interference pattern you saw in Deutsch-Jozsa, generalised to an arbitrary abelian group.

The five instances you met above are this algorithm with different choices of G:

• Deutsch (G = \mathbb{Z}_2): QFT over \mathbb{Z}_2 is the single-qubit Hadamard H.
• BV and Simon (G = \mathbb{Z}_2^n): QFT over \mathbb{Z}_2^n is H^{\otimes n}.
• Shor's order-finding (G \approx \mathbb{Z}, truncated to \mathbb{Z}_Q): QFT over \mathbb{Z}_Q for Q a large power of 2, the "standard" QFT of textbooks.
• Discrete log (G = \mathbb{Z}_{p-1} \times \mathbb{Z}_{p-1}): a tensor product of two \mathbb{Z}_{p-1} QFTs.

The Hadamard-oracle-Hadamard structure you have been seeing since Deutsch is the \mathbb{Z}_2^n specialisation of this single algorithm. That is not a coincidence — it is the whole point of introducing HSP.

The running time. For every abelian G, the algorithm uses O(\log |G|) oracle queries and O(\text{poly}(\log |G|)) gates (assuming the QFT over G can be implemented efficiently — which it can for every group you meet in cryptographic practice). So every abelian HSP instance has a quantum polynomial-time algorithm. Abelian HSP is solved.

The non-abelian cliff

Move one step outside the abelian world and the whole framework trips.

Non-abelian groups have a richer representation theory — their characters are no longer complex numbers but matrices. The "Fourier transform" over a non-abelian group still exists (it is the standard object in non-abelian harmonic analysis), but decoding a coset state by measuring after the Fourier transform no longer yields a clean linear system for H. What you learn from one Fourier-sampled measurement over a non-abelian group is, in general, not enough to reconstruct the hidden subgroup even after many samples.

Three specific non-abelian HSP cases drive the field.

Graph isomorphism — HSP over the symmetric group S_n. Two graphs on n vertices are isomorphic if one can be permuted into the other. Define f: S_n \to X so that f(\pi) records the graph obtained by applying \pi to a fixed labelling, with some canonical tag to identify "the same graph under different permutations." Then f hides the automorphism group of the combined graph, and HSP-solving would immediately solve graph isomorphism. Graph isomorphism is in complexity class P for restricted graph classes, in quasipolynomial time classically (Babai 2015), and not known to be in classical P in general. A quantum polynomial-time algorithm for HSP over S_n would imply a quantum polynomial-time algorithm for graph isomorphism — a major open problem.

Dihedral HSP — HSP over D_N. The dihedral group of order 2N has a "hidden shift" structure that equivalent formulations connect to shortest-vector problems in lattices — the computational problem underpinning lattice-based cryptography (learning-with-errors, Ring-LWE, and most post-quantum schemes). An efficient quantum algorithm for dihedral HSP would break lattice-based cryptography. Kuperberg's algorithm (2003) solves dihedral HSP in 2^{O(\sqrt{\log N})} time — subexponential, but nowhere near polynomial, so lattice crypto remains quantum-safe by current best knowledge.

General non-abelian HSP. For an arbitrary finite group, no general efficient quantum algorithm is known. The standard approach — coset state + Fourier sampling — fails to extract enough information per sample. The best general result is that polynomially many coset samples are information-theoretically sufficient to determine H (Ettinger, Høyer, Knill 1999), but no efficient decoding algorithm is known. This gap — information sufficient, algorithm unknown — is one of the central open problems in quantum algorithms.

Common confusions

• "HSP is just theory — not a practical framework." No. HSP is how quantum-algorithm designers decide whether to even try. When a new problem arrives, the first question is: can you cast it as an HSP instance over an abelian group? If yes, you have a polynomial-time quantum algorithm for free. If only as a non-abelian HSP, your situation is far harder. The framework is the filter.

• "Abelian HSP is 'solved' means every problem reducing to abelian HSP is easy for a quantum computer." Only the oracle-query part. Implementing the oracle efficiently (the classical circuit that computes f) is a separate task. In Shor's case, modular exponentiation is efficient classically, so the HSP-oracle is cheap, and the whole algorithm runs in polynomial time. In other cases, the oracle could be expensive even when HSP itself is "solved."

• "Non-abelian HSP is open" means "no quantum advantage at all over classical." Not quite. Kuperberg's dihedral algorithm is subexponential (2^{O(\sqrt{\log N})}), which is genuinely faster than the best known classical algorithms for lattice problems in some regimes — it just is not polynomial. The non-abelian frontier has partial results, specific subgroups that work, and reductions among instances. It is a live research area, not a dead one.

• "Graph isomorphism has a known quantum polynomial-time algorithm." No. Babai's 2015 quasipolynomial classical algorithm made GI much more tractable classically, but no quantum polynomial-time algorithm is known. Reducing GI to HSP over S_n does not solve GI — you still need to solve HSP over S_n, which is what is open.

• "Learning the abelian HSP algorithm is enough to learn Shor's algorithm." It is most of Shor's algorithm — everything except the classical reduction from factoring to order-finding, and the specific technical hiccup that Shor's uses a QFT over a truncated \mathbb{Z}_Q (because \mathbb{Z} itself is infinite) rather than a literal \mathbb{Z}-QFT. But yes, once you have HSP, Shor's is a short walk.

• "HSP only applies to oracle problems." HSP in its purest form is an oracle problem. But in Shor's algorithm the "oracle" is a real circuit (modular exponentiation), not a mysterious black box. The oracle formulation is a way to talk about the algorithm's structure; when the oracle is itself efficient, the algorithm becomes a full non-oracle algorithm.

Going deeper

The QFT-based algorithm, formally

For an abelian group G, a character is a group homomorphism \chi : G \to \mathbb{C}^\times whose image lies on the unit circle. The set of all characters of G forms a group \hat{G} — the dual group — and for abelian G there is a natural isomorphism \hat{G} \cong G. Characters are the "frequencies" of G.

The quantum Fourier transform over G acts as

For G = \mathbb{Z}_N, characters are \chi_k(j) = e^{2\pi i jk / N} — the standard DFT. For G = \mathbb{Z}_2^n, characters are \chi_s(x) = (-1)^{s \cdot x} — the Hadamard transform.

Given a coset state \frac{1}{\sqrt{|H|}} \sum_{h \in H} |g_0 h\rangle, apply \text{QFT}_G:

The inner sum \sum_h \chi(h) is |H| if \chi is trivial on H (i.e., \chi \in H^\perp) and 0 otherwise. So the QFT outputs a uniform superposition over H^\perp, scaled by a global phase \chi(g_0) per term. Measurement yields a uniformly random element of H^\perp. Since H^\perp \cong G/H and H is recovered as the annihilator of H^\perp, O(\log |G|) samples suffice to determine H via linear algebra.

Dihedral HSP and lattice cryptography

The dihedral group D_N consists of 2N elements: N rotations and N reflections. Its subgroup structure is rich, but the hardest HSP case turns out to be when H is generated by a single reflection. Fourier sampling over D_N produces a state whose measurement reveals a "hidden shift" s \in \mathbb{Z}_N encoded in the phases of a two-qubit system. Extracting s from this state is equivalent to the unique shortest vector problem (uSVP) in a two-dimensional lattice — and uSVP in higher dimensions underpins lattice-based cryptography.

The best algorithm is Kuperberg's sieve (2003), running in 2^{O(\sqrt{\log N})} time and space. This is subexponential in \log N (so better than classical 2^{O(\sqrt{N})}), but nowhere near polynomial, meaning the lattice-based post-quantum schemes currently being standardised by NIST (like Kyber and Dilithium) remain safe under current best knowledge. If someone finds a polynomial-time quantum algorithm for dihedral HSP, most post-quantum cryptography breaks. This is why dihedral HSP is not a theoretical curiosity — it is the single-biggest known threat to the "post-quantum" security landscape.

Graph isomorphism as HSP over S_n

Given two graphs G_1, G_2 on n vertices, form the disjoint-union graph G_1 \sqcup G_2 on 2n vertices. Define f : S_{2n} \to \{\text{graphs}\} by f(\pi) = \pi(G_1 \sqcup G_2), the graph obtained by permuting vertices. The stabiliser of f — the set of permutations that map G_1 \sqcup G_2 to itself — is the automorphism group of G_1 \sqcup G_2. A non-trivial automorphism that swaps G_1 and G_2 exists if and only if the two graphs are isomorphic.

So graph isomorphism reduces to finding the automorphism group of G_1 \sqcup G_2 — which is the HSP for G = S_{2n}. The group S_{2n} is the most notoriously-structured non-abelian group for HSP. Even determining whether a specific ansatz approach will work is open; three decades in, and graph isomorphism is still not known to be in quantum polynomial time.

Kuperberg's subexponential algorithm — the sketch

Kuperberg's idea: instead of trying to extract s from one Fourier sample, generate many coset states, pair them up, and combine them via a sieve to create states with progressively clearer phase information. Each combine step doubles the accuracy but halves the number of states; with 2^{O(\sqrt{\log N})} starting states, you end up with one state clear enough to read s off directly. The algorithm is a rare example of a quantum speedup not built on Fourier sampling alone — it uses classical post-processing structure that has no analogue in abelian HSP.

The hidden shift problem — HSP's sibling

Closely related to HSP is the hidden shift problem: given two functions f_0, f_1 : G \to X with the promise that f_1(g) = f_0(gs) for some fixed s, find s. For abelian G, hidden shift reduces to HSP over G \times \mathbb{Z}_2 (with an extra register indicating which function you queried), so the abelian solutions transfer. For non-abelian G, hidden shift can be strictly harder than HSP — different algorithmic techniques apply. Hidden shift over \mathbb{Z}_N is equivalent to dihedral HSP, so the two problems are the same.

The broader speedup taxonomy

HSP is the home of almost every exponential oracle quantum speedup you will meet. The other main family — quadratic speedups — comes from Grover's algorithm and its generalisations, which are not HSP instances and have a different geometric picture (amplitude amplification). There are a handful of known quantum speedups that do not fit either framework (Child's quantum walk on graphs, the glued-trees problem, Jordan's quantum gradient algorithm), but the vast majority of exponential separations are HSP-flavoured.

Indian context — IIT, TIFR, and post-quantum cryptography

Theoretical computer science groups at TIFR Mumbai, IIT Bombay, IIT Delhi, IIT Madras, and IISc Bangalore have worked on quantum algorithms, HSP variants, and lattice problems. Ashwin Nayak (IIT alumnus), Rahul Jain (NUS, Indian-trained), and others have contributed to oracle lower bounds and the formal structure underlying quantum separations. The connection between dihedral HSP and lattice cryptography is particularly relevant for India: because Aadhaar, UPI, and most government digital infrastructure rely on RSA/ECC, the migration to post-quantum cryptographic standards is a policy priority under the National Quantum Mission. The schemes India is likely to adopt (Kyber, Dilithium) depend on the continued intractability of lattice problems — which depends on the continued intractability of dihedral HSP. The frontier of HSP research is not just theoretical elegance; it is security assumptions that will underpin the signatures on a billion Indian bank transactions in the coming decade.

Where this leads next

• Simon's algorithm — the cleanest non-trivial HSP instance; HSP for \mathbb{Z}_2^n with a period-2 subgroup, in full detail.
• Shor's algorithm — HSP for \mathbb{Z} specialised to order-finding, plus the classical reduction to factoring.
• The Quantum Fourier Transform — the machinery that makes every abelian HSP instance solvable.
• Graph isomorphism and HSP — the non-abelian frontier via S_n.
• Dihedral HSP and lattice crypto — the connection between Kuperberg's algorithm and the security of post-quantum cryptography.
• The Oracle Model — the framework inside which all HSP results are stated.

References

1. Wikipedia, Hidden subgroup problem — standard encyclopaedic summary with the abelian algorithm and instance list.
2. Richard Jozsa, Quantum factoring, discrete logarithms, and the hidden subgroup problem (2001) — influential survey placing Shor's and Simon's in the HSP framework. arXiv:quant-ph/0012084.
3. John Preskill, Lecture Notes on Quantum Computation, Ch. 6 — theory.caltech.edu/~preskill/ph229.
4. Alexei Kitaev, Quantum measurements and the Abelian stabilizer problem (1995) — the abelian HSP result in its original form. arXiv:quant-ph/9511026.
5. Andrew Childs and Wim van Dam, Quantum algorithms for algebraic problems (2010) — broad survey of HSP and related problems. arXiv:0812.0380.
6. Oded Regev, Quantum computation and lattice problems (2002) — the dihedral-HSP-to-lattice connection. arXiv:cs/0304005.