Hidden subgroup problem

The hidden subgroup problem (HSP) is a topic of research in mathematics and theoretical computer science.

Problem statement

Given a group "G", a subgroup "H" ≤ "G", and a set "X", we say a function "f" : "G" → "X" separates cosets of "H" if for all "g"₁, "g"₂ ∈ "G","f"("g"₁) = "f"("g"₂) if and only if "g"₁"H" = "g"₂"H".

Hidden subgroup problem: Let "G" be a group, "X" a finite set, and "f" : "G" → "X" a function such that there exists a subgroup "H" ≤ "G" for which "f" separates cosets of "H". The function "f" is given via an oracle. Using information gained from evaluations of "f" via its oracle, determine a generating set for "H".

Motivation

The importance of this problem is due to two facts:

* Shor's quantum algorithm for factoring and discrete logarithm (as well as several of its extensions) is a special case of HSP;
* Designing an efficient quantum algorithm for HSP for arbitrary groups would result in 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 HSP for the symmetric group would give a quantum algorithm for the graph isomorphism. An efficient quantum algorithm for HSP for the dihedral group would give a quantum algorithm for the poly(n) unique SVP (Aharonov, Regev).)

Algorithms

There is a polynomial time quantum algorithm for solving HSP over Abelian groups. (In the case of hidden subgroup problem,"a polynomial time algorithm" means an algorithm whose running time is a polynomial of the logarithm of the size of the group.) Shor's algorithm is one 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 (Ettinger, Hoyer and Knill), if the running time (including non-oracle operations) can be exponential. However, to design efficient algorithms for the graph isomorphism and SVP, one needs an algorithm for which both the number of oracle evaluations and the running time are polynomial.

The existence of such 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.

Most current approaches to this problem involve partial measurement after a quantum Fourier transform. This approach has been shown to be insufficient for the hidden subgroup problem for the symmetric group (Hallgren, Moore, Roetller, Russell, and Sen).

External links

* [http://arxiv.org/abs/quant-ph/0012084 Richard Jozsa: Quantum factoring, discrete logarithms and the hidden subgroup problem]
* [http://arxiv.org/abs/quant-ph/0411037 Chris Lomont: The Hidden Subgroup Problem - Review and Open Problems]
* [http://xstructure.inr.ac.ru/x-bin/theme2.py?arxiv=quant-ph&level=1&index1=14486 Hidden subgroup problem on arxiv.org]