Toffoli gates are all you need

ELI5 / TLDR

Every time a computer erases a bit of information, it has to release a tiny amount of heat — that’s a law of physics called Landauer’s principle. Reversible computing sidesteps this by never erasing anything, and it turns out you only need one building block to do it: the Toffoli gate, a simple three-input, three-output switch. It can simulate any classical computation. The catch is you end up carrying around extra “junk” bits that the original circuit didn’t need.

The Full Story

The physics tax on forgetting

Imagine you’re writing on a whiteboard. Writing is free, but erasing costs you — every swipe of the eraser generates a little heat. That’s Landauer’s principle in a nutshell. There’s a hard floor on how much energy it takes to destroy one bit of information:

E >= log(2) * k_B * T

where k_B is Boltzmann’s constant and T is the temperature of the room. At room temperature this is absurdly small — about 3 x 10^-21 joules. Today’s chips burn roughly a billion times more than that per operation. But the principle matters because it’s a wall. No matter how clever your engineering gets, irreversible computation will always produce waste heat. Reversible computation, in theory, doesn’t have to.

One gate to rule them all

The Toffoli gate takes three bits in and spits three bits out:

T(a, b, c) = (a, b, c XOR (a AND b))

Think of it like a bouncer with two clipboards. The first two bits (a and b) pass straight through untouched — they’re the “control” bits. The third bit (c) only gets flipped if both a and b are 1. If either control bit is 0, c walks through unchanged.

The crucial property: the gate is its own undo button. Run it twice and you’re back where you started. That’s what makes it reversible — no information is destroyed, so no Landauer tax.

Building everything from one brick

Here’s the punchline. If you feed a 1 into that third input slot, something neat happens:

T(a, b, 1) = (a, b, NOT(a AND b))

That third output is now a NAND of the first two inputs. NAND is the universal gate of classical computing — you can wire up any Boolean function from nothing but NAND gates. So the Toffoli gate, a reversible operation, can simulate any irreversible classical circuit. Reversibility doesn’t cost you any computational power.

The luggage problem

There’s a trade-off. A normal NAND gate eats two inputs and produces one output. The Toffoli version needs three inputs and produces three outputs. Those extra bits — the ones you didn’t ask for — are called ancillary or “garbage” bits. They’re the price of reversibility: since you can’t destroy information, you have to carry it with you. Think of it as packing for a trip where you’re not allowed to throw anything away. Your suitcase gets bigger.

In practice, managing this overhead — figuring out how to minimize garbage bits or “uncompute” them — is one of the core engineering challenges of reversible and quantum circuit design.

Claude’s Take

This is a tight, well-written explainer from John D. Cook — the kind of blog post that does one thing and does it cleanly. He picks a single result (Toffoli gate universality), gives the physics motivation (Landauer’s principle), walks through the proof (NAND construction), and flags the practical caveat (ancilla overhead). No fluff, no overselling.

The score sits at 6 because the content, while correct and clearly presented, covers well-trodden ground. Toffoli gate universality has been a textbook result since the 1980s, and the post doesn’t add new insight or context beyond the standard explanation. It’s a good reference note — the kind of thing you bookmark and send to someone who asks “wait, why do quantum people care about reversible gates?” — but it won’t reshape how you think about the topic if you’ve encountered it before.

Worth the five-minute read. Not worth a second one.