Hidden Subgroup Zoo

From Quantum Computing Theory Group
Jump to: navigation, search

The Problem

Hidden Subgroup Problem (HSP)

Given: A function <math>f</math> from a group <math>G</math> to a set <math>S</math>, <math>f:G \rightarrow S</math> which is promised to be constant and distinct on different left cosets of an unknown subgroup <math>H</math>:

<math>f(g_1)=f(g_2)~{\rm iff}~g_1H = g_2H</math>

Problem: Find the hidden subgroup <math>H</math> by returning a set of generators for <math>H</math>

An algorithm for the hidden subgroup problem is efficient if the algorithm runs in a time polynomial in the logarithm of the size of the group (for infinite groups the definition is more subtle.)

Groups Which Admit an Efficient Algorithm

Finite Abelian Groups

Normal Subgroups

Near Abelian Groups

Near Hamiltonian Groups

Semidirect Products of Abelian Groups

Extraspecial Groups and Nil-2 Groups

Solvable Groups of Bounded Exponent and of Bounded Derived Series

Groups with Small Commutator Subgroup

Groups with an Elementary Abelian Normal 2-Subgroup of Small Index or with Cyclic Factor Group

Groups Which Admit an Subexponential Time Algorithm

Dihedral Group

Generalized Simon's Algorithm Groups

Existential Results