Explicit examples of oracle in Dihedral Hidden Subgroup Problem

36 Views Asked by At

In the general hidden subgroup problem we are given a generating set of a group $G$ (not necessarily abelian), we are given access to a function $f:G\to\mathbb{C}$, such that there is an unknown subgroup $H<G$, where $f$ is constant on every left coset of $H$.

In other words $\forall g\in G \ \forall g_1,g_2\in gH:f(g_1)=f(g_2)$ and $\forall h\in H:f(h)=0$, the latter is for simplicity, and can be replaced by $1$ etc.

The goal is to find a generating set for $H$ with few possible queries to $f$.

I am looking for explicit examples of coset separating functions for the case where $G=D_n$ for general odd $n$ and when $H$ is some subgroup.