Hidden Subgroup Problem

The Hidden Subgroup Problem is the organizing abstraction of quantum algorithmics — the single template from which nearly every exponential quantum speedup descends. You are handed black-box access to a function $f:G\to S$ from a group $G$ into some set of labels $S$ , with one promise: there is a subgroup $H\le G$ such that $f(g_1)=f(g_2)$ precisely when $g_1$ and $g_2$ lie in the same left coset of $H$ . In plain terms $f$ is constant on each coset and different across cosets, so $f$ hides $H$ inside its level sets. Your job is to expose $H$ — to output a generating set — with as few queries to $f$ and as few gates as possible. The reason this one problem matters is that so many famous algorithms are secretly the same algorithm. Take $G=(\mathbb{Z}_2)^n$ with $H$ of order two and you have Simon's problem. Take $G=\mathbb{Z}$ with $f(x)=a^x\bmod N$ and the hidden subgroup is $r\mathbb{Z}$ , where $r$ is the multiplicative order of $a$ — so HSP becomes order finding, and hence Shor's factoring. Discrete logarithm is HSP over $\mathbb{Z}_r\times\mathbb{Z}_r$ ; Deutsch–Jozsa and Bernstein–Vazirani are degenerate abelian cases. In every abelian instance the engine is identical: a single oracle call builds a coset state, the Quantum Fourier Transform over $G$ converts the coset's translational symmetry into a character orthogonal to $H$ , and a handful of such samples pins the subgroup down. The nonabelian version — dihedral, symmetric — is one of the great open problems of the field, tied to lattice cryptography and graph isomorphism. This article is the synthesis piece that its abelian children point back to.

Key takeaways

The Hidden Subgroup Problem: given $f:G\to S$ that is constant on cosets of an unknown $H\le G$ and distinct across them, output a generating set for $H$ .
Almost every structured exponential quantum speedup is an abelian HSP — Deutsch–Jozsa, Bernstein–Vazirani, Simon, order finding, period finding, and discrete logarithm all fit the one template.
The abelian recipe: one query prepares a coset state, the Quantum Fourier Transform over $G$ maps it onto the dual subgroup $H^{\perp}$ , and $O(\mathrm{poly}(\log|G|))$ samples plus linear algebra recover $H$ .
The duality is exact: $|H^{\perp}|=|G|/|H|$ and $(H^{\perp})^{\perp}=H$ , so measured characters annihilating $H$ can be inverted back to $H$ itself.
Nonabelian HSP is largely open — efficient algorithms exist only for special groups; the dihedral case reduces to worst-case lattice problems and the symmetric case to graph isomorphism.
The obstruction is that weak Fourier sampling over higher-dimensional irreducible representations cannot separate conjugate hidden subgroups, so the naive quantum approach provably loses information for $S_n$ and $D_n$ .
Key idea: a function constant on the cosets of a hidden subgroup encodes that subgroup's translational symmetry, and one query turns it into a coset state; for abelian $G$ the Fourier transform diagonalizes translations, so measuring returns a character trivial on $H$ — an element of the dual $H^{\perp}$ — and polynomially many such characters, dualized, reconstruct $H$ .

The core insight

A function that is constant on the cosets of a hidden subgroup encodes the subgroup's symmetry. Quantum mechanically you can produce, with one query, a uniform superposition over a single random coset — a coset state. For abelian $G$ the Fourier transform diagonalizes coset states, so measuring in the Fourier basis returns a character $\chi$ with $\chi(h)=1$ for every $h\in H$ , i.e. an element of the dual subgroup $H^{\perp}$ . Polynomially many such characters generate $H^{\perp}$ , and the duality $(H^{\perp})^{\perp}=H$ recovers $H$ . The whole speedup is the QFT turning translational coset symmetry into easily measured orthogonality.

Where this lives today

The abelian HSP is not a museum piece — it is the reason post-quantum cryptography exists as a field. Shor's factoring and discrete-logarithm algorithms, both abelian HSP instances, break RSA, Diffie–Hellman, and elliptic-curve cryptography once a fault-tolerant quantum computer runs them, which is exactly why NIST has standardized lattice-based replacements. And here the nonabelian HSP re-enters through the back door: Regev showed that an efficient dihedral HSP algorithm would solve the worst-case unique Shortest Vector Problem, the very hardness assumption those new lattice schemes rest on. So the open status of dihedral HSP is a live security question, and Kuperberg's subexponential $2^{O(\sqrt{\log N})}$ sieve — steadily refined for over a decade — sets the current benchmark that lattice parameters are chosen to stay ahead of. The symmetric-group case drives the other frontier: HSP over $S_n$ would place Graph Isomorphism in quantum polynomial time, a target that motivated a wave of "pretty good measurement" and multi-register sampling results before Babai's 2015 classical quasipolynomial algorithm reframed the whole question. Meanwhile small abelian instances run routinely on ion-trap, superconducting, and photonic hardware as compact demonstrations of coset-state preparation and Fourier sampling — the same skeleton, scaled down, that a cryptographically relevant Shor run will one day scale up.

