1
$\begingroup$

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?

$\endgroup$

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Thank you so much for your explanation, it already helped so much!! Can I please ask how you obtained 0⊕B=B at the end? $\endgroup$ Commented Feb 24, 2023 at 18:17
  • 1
    $\begingroup$ 0 + B = B, zero is an identity element. $\endgroup$
    – MonteNero
    Commented Feb 24, 2023 at 18:31
  • $\begingroup$ @user_confused if your $\oplus$ symbol stands for addition modulo two, then you can use the definition of modular arithmetic: Two things are equal "mod 2" if they differ by an integer multiple of 2. Clearly $B$ and $B+0$ are equal so they differ by an integer (zero) times 2 (i.e., they differ by zero). $\endgroup$
    – hft
    Commented Feb 24, 2023 at 18:53
  • $\begingroup$ If your symbol $\oplus$ stands for XOR, then you can look at the truth table for XOR. In particular: 0 XOR 0 is 0, 0 XOR 1 is 1, so for any $B$ (whether B is equal to 0 or equal to 1) we have 0 XOR B = B. $\endgroup$
    – hft
    Commented Feb 24, 2023 at 18:54
  • $\begingroup$ Ok I see I see. Thank you so much! $\endgroup$ Commented Feb 24, 2023 at 19:41
1
$\begingroup$

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.