6

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?

glS
  • 27,510
  • 7
  • 37
  • 125

1 Answers1

6

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.

MartinQuantum
  • 765
  • 5
  • 9