The physical picture

Picture $f$ as a coloring of the group. Every element of a coset $gH$ is painted the same color, and different cosets get different colors — so the hidden subgroup is the shape of one color class, translated to sit over every element. Classically you only ever see the color at points you query, and you learn nothing about the shape until you blunder into two elements sharing a color; finding such a collision is the whole difficulty. Quantum mechanically you do something no classical machine can: you prepare an even superposition over an entire color class at once, with a single oracle call, and then read its symmetry off in one shot.

Figure

The hidden subgroup as a coloring of G = ℤ₈. The function f is constant on each coset of H = {0, 4} and distinct across cosets, so the 8 elements fall into 8/2 = 4 colored coset-pairs. Fourier sampling of a coset state returns only elements of the dual subgroup H⊥ = {0, 2, 4, 6}, whose order is 8/2 = 4

A coset state $|gH\rangle=\tfrac{1}{\sqrt{|H|}}\sum_{h\in H}|gh\rangle$ is nothing but a translate of $|H\rangle$ by the random offset $g$ . Translations are exactly what the Fourier transform diagonalizes — the convolution theorem — so in the Fourier basis the unknown $g$ becomes a harmless global phase and the surviving magnitude pattern picks out the dual subgroup $H^{\perp}$ , the frequencies on which $H$ is silent. That is the entire abelian mechanism: the QFT converts "constant under shifts by $H$ " into "supported on $H^{\perp}$ ", and the random coset never has to be identified. The map below is the punchline of the whole subject — where this clean story holds, and where it collapses.

Figure

The HSP landscape. Abelian instances are completely solved in time polynomial in log of the group order by coset-state preparation, the Fourier transform over G, and linear algebra — this branch contains Simon, Shor, and discrete log. The nonabelian branch is open: dihedral HSP reduces to worst-case lattice problems with only Kuperberg's subexponential 2^O(√log N) sieve known, and symmetric-group HSP would solve graph isomorphism

The abelian-versus-nonabelian divide is the divide between phases and matrices. For abelian $G$ every irreducible representation is one-dimensional — a character — so a Fourier measurement returns a clean group element of $H^{\perp}$ , one linear constraint on $H$ . For nonabelian $G$ the irreps have dimension greater than one, the Fourier transform of a coset state is a block-diagonal matrix, and reading only the block label throws away the intra-block information needed to separate hidden subgroups. Recovering $H$ then becomes solving a linear system whose constraints you can no longer cleanly measure — which is why "find $H^{\perp}$ , then dualize" works beautifully for Simon and Shor and stalls completely for the dihedral and symmetric groups.

The core equations

The whole problem lives in the promise on $f$ . It is a structural guarantee — not a value you can read at any single point, but a symmetry relating every colliding pair of inputs to the same hidden subgroup.

f:G\to S,\qquad f(g_1)=f(g_2)\iff g_1H=g_2H \qquad (1)

where: $G$ — the ambient group, finite or finitely generated; $H\le G$ — the hidden subgroup to be found; $g_iH$ — the left coset of $H$ containing $g_i$ ; $S$ — an arbitrary set of labels. Reading: $f$ is constant on each coset and injective across cosets, so its level sets are the cosets of $H$ . One oracle call, followed by discarding the answer register, leaves the input register in a uniform superposition over a single randomly chosen coset. This coset state is the object every downstream step manipulates.

|gH\rangle=\frac{1}{\sqrt{|H|}}\sum_{h\in H}|gh\rangle \qquad (2)

where: $g$ — a coset representative, drawn uniformly at random by the algorithm and never learned directly; $|H|$ — the order of the hidden subgroup. Reading: the state is a translate of $|H\rangle$ by the random offset $g$ , so all cosets look alike up to a shift. For abelian $G$ the irreducible representations are one-dimensional characters — phase functions indexed by elements of the dual group $\hat G$ , which is isomorphic to $G$ itself. These characters are the matrix entries of the Fourier transform.

\chi_y(x)=e^{2\pi i\,\langle y,x\rangle/|G|} \qquad (3)

