Synthesis stops being an abstract art the moment somebody asks for an adder. Addition is the workhorse of all computation — and it is also, at first glance, a reversibility disaster: (a, b) \mapsto a + b throws a whole operand away. Yet reversible adders exist, they are elegant, and they are arguably the most-built reversible circuits in the world, because one sits inside every implementation of Shor's factoring algorithm. This page builds them: first the trick that makes addition legal at all, then the two classic designs — the VBE ripple-carry adder and the sleeker Cuccaro adder — and then the payoff that only reversible hardware gets: subtraction for free, by running the adder backwards.

Add in place: the legal bijection

The fix for addition's information loss is to keep one operand. Map

(with the sum taken modulo 2^n on n-bit registers, or with a carry-out wire catching the overflow bit). This is a genuine bijection: from the output (a, s) you recover the input as (a, s - a) — nothing is forgotten. Notice the shape: it is exactly the XOR-accumulate pattern of the CNOT, (a,b) \to (a, b \oplus a), promoted from single bits to whole registers — indeed for 1-bit numbers the in-place adder is a CNOT (plus a Toffoli computing the carry ab — the very reason the Toffoli is sometimes drawn as "the carry gate"). Everything below is about doing this on multi-bit binary numbers with the carries handled reversibly.

Design 1: the VBE ripple-carry adder

The first quantum-era adder, by Vedral, Barenco and Ekert (1996), is a direct reversible port of the ripple-carry adder you know from classical hardware — with one reversible twist. It runs in three sweeps:

• carry-compute ladder: a chain of CARRY blocks (each: two Toffolis and a CNOT) writes every carry bit c_1, c_2, \ldots onto a dedicated ancilla wire per bit position, rippling from the low end upward;
• sum: CNOTs form each sum bit s_i = a_i \oplus b_i \oplus c_i in place on the b register;
• carry-uncompute: the CARRY ladder runs again in reverse, wiping every carry ancilla back to 0 — Bennett's compute–use–uncompute discipline, without which the circuit would leak a register full of garbage carries.

The bill: roughly 4n Toffolis (the ladder is paid twice) and n ancilla wires for an n-bit addition. Correct, historic — and wide. The carries only exist as scaffolding, yet each one occupies its own wire.

Design 2: the Cuccaro adder

In 2004 Cuccaro, Draper, Kutin and Moulton showed the carries never need wires of their own: the carry can ride along the a register itself. Their adder uses one ancilla in total (holding the incoming carry c_0 = 0) and two three-gate building blocks acting on the wire triple (c, b, a) at each bit position:

• MAJ ("majority"): CNOT (a \to b), CNOT (a \to c), Toffoli (c, b \to a). Afterwards the a-wire holds \mathrm{maj}(a, b, c) — which is exactly the next carry bit — while the other two wires hold XOR scaffolding;
• UMA ("un-majority and add"): Toffoli (c, b \to a), CNOT (a \to c), CNOT (c \to b). It undoes its partner MAJ and deposits the sum bit s_i = a_i \oplus b_i \oplus c_i on the b-wire on the way back down.

The full adder is a V: MAJ blocks ripple up the register, one CNOT tips the final carry onto the carry-out wire, and UMA blocks come back down, cleaning as they go. Here it is for 2-bit numbers:

Each bit position costs one MAJ and one UMA — one Toffoli each — so about 2n Toffolis, 2n-ish CNOTs, and a single ancilla: half the Toffolis and a fraction of the width of VBE. The cost-metric habits of this module are exactly how you compare such designs at a glance:

Subtraction and comparison, free of charge

Now the magic that irreversible hardware simply cannot copy. The adder is a bijection (a, b) \to (a, a+b); every reversible circuit run backwards (same gates, reverse order — they are all self-inverse) computes the inverse map:

A subtractor is the adder, read right to left. No new design, no new verification — reversibility means every arithmetic circuit you build is two circuits. And a comparator comes almost as cheaply: run the subtract direction just far enough to produce the borrow/sign bit of b - a, copy that single bit onto an output wire with a CNOT, then uncompute the subtraction. The registers emerge untouched, plus one clean bit answering "is a > b?" — the standard pattern for every reversible predicate: compute, copy out one bit, uncompute.