Garbage Bits and Ancillas

The universality lesson ended on a quiet confession: Toffoli circuits compute everything provided we may pin some inputs to constants and ignore some outputs. This lesson looks those two concessions squarely in the eye, gives them their proper names — ancillas in, garbage out — and asks the question a thermodynamicist would ask: who pays for the wires we agreed to ignore? The answer is the cliff-hanger of this module.

The standard embedding

Most functions worth computing are irreversible as stated. A comparator maps many pairs to the same "equal"; an AND crushes four pasts into two. To run such an f on reversible hardware we embed it in a bigger, reversible map. The recipe:

(x,\; \underbrace{0 \cdots 0}_{k}) \;\longmapsto\; \bigl(x,\; f(x),\; g(x)\bigr)

the k extra input wires, pinned to 0, are ancillas — blank scratch paper the circuit is handed;
f(x) is the answer you wanted;
g(x) is everything else the scratch paper ended up holding — intermediate results, leftover inputs, by-products. This is the garbage: outputs with no meaning to you, whose only job is to keep the whole map a permutation. (The surviving copy of x itself is often counted as garbage too — you didn't ask for it back.)

The widths always balance: a reversible circuit has exactly as many output wires as input wires, so whatever the answer doesn't fill, garbage must.

Worked example: a reversible half adder

Add two bits: \mathrm{sum} = a \oplus b, \mathrm{carry} = a \wedge b. Irreversibly that is 2 bits in, 2 bits out — but the map (a,b) \mapsto (\mathrm{sum}, \mathrm{carry}) is not a permutation (01 and 10 both give sum 1, carry 0). Reversibly, take one ancilla and two gates:

Toffoli on (a, b, 0): the ancilla becomes a \wedge b — the carry. State: (a,\; b,\; a \wedge b).
CNOT with control a, target b: the middle wire becomes a \oplus b — the sum. State: (a,\; a \oplus b,\; a \wedge b).

Three wires in, three out: the two answer bits (sum and carry) plus one leftover — a, riding along untouched. That surviving a is our first specimen of garbage: harmless-looking, undeniably necessary (drop it and the map stops being invertible), and — as we are about to see — thermodynamically radioactive.

function	irreversible in → out	reversible in → out	ancillas k	garbage bits
AND	2 → 1	3 → 3	1	2 (the inputs a, b)
half adder	2 → 2	3 → 3	1	1 (the input a)
NAND	2 → 1	3 → 3	1	2
general f, m bits → r bits	m → r	m + k → m + k	k	m + k - r

Why garbage is poisonous

So the reversible computer works — it just leaves droppings. Why not simply reset the garbage wires to 0 when the computation is done, ready for the next run?

Because resetting a bit whose value you don't know is erasure, and erasure is the one thing thermodynamics charges for. Landauer's principle — the centrepiece of the foundations module — prices it at a minimum of kT \ln 2 of dissipated heat per bit. Erase k garbage bits and you pay at least k \, kT \ln 2, every single run. The garbage bits are exactly where the information that irreversible f would have destroyed has been stashed; wiping them destroys it after all. The reversible circuit didn't cancel the bill — it postponed it to checkout.

And doing nothing is no escape either. Leave the garbage in place and it accumulates: every subcircuit of a long computation adds its own droppings, your register file silts up with junk, and the ancilla supply — which must arrive pre-set to 0 — runs dry. Fresh zeroed bits are themselves a consumable: producing one from a used bit is, again, erasure. Trapped between a heat bill and a rubbish mountain, reversible computing looks stuck.

any f on m bits embeds in a reversible map (x, 0^k) \mapsto (x, f(x), g(x)) — ancillas are constant-0 inputs, garbage g(x) is the unwanted outputs that keep the map a permutation;
input and output widths match: m + k wires each way, so garbage occupies whatever the answer leaves over;
erasing the garbage afterwards costs at least kT \ln 2 per bit — the full Landauer bill of the irreversible computation, merely postponed;
not erasing lets garbage accumulate and exhausts the supply of fresh ancillas.

There is a seductive wrong idea here, and it is worth having consciously so you can refuse it: "the computer ran reversibly, so we've already won — the garbage is just clutter, and clutter can be binned." The error is thinking of the garbage as meaningless. It is the opposite: the garbage is dense with meaning — it is the unique fingerprint of which input produced your answer, the very information whose survival made the circuit reversible. Binning it is not tidying; it is performing, in one bulk transaction at the end, all the forgetting the gates so carefully avoided. Thermodynamics audits the whole ledger, not the individual steps. The genuinely astonishing fact — proved by Charles Bennett, next lesson — is that the ledger can be balanced honestly: the garbage can be disposed of reversibly, for free.

Because each embedding tends to have both, the two words blur easily. Keep the ledger straight by when and what you know: an ancilla is an input wire whose value you know perfectly (a constant 0, by convention) — it costs you a supply of pre-zeroed bits. Garbage is an output wire whose value you know only as "some function of the input I didn't want" — it costs you either storage (keep it) or heat (erase it). One wire can be both in sequence: the half adder's ancilla enters as a known 0 and exits as the wanted carry — not garbage at all — while the wire carrying a enters as honest input and exits as garbage. Judge each wire at each end, not by its position in the diagram.