where: $\chi_y$ — the character labeled by $y\in\hat G$ ; $\langle y,x\rangle$ — the pairing on $G\cong\hat G$ , e.g. $y\cdot x$ for $(\mathbb{Z}_2)^n$ ; $\hat G$ — the dual group. Reading: each character is a homomorphism, $\chi_y(x_1x_2)=\chi_y(x_1)\chi_y(x_2)$ , which is the single algebraic fact the algorithm exploits. The Quantum Fourier Transform over $G$ is the unitary whose rows are these characters. For the Boolean cube it is just a wall of Hadamards; over $\mathbb{Z}_N$ it is the familiar discrete Fourier transform.

\mathrm{QFT}_G\,|x\rangle=\frac{1}{\sqrt{|G|}}\sum_{y\in\hat G}\chi_y(x)\,|y\rangle \qquad (4)

where: $\mathrm{QFT}_G$ — the Fourier transform on the group algebra $\mathbb{C}[G]$ ; over $(\mathbb{Z}_2)^n$ it equals $H^{\otimes n}$ . Reading: "apply the QFT" and "Fourier-sample the hidden subgroup" are the same instruction. The dual, or orthogonal, subgroup collects exactly the characters that are blind to $H$ — trivial on every element of it. Its size is fixed by a clean counting identity.

H^{\perp}=\{y\in\hat G:\ \chi_y(h)=1\ \forall h\in H\},\qquad |H^{\perp}|=\frac{|G|}{|H|} \qquad (5)

where: $H^{\perp}$ — the annihilator of $H$ inside $\hat G$ . Reading: characters split into those constant on $H$ (which survive) and those that oscillate across it (which cancel); the former are precisely $H^{\perp}$ . Applying the QFT to a coset state and collecting terms leaves amplitude only on $H^{\perp}$ , each carrying an unobservable phase $\chi_y(g)$ from the random offset. This is the line the entire abelian theory turns on.

\mathrm{QFT}_G\,|gH\rangle=\sqrt{\frac{|H|}{|G|}}\sum_{y\in H^{\perp}}\chi_y(g)\,|y\rangle \qquad (6)

where: the sum runs only over $H^{\perp}$ ; the offset $g$ enters solely through the phase $\chi_y(g)$ . Reading: the random coset has been converted into a random dual element, with the offset demoted to invisible phase. Squaring the amplitudes gives the sampling law: a measurement returns a uniformly random member of $H^{\perp}$ and nothing else. Every run donates one such element — one linear constraint on $H$ .

\Pr[\text{measure }y]=\frac{1}{|H^{\perp}|}\ \ \text{for }y\in H^{\perp},\qquad 0\ \text{otherwise} \qquad (7)

where: $y$ — the sampled dual element; the phase $\chi_y(g)$ vanishes from the probability because $|\chi_y(g)|=1$ . Reading: the distribution depends on $H^{\perp}$ alone, never on the random offset, so the offset can never leak — and after $O(\log|G|)$ samples $H^{\perp}$ is generated and $H=(H^{\perp})^{\perp}$ is recovered by linear algebra.

Derivation ACoset state to a random dual element

The goal is to follow one abelian run from a coset state through the Fourier transform and prove that measurement yields a uniformly random element of the dual subgroup $H^{\perp}$ , with the random coset representative $g$ surviving only as an unobservable phase. This mechanism — a single character-orthogonality sum collapsing the support onto $H^{\perp}$ — is the reason every abelian HSP instance is efficient, so we track amplitudes explicitly rather than gesture at "interference", and we finish by inverting the duality to get $H$ itself.

Step 1. Start from the coset state $|gH\rangle=\tfrac{1}{\sqrt{|H|}}\sum_{h\in H}|gh\rangle$ and apply $\mathrm{QFT}_G$ , expanding each $|gh\rangle$ into the Fourier basis to reach $\tfrac{1}{\sqrt{|H||G|}}\sum_{h\in H}\sum_{y\in\hat G}\chi_y(gh)\,|y\rangle$ . Why: the Fourier transform is the natural basis for translations, so writing the coset in it is what will expose the hidden periodicity as a support condition.

Step 2. Use that characters are homomorphisms, $\chi_y(gh)=\chi_y(g)\chi_y(h)$ , and pull the offset phase $\chi_y(g)$ — which does not depend on $h$ — outside the inner sum, leaving $\tfrac{1}{\sqrt{|H||G|}}\sum_{y}\chi_y(g)\big(\sum_{h\in H}\chi_y(h)\big)|y\rangle$ . Why: separating $g$ from $h$ isolates all dependence on the random coset into a single scalar phase, which is what makes the offset ultimately invisible.

