Simon's problem
= Simon's problem
{c}
{wiki=Simon's_problem}
Simon's problem asks for the hidden string $p\in\{0,1\}^n$ promised by $f(x)=f(y)$ exactly when $x\mathbin\oplus y\in\{0^n,p\}$. It is the <hidden subgroup problem> on $(\mathbb Z_2)^n$ with hidden subgroup $\{0^n,p\}$.