Difference between revisions of "Hidden Subgroup Zoo"
From Quantum Computing Theory Group
Line 21: | Line 21: | ||
===Semidirect Products of Abelian 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=== |
Revision as of 18:30, 17 June 2008
Contents
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.