Step 3. Evaluate the inner character sum by orthogonality: $\sum_{h\in H}\chi_y(h)=|H|$ if $y\in H^{\perp}$ and $0$ otherwise, because $\chi_y$ restricted to $H$ is either the trivial character or a nontrivial one summing to zero. Substituting gives $\sqrt{|H|/|G|}\sum_{y\in H^{\perp}}\chi_y(g)\,|y\rangle$ , equation (6). Why: this is the decisive step — the coset symmetry cancels every frequency except those trivial on $H$ , so the support is exactly the dual subgroup.

Step 4. Take the modulus squared: each surviving $y$ has probability $|H|/|G|=1/|H^{\perp}|$ , independent of $g$ , so measurement returns a uniformly random $y\in H^{\perp}$ . Repeat to collect $y_1,\dots,y_k$ ; once they generate $H^{\perp}$ , solve the linear system $\{\chi_{y_i}(x)=1\}$ whose solution set is $(H^{\perp})^{\perp}=H$ . Why: the flat distribution means $O(\log|G|)$ samples suffice to generate $H^{\perp}$ , and the double-dual identity converts measured characters back into a generating set for the hidden subgroup. *Verified: for $G=(\mathbb{Z}_2)^n$ , $H=\{0,s\}$ gives $H^{\perp}=\{y:y\cdot s=0\}$ of size $2^{n-1}$ , and $n-1$ independent samples fix $s$ — exactly Simon's algorithm; the counting $|H^{\perp}|=|G|/|H|$ was checked for $G=\mathbb{Z}_8$ , $H=\{0,4\}$ , giving $H^{\perp}=\{0,2,4,6\}$ .*

Go deeper · Derivation B · 1 minOrder finding as the hidden subgroup problem over the integers

Derivation BOrder finding as the hidden subgroup problem over the integers

The goal is to show that finding the multiplicative order $r$ of $a$ modulo $N$ — the number-theoretic heart of Shor's factoring algorithm — is precisely the HSP with $G=\mathbb{Z}$ and $H=r\mathbb{Z}$ , and that the abelian recipe specializes to phase estimation on the modular-multiplication operator followed by continued fractions. We identify the hidden subgroup, handle the infinite group by truncation, and trace the Fourier peaks that reveal $r$ , so that "factoring" and "hidden period" become the same statement.

Step 1. Define $f(x)=a^x\bmod N$ on $x\in\mathbb{Z}$ . Then $f(x)=f(y)\iff a^{x-y}\equiv1\iff r\mid(x-y)$ , so $f$ is constant exactly on cosets of $H=\{x:a^x\equiv1\}=r\mathbb{Z}$ . Why: the level sets of modular exponentiation are the residue classes modulo $r$ , which is the definition of the subgroup $r\mathbb{Z}$ being hidden.

Step 2. Because $\mathbb{Z}$ is infinite, work over $\mathbb{Z}_M$ with $M=2^m\gg N^2$ , so a register of $m\approx 2\log N+O(1)$ qubits holds enough of $\mathbb{Z}$ that the truncation error is controlled. Why: the QFT needs a finite group, and choosing $M$ far larger than $r$ keeps the periodic structure from folding onto itself.

Step 3. Prepare the coset state $|x_0+r\mathbb{Z}\rangle$ and apply $\mathrm{QFT}_{\mathbb{Z}_M}$ ; the amplitude concentrates near integer multiples of $M/r$ , $\mathrm{QFT}_{\mathbb{Z}_M}|x_0+r\mathbb{Z}\rangle\approx\sum_j e^{2\pi i j x_0/M}\,|jM/r\rangle$ , the approximate dual of $r\mathbb{Z}$ . Why: the dual of a periodic subgroup is the set of matching frequencies, so Fourier sampling peaks at the reciprocal spacing $M/r$ — the analog of landing in $H^{\perp}$ .

Step 4. Measure a value close to $jM/r$ ; then $\text{measured}/M\approx j/r$ , and the continued-fraction algorithm extracts $r$ from a couple of samples. With $r$ in hand, if $r$ is even and $a^{r/2}\not\equiv-1$ , then $\gcd(a^{r/2}\pm1,N)$ splits $N$ . Why: continued fractions round a noisy rational to the true $j/r$ , replacing the linear algebra of the finite abelian case, and the gcd step is what turns period finding into factoring. *Verified: matches the order-finding circuit of Nielsen & Chuang §5.3.1 — register size $m\approx2\log N+O(1)$ , useful-measurement probability $\Theta(1/r^2)$ per peak summing to $\Theta(1)$ overall; for $a=7,N=15$ the order is $r=4$ and $\gcd(7^2\mp1,15)=\{3,5\}$ , checked directly.*

