Arithmetic modulo 2

Question

I'm teaching myself about quantum computing, and in the case of the cNOT (controlled-NOT) gate, there are the following four "main" inputs/outputs (this doesn't include superpositions):

• $|00\rangle \rightarrow |00\rangle$ (The control qubit, the first one, is $0$, so the second one, the target qubit, is left alone.)
• $|01\rangle \rightarrow |01\rangle$ (The control qubit is again zero, so the target qubit is left alone.)
• $|10\rangle \rightarrow |11\rangle$ (The control qubit is $1$, so the target qubit is "flipped" to $1$.)
• $|11\rangle \rightarrow |10\rangle$ (The control qubit is again one, so the target qubit is flipped to zero.)

The video I'm watching said this can be generalized as $$|x\,y\rangle\rightarrow|x\,y\oplus x\rangle$$ where $\oplus$ is addition modulo 2. What does that mean? I've heard of modular arithmetic, but I've never quite understood it. (My only question here is about $y\oplus x$, I understand the rest of the generalization.)

Any help would be appreciated.

Answer 1

Consider $\mathbb Z$, the set of integers. Of course, we re familiar with standard addition and subtraction on $\mathbb Z$. I am going to say that two integers are "related" if their difference is divisible by 2. Therefore, $6$ and $1408$ are related, as are $-75$ and $401$. But $61$ and $62$ are not related. We can divide up the integers into classes of integers that are all related two each other. It shouldn't be too hard to see that all of the even integers are related to each other, and all of the odd integers are related to each other, but even and odd integers are not related to each other. We will represent the class of even numbers by choosing one of them, and putting it in brackets, like so: $[0]$. Similarly, we will represent the class of odd numbers by $[1]$. Thus, $[0]=[2]=[4]=...$, and $[1]=[-1]=[3]=...$ We can define addition between these classes by $[a]\oplus[b]=[a+b]$. So $$[0]\oplus[0]=[0],$$ $$[0]\oplus[1]=[1],$$ $$[1]\oplus[0]=[1],$$ $$[1]\oplus[1]=[2]=[0].$$ This is addition modulo 2. We are taking all of the integers in the first class and adding them to all the integers in the second class and seeing what class we get as a result.

Eventually, we get tired of writing the brackets, so as long as it is clear from context that $\oplus$ means addition modulo 2, we simply write $$0\oplus 0=0,$$ $$0\oplus 1=1,$$ $$1\oplus 0=1,$$ $$1\oplus 1=0.$$ Even though it looks like we are adding numbers, remember that we are really adding classes of numbers together.

We can generalize this concept to arithmetic modulo $n$ by saying that two integers are related if their difference is divisible by $n$. Then we get $n$ classes of integers which we can add, subtract, and multiply in the same way.

Answer 2

Label your outputs:

• 1) $|00\rangle \rightarrow |00\rangle$
• 2) $|01\rangle \rightarrow |01\rangle$
• 3) $|10\rangle \rightarrow |11\rangle$
• 4) $|11\rangle \rightarrow |10\rangle$

This can be generalized as $$|x\,y\rangle\rightarrow|x\,y\oplus x\rangle\tag{1}$$ where $\oplus$ is addition modulo $2$.

This is modular arithmetic at work modulo $2$, i.e., even numbers are zero mod $2$ and odd numbers are $1$ mod $2$. Since you are just dealing with $0$ (even) and $1$ (odd) your rule (1) is: $$1)\qquad|0\,0\rangle\rightarrow|0\,0\oplus 0=0\rangle$$ $$2)\qquad|0\,1\rangle\rightarrow|0\,1\oplus 0=1\rangle$$ $$3)\qquad|1\,0\rangle\rightarrow|1\,0\oplus 1=1\rangle$$ $$4)\qquad|1\,1\rangle\rightarrow|1\,1\oplus 1=0\rangle$$ where $1\oplus 1=0$ for $y\oplus x$ in 4) is equivalent to $1+1=2\equiv 0\pmod{2}$, and similarly for the others.