Reversible Universality

In ordinary logic design there is a famous economy result: everything — every logic circuit you have ever built — can be assembled from copies of one 2-input gate, NAND. This lesson asks the same question of the reversible world, and gets a two-part answer with a genuine surprise in it. The good news: one 3-bit gate suffices — Toffoli, and separately Fredkin, can each build everything. The surprise: three bits is not a convenience but a necessity. Take all the reversible gates on 1 and 2 bits — every last one of them — and together they still cannot make an AND. Reversibility pushes the price of universality up a wire.

The positive result: Toffoli (or Fredkin) builds everything

Call a set of reversible gates universal if, allowing ancilla wires set to constants and extra "garbage" outputs we agree to ignore, its circuits can compute any Boolean function. The proof for the Toffoli gate is a three-line relay race you have already run:

Toffoli → NAND. Fix the target ancilla at 1: (a, b, 1) \mapsto (a, b, \overline{a \wedge b}). The third wire is a NAND.
Toffoli → FAN-OUT. Fix one control at 1 and the target at 0: (a, 1, 0) \mapsto (a, 1, a) — a copy of a.
NAND + fan-out → everything. That is the classical universality theorem: with NAND and the ability to split signals, any circuit — adders, multiplexers, CPUs — can be wired up.

The Fredkin gate passes the same test by its own constant tricks (F(x, y, 0) gives AND, F(c, 0, 1) gives NOT and a copy). So a single well-chosen 3-bit reversible gate, fed constants, computes anything computable. The same question, asked of gates on qubits, has its own richer answer — universal quantum gate sets — but the classical backbone is exactly this result.

The negative result: 1- and 2-bit gates hit a wall

Now the striking half. On 1 and 2 bits the reversible gates are: identity, NOT, the wire swap, CNOT (in both orientations), and their combinations — 2! \times (2^2)!-ish worth of tables, 24 of them on 2 bits. Every one of these gates only ever does two kinds of thing to a wire: XOR wires together, or flip by a constant. And that confines them to a tidy little island: the affine functions over \mathrm{GF}(2) — outputs of the shape

x_{i_1} \oplus x_{i_2} \oplus \cdots \oplus x_{i_k} \oplus c, \qquad c \in \{0, 1\}

— a XOR of some subset of the inputs, possibly flipped. ("Affine" = linear part plus an optional constant.) AND is not of this shape, and no amount of composing gets you off the island.

Worked argument. Track what each wire of a circuit can carry. At the start, wire i carries the affine expression x_i. Now apply any of the available gates and watch the invariant hold:

a NOT turns the affine expression u into u \oplus 1 — still affine;
a CNOT turns the pair (u, w) into (u, u \oplus w). XORing two affine expressions cancels or keeps variables pairwise and XORs the constants — the result is again a XOR-of-inputs-plus-constant. Still affine;
a swap just relabels the wires.

By induction, every wire, after every gate, carries an affine function of the primary inputs. Nowhere can a product term x \wedge y be born: XOR can cancel an x against an x, but it can never multiply an x by a y. AND is nonlinear — check it against the shape above: no choice of subset-XOR-plus-constant agrees with x \wedge y on all four inputs. So NOT, CNOT and swap generate strictly less than everything, and a 3-bit gate is necessary for reversible universality. That is precisely the wall the Toffoli gate was invented to break: its target update c \oplus (a \wedge b) smuggles in the one thing XOR cannot make — a product.

Watch the invariant at work

Step through a little circuit of CNOTs and a NOT, reading the expression each wire carries. However the gates are stacked, every annotation stays a XOR of x, y and constants — the affine island in action:

the Toffoli gate is universal: with ancilla constants (and garbage outputs permitted) its circuits compute every Boolean function — via NAND (c = 1) and fan-out;
the Fredkin gate is universal too, by its own constant embeddings — and it is conservative into the bargain;
no set of 1- and 2-bit reversible gates is universal: NOT, CNOT and swap generate only the affine functions x_{i_1} \oplus \cdots \oplus x_{i_k} \oplus c over \mathrm{GF}(2) — of which there are just 2^{n+1} on n inputs, out of 2^{2^n} Boolean functions;
hence 3-bit gates are necessary (and, by Toffoli or Fredkin, sufficient) for reversible universality.

How small is the affine island?

Count it. An affine function of n bits is fixed by two choices: which subset of the inputs to XOR (that is 2^n subsets, the empty set giving a constant function) and whether to add the flip \oplus 1 (a factor of 2). Total: 2^{n+1} affine functions. Compare that with all 2^{2^n} Boolean functions of n bits. At n = 3: 16 affine functions in an ocean of 256. At n = 5: 64 against four billion. The island NOT and CNOT are marooned on is vanishingly small — and AND, OR, majority, and essentially everything a computer needs live on the mainland.

In the irreversible world NAND — a 2-input gate — is universal, so why does the reversible world need three wires? Blame the bookkeeping of permutations. A reversible 2-bit gate is a permutation of only 4 patterns, and it turns out every one of the 24 such permutations happens to be an affine map \mathbf{v} \mapsto A\mathbf{v} \oplus \mathbf{b} on \mathrm{GF}(2)^2 — with so few patterns there is simply no room to be nonlinear and still be a bijection. Only at 3 bits, with 8! = 40320 permutations against a mere 1344 affine ones, do genuinely nonlinear shuffles exist — and Toffoli is the canonical specimen. Irreversible logic never faces this squeeze, because forgetting bits is itself a nonlinear act: NAND destroys information at every step, and that destruction is where its universality-for-cheap comes from.

"Toffoli is universal" does not mean a bare mesh of Toffoli gates computes anything you like. The definition quietly grants two helpers, and both are essential: ancilla inputs — extra wires you may pin to constants 0 or 1 — and garbage outputs — wires whose final values you are allowed to ignore. Without a constant to feed its target, a Toffoli cannot even produce a bare AND; without permission to ignore outputs, most functions (whose truth tables are not permutations) could not be computed reversibly at all. These two concessions are not fine print — they are the opening of the next lesson, because "wires we agreed to ignore" turn out to carry a thermodynamic price tag.