Go deeper · Derivation C · 1 minWhy nonabelian Fourier sampling can fail

Derivation CWhy nonabelian Fourier sampling can fail

The goal is to expose the obstruction that keeps the dihedral and symmetric hidden subgroup problems open: for nonabelian $G$ the Fourier transform of a coset state is a block-diagonal matrix over irreducible representations, and measuring only the block label — weak Fourier sampling — yields a distribution that cannot distinguish conjugate hidden subgroups. We decompose the averaged coset state, compute the weak-sampling distribution, and show it is identical for conjugate $H$ , so no post-processing of that data alone can succeed.

Step 1. For nonabelian $G$ the irreps $\sigma:G\to U(d_\sigma)$ generically have dimension $d_\sigma>1$ , so characters no longer label measurement outcomes uniquely; the averaged coset state becomes $\hat\rho_H=\bigoplus_{\sigma\in\hat G}\frac{d_\sigma}{|G|}\,\Pi_\sigma^H$ with $\Pi_\sigma^H=\frac{1}{|H|}\sum_{h\in H}\sigma(h)$ . Why: with higher-dimensional irreps the Fourier transform maps a coset state to a matrix, not a phase, so the clean single-element outcome of the abelian case is gone.

Step 2. Weak Fourier sampling measures only the irrep name $\sigma$ , giving $\Pr[\sigma]=\frac{d_\sigma}{|G|}\,\mathrm{rank}\,\Pi_\sigma^H=\frac{d_\sigma}{|G|}\,\dim(\sigma^H)$ , which depends only on the multiplicity of the trivial $H$ -subrepresentation inside $\sigma$ . Why: discarding the intra-block register keeps only how many $H$ -invariant directions each irrep contains, a coarse statistic.

Step 3. Conjugate subgroups $H_1=gH_2g^{-1}$ have $\sigma(H_1)$ and $\sigma(H_2)$ related by a change of basis, so $\dim(\sigma^{H_1})=\dim(\sigma^{H_2})$ and hence $\Pr[\sigma\mid H_1]=\Pr[\sigma\mid H_2]$ for every $\sigma$ . Why: the weak-sampling distribution is a conjugation invariant, so it literally cannot tell a hidden reflection in $D_n$ from any of its conjugates.

Step 4. Therefore weak sampling is information-theoretically insufficient for $D_n$ and $S_n$ ; one must perform strong sampling within each $d_\sigma$ -dimensional block, and no general efficient way to invert that data is known — Kuperberg's sieve reaches only $2^{O(\sqrt{\log N})}$ for the dihedral case. Why: the missing information sits inside the irrep blocks, and extracting $H$ from it efficiently is exactly the open problem tied to lattices and graph isomorphism. *Verified: consistent with Hallgren–Russell–Ta-Shma and Grigni et al. that weak Fourier sampling cannot solve $S_n$ or $D_n$ HSP, and with Kuperberg's subexponential dihedral sieve.*

Limiting cases

Specializing $G$ and $H$ recovers the textbook quantum algorithms and marks where the theory ends:

Case	Result	Meaning
$G=(\mathbb{Z}_2)^n,\ H=\{0,s\}$	$f(x)=f(y)\iff x\oplus y\in\{0,s\}$	Simon's problem: Fourier sampling returns $y$ with $y\cdot s=0$ ; $n-1$ independent samples fix $s$ .
$G=\mathbb{Z},\ H=r\mathbb{Z}$	$f(x)=a^x\bmod N,\ H=r\mathbb{Z}$	Order finding: the hidden period $r$ gives Shor's factoring via the QFT and continued fractions.
$G=\mathbb{Z}_r\times\mathbb{Z}_r$	$f(x,y)=g^x h^y,\ H=\langle(\ell,-1)\rangle$	Discrete logarithm $\ell=\log_g h$ is read off the slope of the hidden line $H$ .
$G=D_n$ (dihedral)	$H=\langle(d,1)\rangle$ (a reflection)	Nonabelian HSP equivalent (Regev) to worst-case lattice problems; only subexponential algorithms known (Kuperberg).
$G=S_n$ (symmetric)	$H\cong\{e\}$ or order two	HSP over $S_n$ solves Graph Isomorphism; weak Fourier sampling provably fails, no efficient algorithm known.

Common trapcheap coset states do not make the problem easy

