Difference between revisions of "Hidden Subgroup Zoo"
From Quantum Computing Theory Group
(→The Problem) |
|||
(13 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
+ | == The Problem == | ||
+ | |||
'''Hidden Subgroup Problem''' (HSP) | '''Hidden Subgroup Problem''' (HSP) | ||
− | ''Given:'' <math>f</math> | + | ''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>: |
− | <center><math> | + | <center><math>f(g_1)=f(g_2)~{\rm iff}~g_1H = g_2H</math></center> |
− | ''Problem:'' Find the hidden subgroup | + | ''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 == |
Latest revision as of 18:36, 4 August 2008
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.)