Bennett's Uncompute Trick

The last lesson left reversible computing in a trap: compute anything interesting and you are stuck holding garbage bits — keep them and drown, erase them and pay Landauer's bill after all. In 1973 Charles Bennett found the exit, and it is one of the great "of course!" moves in computer science. You cannot erase the garbage — but you built the garbage with reversible gates, so you can make the circuit swallow it back. Don't wipe the scratch paper. Run the calculation backwards and un-write it.

The three-phase recipe

Suppose a reversible circuit C computes (x, 0, 0) \mapsto (x, f(x), g(x)) — answer in one register, garbage g(x) in another. Bennett's recipe wraps C in three phases, using one extra zeroed register for the final answer:

1 — COMPUTE. Run C: (x, 0, 0, 0) \to (x, f(x), g(x), 0). Answer and garbage appear in the workspace.
2 — COPY. With a row of CNOTs (control = each answer bit, target = the fresh register's zeroed bit), copy f(x) out: (x, f(x), g(x), 0) \to (x, f(x), g(x), f(x)). Remember the classical fan-out trick: (u, 0) \mapsto (u, u) — perfectly reversible.
3 — UNCOMPUTE. Run C^{-1} — the same gates as phase 1, in reverse order, each replaced by its inverse — on the original registers: (x, f(x), g(x), f(x)) \to (x, 0, 0, f(x)). The workspace is rewound to blank zeros; only the untouched copy survives.

Net effect of the whole sandwich:

(x,\; 0) \;\longmapsto\; (x,\; f(x)) \qquad \text{— no garbage, nothing erased.}

Every step was a reversible gate; no bit was ever reset by force. The information that "g(x) would have destroyed" is never destroyed or stored — it is disassembled by the same machinery that assembled it, the way you strike a stage set rather than burning the theatre down.

Watching the registers

The whole trick is easiest to believe as a table of register contents. Step through it:

Why is phase 3 legal? Because phase 1 was a permutation, and permutations have inverses: C^{-1} exists and is built from the inverses of C's gates in reverse order — and since Toffoli, CNOT and NOT are each self-inverse, it is literally the same gates, read right to left. Phase 3 never touches the answer register, so the copy placed there in phase 2 sits safely outside the rewind.

any reversible computation (x, 0, 0) \to (x, f(x), g(x)) can be made garbage-free: compute, copy the answer into a fresh register with CNOTs, then uncompute by running the same circuit in reverse;
the net map is (x, 0) \mapsto (x, f(x)) — workspace returned to all-zeros, ancillas ready for reuse, nothing erased, no Landauer cost;
the price: about 2× the time (forward + backward, plus the cheap copy) and the space of the answer register kept alongside the workspace;
the copy step is legal classically because CNOT fan-out (u, 0) \mapsto (u, u) duplicates a definite bit reversibly.

The price tag, honestly itemised

Nothing in thermodynamics is free, and Bennett's trick pays in coin other than heat:

Time: roughly double. Every gate of C runs twice — once forward, once backward — plus one CNOT per answer bit for the copy. A computation of T gate-steps becomes about 2T.
Space: one answer register. The copy must live somewhere the rewind cannot reach, so you keep |f(x)| extra bits alongside the peak workspace. (For long computations chopped into stages, this time–space trade deepens dramatically — reversible Turing machines and "pebble games" take up that story in a later module.)
Heat: zero, in principle. The workspace comes back as genuine, reusable zeros — not because anything was erased, but because the circuit knew how it had dirtied them and undid it. Composability is restored: the next stage inherits clean ancillas, and garbage no longer accumulates.

This same choreography — compute, copy out the answer, uncompute the scratch — is not just a classical curiosity: it reappears, forced by different laws, inside quantum algorithms, where leftover workspace doesn't merely cost heat but scrambles the very interference an algorithm depends on. Learn the trick once here, on honest classical bits, and the quantum version will feel inevitable.

Charles Bennett, at IBM Research, published "Logical Reversibility of Computation" in 1973 — a decade before Fredkin and Toffoli's conservative-logic paper, and years before anyone had drawn the gates this module is built from. Working at the level of Turing machines, Bennett showed that any computation can be carried out reversibly, halting with the tape holding just the input and the answer — using exactly the compute–copy–uncompute sandwich. The result rescued Landauer's principle from a gloomy corollary: without it, one could argue that computing must dissipate heat because garbage must eventually be erased. Bennett showed the escape hatch, completing the argument his IBM colleague Rolf Landauer had begun in 1961 — computation itself has no minimum energy cost; only forgetting does. The pair's ideas, hatched two office doors apart, became the twin pillars of the thermodynamics of computation.

A tempting shortcut: the workspace holds f(x) and g(x), and some other, cleverer circuit D also maps (x, f(x), g(x))-shaped states back toward zeros — so why not rewind with D instead? Because D only cleans the workspace if it inverts exactly the map that wrote it. Run anything other than C^{-1} — the same gates, reverse order, each inverted — and the workspace ends up not at 0 \cdots 0 but at some new nonzero pattern: you have not cleaned the garbage, only laundered it. Worse, a D that "zeroes the workspace regardless of its contents" is not reversible at all — that is erasure wearing a disguise, and Landauer bills it accordingly. The uncompute phase is not generic tidying; it is the precise algebraic inverse of the mess-making.