# Hidden Subgroup Zoo

## The Problem

Hidden Subgroup Problem (HSP)

Given: A function $f$ from a group $G$ to a set $S$, $f:G \rightarrow S$ which is promised to be constant and distinct on different left cosets of an unknown subgroup $H$:

$f(g_1)=f(g_2)~{\rm iff}~g_1H = g_2H$

Problem: Find the hidden subgroup $H$ by returning a set of generators for $H$

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.)