reversible adder

In plain terms

Quantum algorithms for factoring and for discrete logarithms spend nearly all of their work on ordinary arithmetic, so the cost of a quantum attack on cryptography is essentially the cost of addition. Addition has to be done reversibly, and the naive way is wasteful: you compute each carry into a fresh spare qubit and never clean it up, so a long computation leaves a trail of rubbish qubits that can neither be reused nor thrown away, since discarding a qubit that's entangled with your data damages the data.

The carry-clean adder solves this by storing the carries inside the register it's going to leave untouched anyway, and then undoing that storage on the way back out. It needs exactly one clean spare qubit, which it returns in its original state, so the adder can be used again immediately with no fresh supply. Two three-gate blocks do the work, one folding the carry forwards and one writing the sum bit while restoring what the first disturbed.

The saving compounds, as multiplication is built from additions and exponentiation from multiplications, so a constant factor in the adder becomes the constant factor of the whole algorithm.

In CSD

The corpus proves the adder correct for general bit width, in place, and with its ancilla restored, which are three separate statements rather than one. The register holding the first operand ends with the sum modulo the register size, the second operand is returned untouched, the spare qubit returns to its initial value, and wires outside the layout are undisturbed. The derived Toffoli count is two per bit, read off the gate list by the cost model rather than asserted.

The proof is organised as a recursion rather than as a forward and backward chain, which is what makes it an induction on bit count: the adder is the first carry block, then the adder on the high bits with the carry threaded in, then the closing block. That shape made the compute and uncompute correctness a single induction. A second design in the same layer replaces the temporary storage with measurement-based uncomputation, which trades Toffoli gates for measurements, and the hybrid lift proves the two agree on amplitudes, one gadget per carry cell. The honest boundary is that this adder is modular in the register size only, as reduction modulo a general number is a separate construction.

Mathematically

The blocks are maj c b a = [CX a b, CX a c, CCX c b a] and uma c b a = [CCX c b a, CX a c, CX c b], verified on the concrete three-wire state by decide and then lifted to general layouts. cuccaroAdd_correct gives A holding (A + B) mod 2^n, cuccaroAdd_preserves_B and cuccaroAdd_preserves_external give the untouched registers, cuccaroAdd_ancilla_clean gives the restored carry qubit, and cuccaroAdd_toffoli gives 2n Toffoli gates. The recursion cuccaroRec_correct is the induction carrying all of them.

The measurement-based variant is GidneyAdder.lean with the temporary-AND trick, and gidneyHybridAdd_amplitude in HybridLift.lean proves the hybrid circuit reproduces the unitary adder's amplitudes, with one gadget per carry cell rather than one per Toffoli. Modular reduction and the multiplier assembly are separate modules.

The name

Steven Cuccaro, Thomas Draper, Samuel Kutin and David Moulton published the carry-clean ripple-carry adder in 2004, from the IDA Center for Computing Sciences, and it remains the default choice when spare qubits are scarce. Their paper's contribution was arranging the carries so that the uncomputation is free rather than a second pass.

Craig Gidney's 2018 temporary-AND construction takes the other trade, spending measurements and classically controlled corrections to halve the Toffoli count, and the two designs mark the ends of the range that current resource estimates interpolate.

Related entries

• Toffoli gateThe Toffoli gate flips its target only when both controls are set, which is enough to compute anything classically while remaining reversible, and its count is the currency in which the cost of a quantum algorithm is quoted.
• Shor's algorithmShor's algorithm factors large numbers in polynomial time on a quantum computer, and it turned quantum computing from a curiosity into a budget line and made every deployed cryptosystem provisional.
• quantum Fourier transformThe quantum Fourier transform runs Fourier's transform as a single reversible motion of a quantum register, and it's the lens that turns hidden periods and phases into outcomes a measurement can land on.
• phase estimationPhase estimation, the workhorse subroutine of quantum computing, carries a guarantee, as if you read the dial at the nearest tick you're right at least four divided by pi squared of the time, a little over forty percent, however fine the dial.
• Clifford plus TClifford plus T is the standard universal gate set, as the Clifford gates alone are classically simulable and adding the single eighth-turn phase gate makes every unitary reachable to any accuracy you ask for.