# Hidden Subgroup Zoo

From Quantum Computing Theory Group

## Contents

- 1 The Problem
- 2 Groups Which Admit an Efficient Algorithm
- 2.1 Finite Abelian Groups
- 2.2 Normal Subgroups
- 2.3 Near Abelian Groups
- 2.4 Near Hamiltonian Groups
- 2.5 Semidirect Products of Abelian Groups
- 2.6 Extraspecial Groups and Nil-2 Groups
- 2.7 Solvable Groups of Bounded Exponent and of Bounded Derived Series
- 2.8 Groups with Small Commutator Subgroup
- 2.9 Groups with an Elementary Abelian Normal 2-Subgroup of Small Index or with Cyclic Factor Group

- 3 Groups Which Admit an Subexponential Time Algorithm
- 4 Existential Results

## 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>:

*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.)