Simon's Problem as hidden subgroup
Anders B Madsen 01 Mar 2023 15:50
Given a 2-1 function $f$ satisfying $f(x) = f(x \oplus a)$ for all $x \in \mathbb{Z}_{2}^n$, Simon's Problem is to find the bitstring $a \in \mathbb{Z}_{2}^n$.
The group is $G = \mathbb{Z}_{2} \times \ldots \times \mathbb{Z}_{2}$ and the hidden subgroup is simply the 2-element group generated by $a$:
\begin{align} H = \langle a \rangle = \{0, a\}\,. \end{align}
For all $x \in \mathbb{Z}_{2}^n$, $f$ is then constant on the coset
(2)\begin{align} x + H = \{x, x \oplus a\}\,, \end{align}
and finding the generator of $H$ produces $a$.