\n",
"
Example for n=3:
\n",
"\n",
"Consider the function $f:\\{0,1\\}^3\\to\\{0,1\\}^3$ defined by the truth table below. \n",
"
\n",
" \n",
" \n",
" | $$x$$ | \n",
" $$f(x)$$ | \n",
"
\n",
" \n",
" \n",
" | $$000$$ | \n",
" $$000$$ | \n",
"
\n",
" \n",
" | $$001$$ | \n",
" $$001$$ | \n",
"
\n",
" \n",
" | $$010$$ | \n",
" $$001$$ | \n",
"
\n",
" \n",
" | $$011$$ | \n",
" $$000$$ | \n",
"
\n",
" \n",
" | $$100$$ | \n",
" $$100$$ | \n",
"
\n",
" \n",
" | $$101$$ | \n",
" $$101$$ | \n",
"
\n",
" \n",
" | $$110$$ | \n",
" $$101$$ | \n",
"
\n",
" \n",
" | $$111$$ | \n",
" $$100$$ | \n",
"
\n",
"
\n",
"\n",
" \n",
" \n",
"By inspection, we can see that $f$ satisfies the properties described in the statement of Simon's problem. In particular, note that each output $f(x)$ appears twice for two distinct inputs. We are given the promise that, for each of these two inputs $x$ and $y$ with the same output $f(x)=f(y)$, we have $x \\oplus s = y$ for a yet to be determined $s$, and therefore $x\\oplus y = s$.\n",
"\n",
"For concreteness, notice that the input strings $001$ and $010$ are both mapped by $f$ to the same output string $001$. Taking the bitwise XOR of $001$ and $010$ we obtain the secret string $s$:\n",
"\n",
"$$s=001 \\oplus 010 = 011$$\n",
"\n",
"Therefore, in this example, the secret string is $s = 011$.\n",
" \n",
" \n",
"In this specific example, we also see that the string $000$ is mapped to itself. Since $x\\oplus y=s$ for two inputs $x$ and $y$ with the same output, we must have that $s$ is also mapped to $000$, since $s=000\\oplus s$. Indeed, we see that $011$ maps to $000$, as expected.\n",
"
![](\"quantum_circuit.png\",)
\n",
"