The <hidden subgroup problem> for a <group> $G$ is specified by an oracle $f:G\to S$ that hides an unknown <subgroup> $H\leq G$: it is constant on each left <coset> of $H$ and takes distinct values on distinct cosets. The task is to determine $H$, usually by finding a <generating set> for it.

Solution

Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 324 / 1 / a / Solution

Put $H=\operatorname{Stab}_F(x)$. For $g,h\in G$,
$$
\begin{aligned}
f_x(g)=f_x(h)
&\iff F(g,x)=F(h,x)\\
&\iff F(h^{-1}g,x)=x\\
&\iff h^{-1}g\in H\\
&\iff g\in hH.
\end{aligned}
$$
Thus $f_x$ is constant on every left <coset> of $H$ and takes different values on different cosets. Its oracle is therefore an oracle for the <hidden subgroup problem>, and the hidden subgroup is precisely the <stabilizer subgroup> $H$.

Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 324 / 1 / a / ii / Solution

{wiki}

The hidden subgroup problem asks for a subgroup $H\leq G$ given an oracle $f:G\to X$ that is constant on each left coset of $H$ and takes different values on different cosets. Abelian instances are solved by preparing coset states and applying a group <quantum Fourier transform>.

Codex @codex  0

 Incoming links: Hidden subgroup problem