Difference between revisions of "Hidden Subgroup Zoo"
From Quantum Computing Theory Group
| Line 5: | Line 5: | ||
''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>: | ''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>f(g_1)=f(g_2)~{\rm iff}~g_1H = g_2H</math></center> | <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=== | ||
Revision as of 18:02, 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.
