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 hides the subgroup H if for all g1, g2 ∈ G, f(g1) = f(g2) if and only if g1H = g2H for the cosets of H. Equivalently, the function 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 → X a function that hides a subgroup H ≤ 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.[1] An efficient quantum algorithm for the HSP for the dihedral group would give a quantum algorithm for the poly(n) unique SVP [2].
Algorithms
There is a polynomial time quantum algorithm for solving HSP over finite 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 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 (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).
References
- ^ Mark Ettinger; Peter Høyer. "A quantum observable for the graph isomorphism problem". arXiv:quant-ph/9901029.
- ^ Oded Regev. "Quantum computation and lattice problems". arXiv:cs/0304005.