Modular Addition general explanation

Question

This is an incredibly basic question, but basically I'm really struggling to understand what the "addition modulo 2" is and why is it used in quantum computing.

I've tried Wikipedia, endless QC lecture notes and forums, but everywhere they just give for granted that you know what the modular addition stands for... but I don't.

What exactly does a modulo 2 addition stand for? Where does the 2 come from? Can anyone please work out an example (rather than just give the result)?

For example, why does A⊕A⊕B=B?

For example again, I get what the CNOT gate does, and I understand how the bit-flipping matter works overall, but can someone please explain or direct me to a source on how this (0⊕b=b and 1⊕b=¬b) actually links to this modular addition?

Answer 1

What exactly does a modulo 2 addition stand for?

It means that numbers are considered congruent (often stated as "equal" or "equal... mod 2") when they have the same remainder when divided by two.

For example, we write $$ 1 = 3 \;\text{mod }2 $$ since $$ 3 = 1 + 2 = 1 + 2n\;, $$ where n is the integer 1.

For example, we write $$ 1 = 5 \;\text{mod }2 $$ since $$ 5 = 1 + 4 = 1 + 2n\;, $$ where n is the integer 2.

For any number that is equal to $1 + 2n$, where $n$ is an integer, we say that number "equals 1"mod 2."

For any number that is equal to $0 + 2n$, where $n$ is an integer, we say that number "equals 0 mod 2."

$$ 1 + 2n = 1 \;\text{mod }2 \\ 0 + 2n = 0 \;\text{mod }2 $$

You can consider modular arithmetic with respect to any number. It just happens that mod 2 is useful when dealing with binary numbers, since that is the base of the number system.

---

For example, why does A⊕A⊕B=B?

If $\oplus$ generally means addition, then the equality does not hold (in general). The equality holds when $\oplus$ means addition "mod 2," e.g., when $A$ and $B$ are bits. (Addition mod 2 on classical bits is equivalent to an XOR gate on classical bits.)

Regardless of whether $A$ is 0 or 1, we have: $$ A\oplus A = 0\;\text{mod }2 $$ since (where $A=1$ and $n=1$) $$ 1 + 1 = 2 = 0 + 2 = 0 \;\text{mod }2 $$ and (where $A=0$ and $n=0$) $$ 0 + 0 = 0 = 0 + 0 = 0 \;\text{mod }2\;. $$

Then, use that fact that modular arithmetic is associative and also $$ 0 \oplus B = B $$ for any number B.

Answer 2

To add to hft's great answer, addition modulo 2 is often used as a synonym for the bit-wise XOR function, as you can see from a truth table:

a   b    xor    a+b mod 2
-------------------------
0   0     0       0
0   1     1       1
1   0     1       1
1   1     0       0