Difference between revisions of "Hidden Subgroup Zoo"
From Quantum Computing Theory Group
Line 1: | Line 1: | ||
'''Hidden Subgroup Problem''' (HSP) | '''Hidden Subgroup Problem''' (HSP) | ||
− | Given: <math>f</math>, a function from a group <math>G</math> to a set <math>S</math> which is promised to be constant and distinct on different left cosets of an unknown subgroup <math>H</math>: | + | ''Given:'' <math>f</math>, a function from a group <math>G</math> to a set <math>S</math> which is promised to be constant and distinct on different left cosets of an unknown subgroup <math>H</math>: |
<center><math>f:H \rightarrow S</math> <math>f(g)=f(h)</math> iff <math>gH = gH</math></center> | <center><math>f:H \rightarrow S</math> <math>f(g)=f(h)</math> iff <math>gH = gH</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> |
Revision as of 00:46, 13 June 2008
Hidden Subgroup Problem (HSP)
Given: <math>f</math>, a function from a group <math>G</math> to a set <math>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>