NOT and CNOT as Classical Gates

Last lesson established what a reversible gate is: a permutation of bit patterns. Now let's meet the two smallest gates anyone actually builds with. One of them you have known since your first logic course. The other is the workhorse of every reversible — and every quantum — circuit ever drawn: the controlled-NOT. Everything here is plain classical bits, 0s and 1s on wires; no quantum mechanics anywhere in sight.

NOT: the one-bit shuffle

On a single bit there are only 2^1 = 2 patterns, so there are exactly 2! = 2 reversible 1-bit gates: the do-nothing identity, and NOT, written x \mapsto \bar{x} = 1 - x. As a permutation NOT is the transposition (\,0\;1\,), and like every single transposition it is self-inverse:

\mathrm{NOT}(\mathrm{NOT}(x)) = \overline{\bar{x}} = x.

Flip a bit twice and you are back where you started. "Self-inverse" is a theme to watch — every gate in this lesson and the next two has it, and it is a gift: the circuit that undoes your circuit is the same circuit, run right-to-left.

CNOT: if this bit is on, toggle that one

Two wires now. The controlled-NOT (CNOT for short, also called the Feynman gate) carries a control bit x and a target bit y, and follows one sentence of logic: if the control is 1, flip the target; otherwise touch nothing. The control always passes through unchanged. Compactly:

(x, y) \;\longmapsto\; (x,\; x \oplus y),

where \oplus is XOR — addition of bits, throwing the carry away. The full truth table:

x in	y in	x out	x \oplus y out
0	0	0	0
0	1	0	1
1	0	1	1
1	1	1	0

Run the reversibility check from last lesson: the output rows are 00, 01, 11, 10 — all four patterns, each once. CNOT is a permutation, the transposition (\,10\;11\,): it fixes the first two rows and swaps the last two.

The circuit symbol

In a circuit diagram each bit is a horizontal wire read left to right. CNOT is drawn as a filled dot on the control wire and a ⊕ (a circled plus, echoing XOR) on the target wire, joined by a vertical line:

This exact notation carries over unchanged to quantum circuit diagrams — the CNOT on qubits is the same gate, drawn the same way, just acting on quantum states instead of definite bits.

Self-inverse, by algebra

Apply CNOT twice and track the target bit. After the first gate it holds x \oplus y; the second gate XORs the (unchanged) control x in again:

x \oplus (x \oplus y) \;=\; (x \oplus x) \oplus y \;=\; 0 \oplus y \;=\; y.

Three XOR facts did all the work: it is associative, anything XOR itself is 0, and 0 XOR anything leaves it alone. So two CNOTs in a row are the identity — \mathrm{CNOT}^2 = I — which is also obvious from the cycle picture: a transposition done twice swaps the pair back.

Two jobs in one gate

Why is this little gate everywhere? Because it does reversibly the two jobs ordinary circuits do destructively:

Reversible XOR. An ordinary XOR gate maps two bits to one and forgets which summand was which. CNOT computes the same x \oplus y but keeps x alive on the control wire — with both x and x \oplus y in hand, you can recover y = x \oplus (x \oplus y). Nothing was lost.
Reversible FAN-OUT. Ordinary circuits copy a signal by physically splitting a wire. The reversible way: feed the bit you want copied into the control and a fresh 0 into the target. Then (x, 0) \mapsto (x, x \oplus 0) = (x, x) — two synchronized copies of x, made by a perfectly invertible step. This copy trick is a load-bearing move: Bennett's uncompute trick, at the end of this module, hinges on it.

Richard Feynman fell for reversible computing in the early 1980s, lecturing on the physics of computation at Caltech and asking how small and how cold a computer could possibly run. In his notes the controlled-NOT was the star two-bit primitive, and the reversible-computing community started calling it the Feynman gate in his honour. Feynman's obsession paid off twice over: his 1982 musings on simulating physics with reversible logic led straight to his proposal of the quantum computer — where, sure enough, the CNOT sits at the heart of nearly every circuit.

Students meeting CNOT often shrug: "it's just XOR." Half right, and the half matters. A bare XOR gate — two wires in, one wire out — is irreversible: output 1 could have come from 01 or 10, and a bit of information is destroyed. CNOT is XOR plus a receipt: it carries the control bit through untouched, and that surviving bit is exactly what makes the table a permutation. The pattern generalises — the standard recipe for making any operation reversible is "keep enough of the input alongside the answer" — and you will see it again with the Toffoli gate and AND.