Bits, XOR and bit strings

XOR, written $\oplus$, is addition mod 2: add the bits and keep only whether the total is even (0) or odd (1). So $0\oplus0 = 0$, $0\oplus1 = 1\oplus0 = 1$ and $1\oplus1 = 0$. Three facts do most of the work in these lessons:

• $y\oplus0 = y$ and $y\oplus1 = \bar y$, the flipped bit;
• $y\oplus y = 0$, so XOR-ing the same bit in twice undoes it;
• order and grouping don’t matter, so ${a\oplus b\oplus c}$ is 1 exactly when an odd number of the bits are 1.

CNOT is XOR made reversible. On the two-qubit basis state $\ket{a, b}$ (first bit $a$, second bit $b$) it keeps its control and XORs it into the target, $\ket{a, b}\to\ket{a, b\oplus a}$ (Lesson 6).

An $n$⁠-bit string $x = x_1x_2\ldots x_n$ is one of the $2^n$ elements of $\{0,1\}^n$, and it also names a basis state of $n$ qubits, written as the ket $\ket{x}$. XOR of two strings works bit by bit: $1011\oplus0110 = 1101$. The dot product mod 2 multiplies matching bits and adds the results mod 2:

With ordinary sums, as the diagnostic in Lesson 0 writes it, that is

The two agree, because XOR-ing bits together is adding them and keeping only whether the total is odd. Either way, $x\cdot z$ is 1 exactly when $x$ and $z$ share an odd number of 1s. It appears in the Deutsch–Jozsa algorithm of Lesson 9.

A sum $\sum_{x\in\{0,1\}^n}$ has one term for each of the $2^n$ strings: for $n = 2$, the four terms ${x = 00, 01, 10, 11}$. Deutsch’s algorithm turns a bit $f(x)$ into a sign, $(-1)^{f(x)}$: $+1$ when $f(x) = 0$ and $-1$ when $f(x) = 1$. Signs multiply the way bits add, $(-1)^a(-1)^b = (-1)^{a\oplus b}$, and $(-1)^k$ depends only on whether $k$ is even. One consequence: $\sum_x(-1)^{f(x)}$ is $\pm2^n$ when $f$ is constant and 0 when $f$ is balanced (as many 0s as 1s).