5
$\begingroup$

Given access to an oracle for a function $f:\{0,1\}^n\to\{0,1\}^n$ such that $f(x)=f(y)$ iff $x\oplus y\in\{0,s\}$, Simon's algorithm allows to recover $s$ in $\mathcal O(n)$ queries to the oracle.

The Wikipedia page also mentions how Simon's problem is a special case of the more general Abelian hidden subgroup problem, which concerns, given a function $f:G\to X$ with $G$ group, finding the normal subgroup $H\triangleleft G$ such that $f(x)=f(y)$ iff there is some $g\in G$ such that $x,y\in gH$ (with $gH$ denoting the left coset of $H$ by $g$).

While I can see the similarity between the two definitions, many online sources do not explicitly spell it out, hence my asking here: what is the normal subgroup that is hidden in Simon's problem?

$\endgroup$
4
$\begingroup$

To see that Simon's program is an instance of an (abelian) hidden subgroup problem, we have to identify the group $G$, the subgroup $H$, the set $X$ and the function $f : G \rightarrow X$. Note first that the set $\{ 0,1 \}^n$ of all bit vectors of length $n$ naturally comes with a group structure given by the (component-wise) XOR between bit vectors: $(x_1, \ldots, x_n) \oplus (y_1, \ldots, y_n) := (x_1 \oplus y_1, \ldots, x_n \oplus y_n)$. Using this definition of the group law, $\{0,1\}^n$ becomes an abelian (i.e., commutative) group $G$. Any set $S$ of bit vectors generates a subgroup of $G$. If a set consists only of one element, i.e., $S=\{s\}$, then the group $H$ generated by $S$ consists of just the neutral element $0_G$ of $G$ (i.e., the all zero bit vector $(0, \ldots, 0)\in G$) and $s$ itself, i.e., $H=\{0_G, s\}$. Indeed, any other multiple of $s$ is either the zero vector or $s$ as the components are added modulo $2$.

Finally, the set $X$ is $\{0,1\}^n$ and the map $f$ is precisely the map as given in Simon's problem. Let's check that the defining property to make $(G, H, f)$ an instance of a hidden subgroup problem actually holds, namely that $f$ is constant on cosets $gH$ and takes different values for different cosets $gH \not= g'H$. We are promised that $f(x)=f(y)$ iff $x\oplus y \in \{0_G,s\}$. Pick an element $g \in G$. As $H = \{0_G,s\}$, the set $gH$ is equal to $\{0_G \oplus g, s \oplus g\} = \{g, s\oplus g\}$. We have that $g \oplus (s \oplus g) = s$ which implies that $f(g) = f(s \oplus g)$, i.e., the function is constant on the coset. By a similar argument we get that two different cosets get mapped to different values. This shows that Simon's problem is indeed an instance of an abelian hidden subgroup problem. Finally, note that in an abelian group every subgroup is a normal subgroup.

For more information about the abelian hidden subgroup problem, see for instance this paper by Brassard and Hoyer or this paper by Mosca and Ekert.

$\endgroup$
  • $\begingroup$ So in summary, the group $G$ under consideration is $(\mathbb Z_2^n,\oplus)$ with component-wise sum, the subgroup $H$ is $H=\{0,s\}$, and this is normal because every subgroup of an abelian group is normal. The cosets of $H$ are of the form $g+H=\{g,s\oplus g\}$, and so the requirement of Simon's problem are equivalent to $f$ being (naturally extendible to a function that is) injective on $G/\{0,s\}$. Great, thanks for the answer $\endgroup$ – glS Mar 18 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.