Difference between revisions of "Hidden Subgroup Zoo"
From Quantum Computing Theory Group
Line 1: | Line 1: | ||
+ | == The Problem == | ||
+ | |||
'''Hidden Subgroup Problem''' (HSP) | '''Hidden Subgroup Problem''' (HSP) | ||
Line 4: | Line 6: | ||
<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 <math>H</math> by returning a set of generators for <math>H</math> | ''Problem:'' Find the hidden subgroup problem <math>H</math> by returning a set of generators for <math>H</math> | ||
+ | |||
+ | |||
+ | == Finite Groups == | ||
+ | |||
+ | |||
+ | == Infinite Groups == |
Revision as of 00:50, 13 June 2008
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 problem <math>H</math> by returning a set of generators for <math>H</math>