Modulo 2 properties: $(-1)^{(x⊕a)∙y)}=1+(-1)^{a∙y)}$

Question

I am looking at Quantum Physics solution for the Simon's problem.

In there there is equation for hadamard gate:

I have trouble understanding the step: $(-1)^{(x⊕a)∙y)}=1+(-1)^{a∙y)}$

I was wondering if someone can point to general property of Modulo 2 that allows for the above equality.

Giorgos Giapitzakis · Answer 1 · 2023-07-16T18:47:50.487

1

There is a typo in the attached picture. The third line should have been written as:

$$\frac{1}{\sqrt{2^{n+1}}}\sum_{y=0}^{2^n-1} (-1)^{x'\bullet y} \color{red}{\cdot}(1+(-1)^{a\bullet y})|y\rangle$$

The above comes from the fact that the binary dot product distributes over the bitwise sum modulo $2$.

edited Jul 16 '23 at 18:47

answered Jul 16 '23 at 18:22

So: $(x⊕a)∙y=(x∙y)∙(a∙y)$ for mod 2 – PhysicsQuestion Jul 16 '23 at 18:29
@PhysicsQuestion $(x\oplus a)\cdot y = (x \cdot y) \oplus (a \cdot y)$ – Giorgos Giapitzakis Jul 16 '23 at 18:30
So can you exaplin the "???" part: $(-1)^{(x⊕a)∙y}=(-1)^{(x∙y)⊕(a∙y)}=???..=(-1)^{(a∙y)}$ – PhysicsQuestion Jul 16 '23 at 18:42
First of all it's easy to verify (casework) that $(-1)^{(x'\cdot y)\oplus (a\cdot y)} = (-1)^{x'\cdot y} (-1)^{a\cdot y}$. Then you just pull out the $(-1)^{x'\cdot y}$ as a common factor. – Giorgos Giapitzakis Jul 16 '23 at 18:46

1 Answers1