Hidden subgroup problem (HSP) is a class of problems that provides a unified framework for many quantum algorithms. The problem is: given a group $G$, a set $X$, and a function $f: G \to X$ that is constant on cosets of some subgroup $H \leq G$ and takes distinct values on different cosets, find the hidden subgroup $H$.

Many famous quantum algorithms can be cast as instances of the HSP. Deutsch's algorithm solves HSP over $\mathbb{Z}_2$. The Bernstein-Vazirani algorithm solves HSP over $\mathbb{Z}_2^n$. Shor's order-finding algorithm solves HSP over $\mathbb{Z}$ (or finite cyclic groups $\mathbb{Z}_N$). The quantum Fourier transform over the group $G$ is the key quantum tool for solving the abelian HSP.

The abelian HSP — where $G$ is abelian — is efficiently solvable by quantum computers. The algorithm queries the oracle to prepare a coset state $\frac{1}{\sqrt{|H|}}\sum_{h\in H}\lvert x_0 h\rangle$ for a random coset representative $x_0$, then applies the QFT over $G$, and measures to obtain a character of $G$ that is orthogonal to $H$. Repeating $O(\log|G|)$ times yields enough information to identify $H$ via classical post-processing.

The non-abelian HSP — where $G$ is non-abelian — is not known to be efficiently solvable in general. Solving the HSP over the symmetric group $S_n$ would yield an efficient quantum algorithm for graph isomorphism. Solving it over the dihedral group $D_n$ would yield an efficient algorithm for the shortest vector problem in lattices. Both remain open problems and are important targets for future quantum algorithms.