The Toffoli Gate

NOT and CNOT gave us reversible flipping, XOR and copying — but try as you might, you cannot coax an AND out of them. And without AND (or something like it) you cannot compute much: no adders, no comparators, no computers. The gate that breaks the logjam needs three wires. It was pinned down by Tommaso Toffoli around 1980, and it is the single most important gate in reversible computing: the controlled-controlled-NOT, or Toffoli gate.

The rule extends CNOT in the most natural way imaginable: two controls instead of one. Flip the target only if both controls are 1; pass the controls through untouched. In symbols:

(a, b, c) \;\longmapsto\; \bigl(a,\; b,\; c \oplus (a \wedge b)\bigr).

The truth table: eight rows, one swap

Three bits means 2^3 = 8 rows. Since the target only flips when a = b = 1, six of the eight rows pass through completely unchanged — all the action is at the bottom:

abc in	abc out	what happened
000	000	controls not both 1 — untouched
001	001	untouched
010	010	untouched
011	011	untouched
100	100	untouched
101	101	untouched
110	111	both controls 1 — target flips
111	110	both controls 1 — target flips

Every 3-bit pattern appears exactly once on the right, so this is a permutation — reversible, as promised. In cycle notation the Toffoli gate is the lone transposition (\,110\;111\,), and like every single transposition it is self-inverse: apply it twice and the swapped pair swaps back, c \oplus (a \wedge b) \oplus (a \wedge b) = c. The gate that undoes a Toffoli is a Toffoli.

The circuit symbol

Three wires; a filled dot on each control wire; a ⊕ on the target wire; one vertical line through all three. Read it aloud exactly as it looks: "if this and this, then flip that."

The payoff: AND, reversibly

Now the move that makes this gate famous. Feed the two bits you want to AND into the controls, and a constant 0 — an ancilla, a helper bit prepared in a known state — into the target:

(a, b, 0) \;\longmapsto\; \bigl(a,\; b,\; 0 \oplus (a \wedge b)\bigr) = (a,\; b,\; a \wedge b).

The third wire now carries a \wedge b — a genuine AND — and yet nothing was destroyed, because a and b both walked out alongside the answer. Worked examples, straight off the table:

(1, 1, 0): both controls on, target flips — (1, 1, 1). Third bit = 1 = 1 \wedge 1. ✓
(1, 0, 0): controls not both on, nothing moves — (1, 0, 0). Third bit = 0 = 1 \wedge 0. ✓
(0, 1, 0): same story — (0, 1, 0), third bit 0 = 0 \wedge 1. ✓

Set the ancilla to 1 instead and the target output becomes 1 \oplus (a \wedge b) = \overline{a \wedge b} — a NAND. And NAND, as every logic course proves, builds everything: NOT, AND, OR, adders, memories, whole processors. One reversible gate plus a supply of constant bits therefore simulates all of Boolean logic — the claim we will state carefully as universality two lessons from now.

maps (a, b, c) \mapsto (a, b, c \oplus (a \wedge b)): the target flips exactly when both controls are 1; the controls never change;
is a permutation of the 8 patterns — the transposition (\,110\;111\,) — and is self-inverse;
with ancilla c = 0 computes AND: (a, b, 0) \mapsto (a, b, a \wedge b);
with ancilla c = 1 computes NAND — so Toffoli gates plus constants can simulate any Boolean circuit.

It looks almost too small to matter: of eight rows, the Toffoli gate touches two. But those two rows are precisely where a product of inputs shows itself — the target moves only when a \wedge b = 1, so the gate's behaviour genuinely depends on a nonlinear combination of its inputs. NOT and CNOT can only ever XOR wires together, and XORs of XORs stay XORs; no amount of them produces a row-pattern that singles out "a and b both on." That one nonlinear twist is the entire gap between "can shuffle parities around" and "can compute anything computable" — a story told in full in the universality lesson. The same gate, promoted to qubits, plays the same heavy-lifting role in quantum circuits.

A common first reaction to (a, b, 0) \mapsto (a, b, a \wedge b): "but the inputs are still sitting there — shouldn't we clean them up?" Resist it. Those surviving copies of a and b are exactly what keeps the gate reversible: an AND that returned only a \wedge b would merge four pasts into two and destroy information. If you erase the leftover inputs afterwards, Landauer's principle presents its bill — at least kT \ln 2 of heat per erased bit — and you have gained nothing over an ordinary AND gate. The reversible discipline is to carry helpers forward and dispose of them cleverly later; how to do that without ever paying the eraser is precisely the business of the garbage-bits and uncompute lessons at the end of this module.