The most common misconception is that HSP is solved the moment you can prepare coset states. It is not. Ettinger, Høyer, and Knill proved the query complexity is polynomial for every finite group — a polynomial number of coset-state copies information-theoretically determines $H$ — yet this says nothing about efficiency, because extracting $H$ from those copies can require an exponential-time measurement and classical post-processing. That gap is the whole difficulty of the nonabelian case. A second trap is to assume Fourier sampling always works: weak Fourier sampling measures only the irreducible-representation label and discards the register inside each block, and for groups like $S_n$ and $D_n$ this provably erases the information distinguishing conjugate hidden subgroups. Few queries plus a naive measurement is not an algorithm — you also need efficient post-processing, and for nonabelian $G$ that piece is missing.

Worked examples

1 · Abelian HSP over ℤ₈, fully worked

Take $G=\mathbb{Z}_8$ with hidden subgroup $H=\{0,4\}$ of order two. Suppose an oracle $f$ colors the group by coset. Walk through coset-state preparation, Fourier sampling, and the duality that recovers $H$ .

Step 1. List the cosets. Adding $H=\{0,4\}$ to each element pairs $i$ with $i+4$ , giving the four cosets $\{0,4\},\{1,5\},\{2,6\},\{3,7\}$ — count $|G|/|H|=8/2=\mathbf{4}$ , so $f$ takes exactly 4 distinct values. One query into an ancilla, then measuring the ancilla, collapses the input register onto one of these, say $\tfrac{1}{\sqrt2}(|2\rangle+|6\rangle)$ , a coset state with random offset $g=2$ .

Step 2. Identify the dual subgroup. A character $\chi_y(x)=e^{2\pi i\,yx/8}$ is trivial on $H$ when $\chi_y(4)=e^{2\pi i\,4y/8}=e^{\pi i y}=1$ , i.e. when $y$ is even. So $H^{\perp}=\{0,2,4,6\}$ , of size $|H^{\perp}|=|G|/|H|=\mathbf{4}$ , matching equation (5).

Step 3. Fourier-sample. Applying $\mathrm{QFT}_{\mathbb{Z}_8}$ to $\tfrac{1}{\sqrt2}(|2\rangle+|6\rangle)$ and squaring amplitudes gives probability $1/|H^{\perp}|=\mathbf{1/4}$ on each of $\{0,2,4,6\}$ and exactly zero on the odd elements — the offset $g=2$ contributes only the phase $e^{2\pi i\,2y/8}$ , which cancels in the probability. Each run therefore returns one uniformly random even number.

Step 4. Recover $H$ . Collect samples until they generate $H^{\perp}$ ; for instance $y_1=2$ and $y_2=6$ generate all of $\{0,2,4,6\}$ under addition mod 8. Now solve $\chi_y(x)=1$ for all sampled $y$ , i.e. $2x\equiv0$ and $6x\equiv0\pmod 8$ : both force $x\in\{0,4\}$ . The double dual $(H^{\perp})^{\perp}=\mathbf{\{0,4\}}=H$ is exactly the hidden subgroup, recovered from two informative measurements plus a line of modular arithmetic. H = {0, 4}, obtained from H⊥ = {0, 2, 4, 6} by dualizing.

2 · Order finding as HSP: factoring 15, fully worked

Use the HSP-over- $\mathbb{Z}$ picture to factor $N=15$ with base $a=7$ . Find the hidden subgroup, the period, and the factors.

Step 1. The oracle is $f(x)=7^x\bmod 15$ . Tabulate: $7^1=7,\ 7^2=49\equiv\mathbf{4},\ 7^3\equiv13,\ 7^4\equiv\mathbf{1}\pmod{15}$ . The values repeat with period 4, so $f(x)=f(y)\iff 4\mid(x-y)$ and the hidden subgroup is $H=4\mathbb{Z}$ .

Step 2. Read off the period. The smallest positive $x$ with $7^x\equiv1$ is $x=\mathbf{4}$ , so the multiplicative order is $r=4$ ; the quantum part (phase estimation on $U_7:|z\rangle\mapsto|7z\bmod15\rangle$ , then continued fractions on a measured $j/r$ ) delivers exactly this $r$ . Here $r=\mathbf{4}$ is even — the good case.

Step 3. Split $N$ . Compute $a^{r/2}=7^{2}=49\equiv\mathbf{4}\pmod{15}$ , and check $4\not\equiv-1\equiv14$ , so the case is nondegenerate. Then $\gcd(a^{r/2}-1,N)=\gcd(3,15)=\mathbf{3}$ and $\gcd(a^{r/2}+1,N)=\gcd(5,15)=\mathbf{5}$ .

