Hidden subgroup problem
From Wikipedia, the free encyclopedia
The hidden subgroup problem (HSP) is a topic of research in mathematics and theoretical computer science.
Contents |
[edit] 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 g1, g2 ∈ G, f(g1) = f(g2) if and only if g1H = g2H.
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.
[edit] 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).)
[edit] 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 (Moore, Russell, Schulman).
