Reversible Computing & Uncomputation
Bennett’s trick and why garbage destroys interference.
Every quantum oracle hides a classical computation that had to be made reversible, and then cleaned up. The cleanup is not bookkeeping: leftover "garbage" is a which-path record that silently kills interference. Bennett's compute–copy–uncompute trick, and its time–space trade-offs, are how we avoid it.
What you’ll learn
- State Landauer's principle, and prove that 2-bit reversible gates are affine, so a 3-bit gate such as Toffoli is needed for reversible universality.
- Prove the parity obstruction: without ancillas, gates on fewer than wires generate only even permutations of .
- Build clean oracles by compute–copy–uncompute, and quantify how garbage destroys coherence.
- Analyze Bennett's pebble game: moves with pebbles, and the general time, space trade-off.
Why reversible, and which gates
Landauer (1961): erasing one bit of information in an environment at temperature dissipates at least of heat. Bennett (1973): any computation can be made logically reversible, so in principle it need erase nothing.
For quantum computing, reversibility is not about heat but mandatory: closed-system evolution is unitary, and on computational-basis states a classical reversible gate is a permutation matrix.
The Toffoli gate breaks the barrier. With it computes AND; with it is NOT; with and it copies (fan-out). So Toffoli, with constant ancillas, is universal for classical reversible computation (Toffoli 1980).
The parity obstruction
Think first Does the parity obstruction also forbid building on 4 qubits, without ancillas, from smaller quantum gates?
No. The argument needs every gate to be a permutation matrix, and quantum gates need not be. Barenco et al. (1995) build every without ancillas from two-qubit gates, using controlled- gates with , which are not permutations. Classical reversible logic needs the ancilla; quantum logic does not.
Compute, copy, uncompute
Make each gate of an irreversible circuit reversible: AND by a Toffoli into a fresh ancilla, NOT by , fan-out by CNOT. The leftover intermediate values are garbage.
CNOTs into the output register.
Run backwards (each Toffoli is its own inverse). The copy survives because never touches the output register.
A clean oracle, with every ancilla returned to .
Why bother to uncompute, if the output already sits in its own register? Because the garbage is entangled with .
Why garbage destroys interference
A phase oracle that leaves garbage behind.
Trace out the garbage register.
If the garbage determines (say, it contains a copy of ), every coherence vanishes: the phase oracle has become a measurement, and the interference step that follows sees a classical mixture.
Partial garbage does partial damage: the coherence between and survives exactly to the extent that and overlap. Uncomputation sets , making every overlap equal to .
A buggy oracle leaves garbage with for all . Compared with a clean oracle, the off-diagonal elements of are
- unchanged
- multiplied by factors of modulus
- multiplied by
- set to zero
Show the answer
B. multiplied by factors of modulus
Each coherence is multiplied by , so its magnitude shrinks by the factor . Interference visibility drops accordingly, but not to zero.
Time–space trade-offs: pebble games
Bennett's 1973 construction keeps the entire history of the computation: space proportional to the running time , which is ruinous for long computations. His 1989 fix is a pebble game on the chain of intermediate states . A pebble on node means "state is stored"; you may place or remove a pebble on node only if node holds one (computing or uncomputing step ). The goal: a pebble on node , and none elsewhere.
Three recursive calls, the last one played backwards.
With and .
Only the midpoint pebble is held while recursing.
Pebble the checkpoints in turn, then clear the first : recursive calls per level. As , .
With recursive halving, how many pebbles (stored intermediate states, the final one included) are needed to reach node ?
Show the answer
11 pebbles
pebbles and moves, versus Bennett's 1973 strategy with pebbles and moves. Eleven is optimal: with pebbles no strategy ever reaches beyond node (Knill 1995), which is for .
Key takeaways
- Classical reversible gates are permutations; 2-bit ones are affine, so a 3-bit gate such as Toffoli is needed, and without ancillas small gates generate only even permutations.
- Compute–copy–uncompute turns any classical circuit into a clean oracle with gates and ancillas, which gives .
- Garbage multiplies every coherence by : a which-path record that destroys interference unless it is uncomputed.
- Pebble games trade time for space: pebbles for moves, and in general time with space.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Why is no set of 1- and 2-bit reversible gates universal for classical reversible computation, even with ancillas?
- They are all affine over , and AND is not affine
- They are not invertible
- They cannot copy bits
- They violate Landauer's principle
Show the answer
A. They are all affine over , and AND is not affine
All 24 permutations of are affine maps, and compositions of affine maps (with constant inputs) remain affine, while AND is not. A 3-bit gate such as Toffoli is necessary.
In compute–copy–uncompute, why is the output copied before running ?
- To create the entanglement needed for a speedup
- Because would otherwise erase the output along with the garbage
- Because Toffoli gates are not their own inverses
- To get around the no-cloning theorem
Show the answer
B. Because would otherwise erase the output along with the garbage
returns every register touched to its initial value, including the one holding . Copying into a register that never touches preserves it.
Recursive halving reaches node of the pebble game with only pebbles. What is the price?
- Exponentially many moves
- A nonzero error probability
- Some irreversible steps
- moves instead of about
Show the answer
D. moves instead of about
gives : polynomially more time for exponentially less space. Splitting into segments brings the exponent down to .
A phase oracle leaves the computed bit itself as garbage, . Between which basis states , does coherence survive?
- None
- All pairs
- Pairs with
- Pairs with
Show the answer
C. Pairs with
, so only coherences within each level set of survive. That is why the uncleaned circuit in the widget gives or at random instead of always : only coherence within each parity class survives.
Further reading
- R. Landauer, "Irreversibility and heat generation in the computing process", IBM J. Res. Dev. 5, 183 (1961).
- C. H. Bennett, "Logical reversibility of computation", IBM J. Res. Dev. 17, 525 (1973).
- T. Toffoli, "Reversible computing", in Automata, Languages and Programming (ICALP 1980), Lecture Notes in Computer Science 85.
- C. H. Bennett, "Time/space trade-offs for reversible computation", SIAM J. Comput. 18, 766 (1989).
- M. A. Nielsen & I. L. Chuang, Quantum Computation and Quantum Information, §3.2.5 (Cambridge, 10th anniv. ed., 2010).