Step 4. Conclude. The nontrivial factors are $\mathbf{3}$ and $\mathbf{5}$ , and indeed $3\times5=15$ . A single abelian HSP instance — hidden subgroup $4\mathbb{Z}$ inside $\mathbb{Z}$ — has factored the modulus. Factoring 15 with a = 7 reduces to finding H = 4ℤ, giving r = 4 and the factors 3 and 5.

Physics of the portrait

The Hidden Subgroup Problem is a piece of theoretical computer science, but it belongs in a physics-flavored quantum course because it is where the mechanism of quantum advantage becomes visible: symmetry, encoded by a group, read out by a Fourier transform. The person who first saw that the disparate 1994 breakthroughs were one problem, and who supplied the tool that solves the whole abelian family, was Alexei Kitaev.

Origins · 1 minAlexei Kitaev and how this was discovered

Alexei Kitaev

b. 1963; Landau Institute, Caltech, Microsoft Station Q · phase estimation and the abelian stabilizer/hidden subgroup problem

Alexei Kitaev is one of the rare physicists who reshaped both quantum computing and condensed-matter theory. In 1995, months after Shor and Simon, his paper Quantum Measurements and the Abelian Stabilizer Problem introduced quantum phase estimation — the routine for reading an eigenphase of a unitary to many bits — and used it to solve the abelian stabilizer problem, which is the hidden subgroup problem for finite abelian groups stated in the language of group actions and eigenvalues. This unified Shor's factoring and discrete logarithm and Simon's period finding as a single algorithm: prepare a coset state, apply the Fourier transform over the group, sample the dual, and dualize back. Phase estimation is now the backbone of Shor's algorithm, quantum chemistry simulation, and the amplitude-estimation family, and it is how most textbooks actually derive order finding. Kitaev's reach did not stop there — he went on to invent the toric code and the theory of topological quantum computation with anyons, the Kitaev chain and its Majorana modes, and later the Sachdev–Ye–Kitaev model connecting quantum chaos to black-hole physics. But within the story of this article his decisive contribution is the recognition that a symmetry hidden in a function's level sets can be estimated as a phase, turning the scattered quantum speedups of 1994 into instances of one clean problem.

History

1994

— Simon's hidden-XOR period and Shor's period finding reveal a shared template

1995

— Kitaev solves the Abelian Stabilizer Problem with phase estimation

1998

— Mosca and Ekert frame the general hidden subgroup problem over finite groups

2004

— Regev reduces the dihedral HSP to worst-case lattice problems

2004

— Ettinger, Høyer and Knill prove HSP query complexity is polynomial for all groups

Going further

Texts. Nielsen & Chuang, Quantum Computation and Quantum Information (10th anniversary ed.), §5.4 (quantum Fourier transform and applications; hidden subgroup discussion) and §5.3 (order finding) · Preskill, Lecture Notes for Physics 219, Chapter 6 (quantum algorithms; period finding and HSP) · Watrous, The Theory of Quantum Information (Fourier analysis over groups) · Kitaev, Shen, Vyalyi, Classical and Quantum Computation (the abelian stabilizer / hidden subgroup problem) · Childs & van Dam, Quantum algorithms for algebraic problems, Rev. Mod. Phys. 82, 1 (2010) · A. Kitaev, Quantum Measurements and the Abelian Stabilizer Problem (1995) · Ettinger, Høyer, Knill, The quantum query complexity of the hidden subgroup problem is polynomial (2004) · Regev, Quantum computation and lattice problems (2004) · Kuperberg, A subexponential-time quantum algorithm for the dihedral hidden subgroup problem (2005).

Provenance. The coset-state-to-dual mechanism (equations 2–7) is recomputable from $\mathrm{QFT}_G$ and the character-orthogonality sum $\sum_{h\in H}\chi_y(h)=|H|\,[y\in H^{\perp}]$ ; cross-check against Nielsen & Chuang §5.4 and Watrous's Fourier chapter. The duality $|H^{\perp}|=|G|/|H|$ and $(H^{\perp})^{\perp}=H$ follow from finite-abelian-group theory and were checked numerically for $G=\mathbb{Z}_8$ , $H=\{0,4\}$ giving $H^{\perp}=\{0,2,4,6\}$ . Order-finding sizing ( $m\approx2\log N$ , success $\Theta(1/r^2)$ per peak) is Nielsen & Chuang §5.3.1; the factoring example ( $a=7,N=15\Rightarrow r=4$ , factors 3 and 5) was verified directly. The nonabelian weak-sampling obstruction follows Hallgren–Russell–Ta-Shma and Grigni et al.; the dihedral–lattice reduction is Regev (2004) and the subexponential sieve is Kuperberg (2005). No nonstandard numerical claims are made.

