I am trying to understand Simon's Algorithm now, but I am confused as to how the factorization of the XOR operator in $$\begin{aligned} \alpha_y &= \frac 1{\sqrt 2}(-1)^{r\cdot y} + (-1)^{(r \oplus s)\cdot y}\\ &=\frac 1{\sqrt 2}(-1)^{r\cdot y}(1+ (-1)^{s\cdot y})\end{aligned}$$ works. After the factorization, ${r\cdot y}$ and ${s\cdot y}$ seem to just be products of one another.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
$(-1)^1 = (-1)^3$, so the operation in your question is in the sense of modulo 2, hence $r\cdot y+s\cdot y=(r\oplus s)\cdot y$.
Examples to show things I've said just now. $r = (1,0,1),s=(0,0,1),y=(1,1,1),$ then $r\cdot y=(1,0,1),s\cdot y=(0,0,1),(r\cdot y+s\cdot y)\text{mod2 }=(1,0,0)$ and $r\oplus s=(1,0,0),(r\oplus s)\cdot y=(1,0,0)$, easy to see $r\cdot y+s\cdot y=(r\oplus s)\cdot y$.
