Hidden Subgroup Problem

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 quantum algorithm for factoring is an instance of the hidden subgroup problem for finite Abelian groups, while the other problems correspond to finite groups that are not Abelian.

Problem statement

Given a group $G$, a subgroup $H \leq G$, and a set $X$, we say a function $f : G \to X$ hides the subgroup $H$ if for all $g_1 g_2 \in G, f(g_1) = f(g_2)$ if and only if $g_1 H = g_2 H$. Equivalently, $f$ is constant on the cosets of ''H'', while it is different between the different cosets of ''H''.

Hidden subgroup problem: Let $G$ be a group, $X$ a finite set, and $f : G \to X$ a function that hides a subgroup $H \leq G$. The function $f$ is given via an oracle, which uses $O(\log , G, + \log , X, )$ bits. Using information gained from evaluations of $f$ via its oracle, determine a generating set for $H$.

A special case is when $X$ is a group and $f$ is a group homomorphism in which case $H$ corresponds to the kernel of $f$.

Motivation

The hidden subgroup problem is especially important in the theory of quantum computing for the following reasons.

* Shor's quantum algorithm for factoring and discrete logarithm (as well as several of its extensions) relies on the ability of quantum computers to solve the HSP for finite Abelian groups.
* The existence of efficient quantum algorithms for HSPs for certain non-Abelian groups would imply efficient quantum algorithms for two major problems: the graph isomorphism problem and certain shortest vector problems (SVPs) in lattices. More precisely, an efficient quantum algorithm for the HSP for the symmetric group would give a quantum algorithm for the graph isomorphism. An efficient quantum algorithm for the HSP for the dihedral group would give a quantum algorithm for the $\operatorname(n)$ unique SVP.

Algorithms

There is a efficient quantum algorithm for solving HSP over finite Abelian groups in time polynomial in $\log, G,$. Shor's algorithm applies a particular case of this quantum algorithm.

For arbitrary groups, it is known that the hidden subgroup problem is solvable using a polynomial number of evaluations of the oracle. However, the circuits that implement this may be exponential in $\log, G,$, making the algorithm overall not efficient; 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.

To solve the problem for finite Abelian groups, the 'standard' approach to this problem involves: the creation of the quantum state $\frac\sum_$, a subsequent quantum Fourier transform to the left register, after which this register gets sampled. This approach has been shown to be insufficient for the hidden subgroup problem for the symmetric group.{{cite arXiv, eprint=quant-ph/0501056, author=Cristopher Moore, Alexander Russell, Leonard J. Schulman, title=The Symmetric Group Defies Strong Fourier Sampling: Part I, year=2005

See also

* Dual group (Quantum Computing)
* Hidden shift problem

References

External links

Richard Jozsa: Quantum factoring, discrete logarithms and the hidden subgroup problem

Chris Lomont: The Hidden Subgroup Problem - Review and Open Problems

Hidden subgroup problem on arxiv.org

Group theory
Quantum algorithms