Prerequisites. Quantum Fourier Transform · Simon's Algorithm · Quantum Parallelism and the Oracle Model · Quantum Phase Estimation. Leads to. Shor's Factoring Algorithm · Quantum Discrete Logarithm Algorithm · Order Finding and Period Finding · Bernstein–Vazirani Algorithm.

Ask the tutor: Ask me to run the ℤ₈ hidden-subgroup example end to end — coset state, Fourier sampling of H⊥, and the dualization back to H — or to show exactly how the abelian recipe becomes Shor's order finding.

What exactly is a coset state, and why is it the right object?

A coset state $|gH\rangle=\tfrac{1}{\sqrt{|H|}}\sum_{h\in H}|gh\rangle$ is a uniform superposition over one left coset of the hidden subgroup, produced by evaluating $f$ into an ancilla and then discarding the ancilla — which projects the input register onto whichever coset shares the measured function value. It is the right object because it carries the hidden subgroup's symmetry while hiding the random coset representative $g$ : shifting every label by an element of $H$ leaves the state unchanged. That translational invariance is precisely what the Fourier transform is built to detect, so the coset state is the bridge between " $f$ hides $H$ " and "measurement reveals $H^{\perp}$ ".

Why does the random coset representative g never leak?

Because $g$ enters the post-Fourier state only through the phase factor $\chi_y(g)$ multiplying each amplitude, and phases of modulus one vanish when you compute a probability. The measurement probability of outcome $y$ is $|\chi_y(g)|^2/|H^{\perp}|=1/|H^{\perp}|$ , completely independent of $g$ . So although each run uses a fresh random offset, the outcome distribution depends only on the dual subgroup $H^{\perp}$ . This is a feature, not a bug: you do not want to learn $g$ — you want $H$ — and the algorithm automatically discards the irrelevant offset while keeping the relevant symmetry.

How is the Hidden Subgroup Problem related to Shor's algorithm?

Shor's algorithm is the HSP with $G=\mathbb{Z}$ and $f(x)=a^x\bmod N$ , whose hidden subgroup is $r\mathbb{Z}$ for the multiplicative order $r$ of $a$ . The general abelian recipe — coset state, Fourier transform over the group, sample the dual, post-process — specializes to Shor's circuit with the QFT over $\mathbb{Z}_M$ playing the role of the group Fourier transform and continued fractions replacing the linear algebra used in the finite case. Once you have $r$ , the classical reduction $\gcd(a^{r/2}\pm1,N)$ turns period finding into factoring. So Shor is not a separate trick; it is the single most consequential instance of one general template.

What makes the nonabelian case so much harder than the abelian one?

For abelian groups every irreducible representation is one-dimensional — a character — so a Fourier measurement returns a single group element of $H^{\perp}$ , a clean linear constraint you can accumulate and solve. For nonabelian groups the irreps have dimension greater than one, and the Fourier transform of a coset state is a block-diagonal matrix. Measuring only the block label (weak Fourier sampling) provably cannot distinguish conjugate hidden subgroups, while measuring inside the blocks (strong sampling) keeps the needed information but leaves you with no general efficient way to extract $H$ . The information can even be there in polynomially many copies, yet require an exponential-time measurement to use — which is the crux of why dihedral and symmetric HSP remain open.

If the query complexity is polynomial, why isn't the problem solved?

Ettinger, Høyer, and Knill proved that for every finite group, polynomially many coset-state copies contain enough information, in principle, to determine $H$ . But "the information is present" and "you can extract it efficiently" are different statements. The optimal measurement that would read $H$ off those copies may itself take exponential time to implement, and the subsequent classical post-processing may be intractable. Efficiency demands both few queries and a polynomial-time procedure to identify $H$ from the measurement results, and it is the second requirement that fails for groups like $S_n$ and $D_n$ . Polynomial query complexity is a lower bound on hope, not a proof of an algorithm.

Why does the Hidden Subgroup Problem matter for cryptography?

Two ways, pointing in opposite directions. The abelian case is a threat: Shor's factoring and discrete-logarithm algorithms are abelian HSP instances, and they break RSA, Diffie–Hellman, and elliptic-curve schemes on a fault-tolerant quantum computer. The nonabelian case is a safeguard under suspicion: Regev showed that an efficient dihedral HSP algorithm would solve worst-case lattice problems, which are exactly the hardness assumptions underpinning most post-quantum cryptography. So the boundary between the solved abelian world and the open nonabelian world is also the boundary between "already broken" and "believed safe", and Kuperberg's subexponential dihedral sieve is the benchmark that lattice parameter choices must stay ahead of.