The hidden subgroup problem (HSP) is a topic of research in mathematics and theoretical computer science.
The framework captures problems such as factoring, discrete logarithm, graph isomorphism, and the shortest vector problem.
This makes it especially important in the theory of quantum computing because Shor's algorithms for factoring and finding discrete logarithms in quantum computing are instances of the hidden subgroup problem for finite abelian groups, while the other problems correspond to finite groups that are not abelian.
a function that hides a subgroup
Using information gained from evaluations of
via its oracle, determine a generating set for
is a group homomorphism in which case
The hidden subgroup problem is especially important in the theory of quantum computing for the following reasons.
There is an efficient quantum algorithm for solving HSP over finite abelian groups in time polynomial in
For arbitrary groups, it is known that the hidden subgroup problem is solvable using a polynomial number of evaluations of the oracle.
, making the algorithm not efficient overall; efficient algorithms must be polynomial in the number of oracle evaluations and running time.
The existence of such an algorithm for arbitrary groups is open.
Quantum polynomial time algorithms exist for certain subclasses of groups, such as semi-direct products of some abelian groups.
The algorithm for abelian groups uses representations, i.e. homomorphisms from
, the general linear group over the complex numbers.
For an abelian group, all the irreducible representations are the characters, which are the representations of dimension one; there are no irreducible representations of larger dimension for abelian groups.
The quantum fourier transform can be defined in terms of
, the additive cyclic group of order
the quantum fourier transform has the definition of
Any finite abelian group can be written as the direct product of multiple cyclic groups
On a quantum computer, this is represented as the tensor product of multiple registers of dimensions
called the dual group of
For each iteration of the algorithm, the quantum circuit outputs an element
form an orthonormal basis:
be the trivial representation, which maps all inputs to
Each measurement of the final state will result in some information gained about
, will be found after a polynomial number of measurements.
The size of the subgroup generated by
Many algorithms where quantum speedups occur in quantum computing are instances of the hidden subgroup problem.
The following list outlines important instances of the HSP, and whether or not they are solvable.