The hidden subgroup problem (HSP) is a topic of research in mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

 and theoretical computer science

Theoretical computer science

Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....

.

Problem statement

Given a group

Group (mathematics)

In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...

 G, a subgroup

Subgroup

In group theory, given a group G under a binary operation *, a subset H of G is called a subgroup of G if H also forms a group under the operation *. More precisely, H is a subgroup of G if the restriction of * to H x H is a group operation on H...

 H ≤ G, and a set X, we say a function f : G → X hides the subgroup H if for all g₁, g₂ ∈ G,
f(g₁) = f(g₂) if and only if g₁H = g₂H for the cosets

Coset

In mathematics, if G is a group, and H is a subgroup of G, and g is an element of G, thenA coset is a left or right coset of some subgroup in G...

 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

Oracle machine

In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any...

. 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

Group homomorphism

In mathematics, given two groups and , a group homomorphism from to is a function h : G → H such that for all u and v in G it holds that h = h \cdot h...

 in which case H corresponds to the kernel

Kernel (algebra)

In the various branches of mathematics that fall under the heading of abstract algebra, the kernel of a homomorphism measures the degree to which the homomorphism fails to be injective. An important special case is the kernel of a matrix, also called the null space.The definition of kernel takes...

 of f.

Motivation

The Hidden Subgroup Problem is especially important in the theory of quantum computing

Quantum computer

A quantum computer is a device for computation that makes direct use of quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data. Quantum computers are different from traditional computers based on transistors...

 for the following reasons.

• Shor's quantum algorithm
  Shor's algorithm
  Shor's algorithm, named after mathematician Peter Shor, is a quantum algorithm for integer factorization formulated in 1994...
  
   for factoring and discrete logarithm
  Discrete logarithm
  In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga is a solution of the equation ax = b over the real or complex numbers...
  
   (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
  Graph isomorphism problem
  The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.Besides its practical importance, the graph isomorphism problem is a curiosity in computational complexity theory as it is one of a very small number of problems belonging to NP...
  
   and certain shortest vector problems (SVPs) in lattices. More precisely, an efficient quantum algorithm for the HSP for the symmetric group
  Symmetric group
  In mathematics, the symmetric group Sn on a finite set of n symbols is the group whose elements are all the permutations of the n symbols, and whose group operation is the composition of such permutations, which are treated as bijective functions from the set of symbols to itself...
  
   would give a quantum algorithm for the graph isomorphism. An efficient quantum algorithm for the HSP for the dihedral group
  Dihedral group
  In mathematics, a dihedral group is the group of symmetries of a regular polygon, including both rotations and reflections. Dihedral groups are among the simplest examples of finite groups, and they play an important role in group theory, geometry, and chemistry.See also: Dihedral symmetry in three...
  
   would give a quantum algorithm for the poly(n) unique SVP .

Algorithms

There is a polynomial time quantum algorithm for solving HSP over Abelian group

Abelian group

In abstract algebra, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on their order . Abelian groups generalize the arithmetic of addition of integers...

s. (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 group

Abelian group

In abstract algebra, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on their order . Abelian groups generalize the arithmetic of addition of integers...

s.

Most current approaches to this problem involve partial measurement after a Quantum Fourier transform

Quantum Fourier transform

In quantum computing, the quantum Fourier transform is a linear transformation on quantum bits, and is the quantum analogue of the discrete 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

• 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