Simple Algorithm
Quantum Computing · Rydberg State · 28 min

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 nn wires generate only even permutations of {0,1}n\{0,1\}^n.
  • Build clean oracles ∣x⟩∣y⟩↦∣x⟩∣y⊕f(x)⟩\ket{x}\ket{y}\mapsto\ket{x}\ket{y\oplus f(x)} by compute–copy–uncompute, and quantify how garbage destroys coherence.
  • Analyze Bennett's pebble game: nlog⁡23n^{\log_2 3} moves with log⁡2n+1\log_2 n+1 pebbles, and the general T1+ϵT^{1+\epsilon} time, O(Slog⁡T)\order{S\log T} space trade-off.

Why reversible, and which gates

Landauer (1961): erasing one bit of information in an environment at temperature TT dissipates at least kBTln⁡2k_BT\ln2 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 ∣a,b,c⟩↦∣a,b,c⊕ab⟩\ket{a,b,c}\mapsto\ket{a,b,c\oplus ab} breaks the barrier. With c=0c=0 it computes AND; with a=b=1a=b=1 it is NOT; with a=1a=1 and c=0c=0 it copies bb (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 C3XC^3X 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 Cn−1XC^{n-1}X without ancillas from O(n2)\order{n^2} two-qubit gates, using controlled-VV gates with V2=XV^2=X, which are not permutations. Classical reversible logic needs the ancilla; quantum logic does not.

Compute, copy, uncompute

DerivationBennett's trick
  1. R: ∣x⟩∣0a⟩∣0m⟩⟼∣x⟩∣g(x)⟩∣f(x)⟩R:\ \ket{x}\ket{0^a}\ket{0^m}\longmapsto\ket{x}\ket{g(x)}\ket{f(x)}

    Make each gate of an irreversible circuit reversible: AND by a Toffoli into a fresh ancilla, NOT by XX, fan-out by CNOT. The leftover intermediate values g(x)g(x) are garbage.

  2. copy:∣x⟩∣g(x)⟩∣f(x)⟩∣y⟩⟼∣x⟩∣g(x)⟩∣f(x)⟩∣y⊕f(x)⟩\text{copy:}\quad\ket{x}\ket{g(x)}\ket{f(x)}\ket{y}\longmapsto\ket{x}\ket{g(x)}\ket{f(x)}\ket{y\oplus f(x)}

    mm CNOTs into the output register.

  3. R−1:∣x⟩∣g(x)⟩∣f(x)⟩∣y⊕f(x)⟩⟼∣x⟩∣0a⟩∣0m⟩∣y⊕f(x)⟩R^{-1}:\quad\ket{x}\ket{g(x)}\ket{f(x)}\ket{y\oplus f(x)}\longmapsto\ket{x}\ket{0^a}\ket{0^m}\ket{y\oplus f(x)}

    Run RR backwards (each Toffoli is its own inverse). The copy survives because RR never touches the output register.

  4. Uf: ∣x⟩∣y⟩↦∣x⟩∣y⊕f(x)⟩,∣Uf∣=2∣R∣+mU_f:\ \ket{x}\ket{y}\mapsto\ket{x}\ket{y\oplus f(x)},\qquad\abs{U_f} = 2\abs{R}+m

    A clean oracle, with every ancilla returned to ∣0⟩\ket0.

Why bother to uncompute, if the output already sits in its own register? Because the garbage is entangled with xx.

Why garbage destroys interference

DerivationCoherence is multiplied by the garbage overlap
  1. ∣Ψ⟩=∑xαx(−1)f(x)∣x⟩∣g(x)⟩\ket\Psi = \sum_x\alpha_x(-1)^{f(x)}\ket{x}\ket{g(x)}

    A phase oracle that leaves garbage behind.

  2. ρx=Tr⁡g∣Ψ⟩ ⁣⟨Ψ∣=∑x,x′αxαˉx′(−1)f(x)+f(x′) ⟨g(x′)∣g(x)⟩ ∣x⟩ ⁣⟨x′∣\rho_x = \Tr_g\dyad{\Psi} = \sum_{x,x'}\alpha_x\bar\alpha_{x'}(-1)^{f(x)+f(x')}\,\braket{g(x')|g(x)}\,\ketbra{x}{x'}

    Trace out the garbage register.

  3. ⟨g(x′)∣g(x)⟩=δxx′⟹ρx=∑x∣αx∣2∣x⟩ ⁣⟨x∣\braket{g(x')|g(x)} = \delta_{xx'}\quad\Longrightarrow\quad\rho_x = \sum_x\abs{\alpha_x}^2\dyad{x}

    If the garbage determines xx (say, it contains a copy of xx), every coherence vanishes: the phase oracle has become a measurement, and the interference step that follows sees a classical mixture.

  4. Partial garbage does partial damage: the coherence between xx and x′x' survives exactly to the extent that g(x)g(x) and g(x′)g(x') overlap. Uncomputation sets g≡0g\equiv0, making every overlap equal to 11.

Check your understanding

A buggy oracle leaves garbage with ∣⟨g(x′)∣g(x)⟩∣=0.9\abs{\braket{g(x')|g(x)}} = 0.9 for all x≠x′x\ne x'. Compared with a clean oracle, the off-diagonal elements of ρx\rho_x are

  1. unchanged
  2. multiplied by factors of modulus 0.90.9
  3. multiplied by 0.810.81
  4. set to zero
Show the answer

B. multiplied by factors of modulus 0.90.9

Each coherence ∣x⟩ ⁣⟨x′∣\ketbra{x}{x'} is multiplied by ⟨g(x′)∣g(x)⟩\braket{g(x')|g(x)}, so its magnitude shrinks by the factor 0.90.9. 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 TT, which is ruinous for long computations. His 1989 fix is a pebble game on the chain of intermediate states 0→1→⋯→n0\to1\to\cdots\to n. A pebble on node ii means "state ii is stored"; you may place or remove a pebble on node ii only if node i−1i-1 holds one (computing or uncomputing step ii). The goal: a pebble on node nn, and none elsewhere.

DerivationRecursive halving
  1. P(2k):P(2k−1) to the midpoint;P(2k−1) from the midpoint to the end;P(2k−1)−1 to clear the midpointP(2^k):\quad P(2^{k-1})\ \text{to the midpoint};\quad P(2^{k-1})\ \text{from the midpoint to the end};\quad P(2^{k-1})^{-1}\ \text{to clear the midpoint}

    Three recursive calls, the last one played backwards.

  2. moves:M(2k)=3 M(2k−1)=3k=nlog⁡23≈n1.585\text{moves:}\quad M(2^k) = 3\,M(2^{k-1}) = 3^k = n^{\log_2 3}\approx n^{1.585}

    With M(1)=1M(1)=1 and n=2kn=2^k.

  3. pebbles:p(2k)=p(2k−1)+1=k+1=log⁡2n+1\text{pebbles:}\quad p(2^k) = p(2^{k-1})+1 = k+1 = \log_2 n+1

    Only the midpoint pebble is held while recursing.

  4. split into m segments:M=nlog⁡m(2m−1),p=O(mlog⁡mn)\text{split into } m \text{ segments:}\quad M = n^{\log_m(2m-1)},\qquad p = \order{m\log_m n}

    Pebble the mm checkpoints in turn, then clear the first m−1m-1: 2m−12m-1 recursive calls per level. As m→∞m\to\infty, log⁡m(2m−1)→1\log_m(2m-1)\to1.

Predict before you look

With recursive halving, how many pebbles (stored intermediate states, the final one included) are needed to reach node n=1024n = 1024?

Show the answer

11 pebbles

p=log⁡21024+1=11p = \log_2 1024+1 = 11 pebbles and 310=59,0493^{10} = 59{,}049 moves, versus Bennett's 1973 strategy with 10241024 pebbles and 2⋅1024−1=20472\cdot1024-1 = 2047 moves. Eleven is optimal: with pp pebbles no strategy ever reaches beyond node 2p−12^p-1 (Knill 1995), which is 10231023 for p=10p=10.

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 UfU_f with O(s)\order{s} gates and ancillas, which gives P⊆BQP\mathsf{P}\subseteq\mathsf{BQP}.
  • Garbage multiplies every coherence by ⟨g(x′)∣g(x)⟩\braket{g(x')|g(x)}: a which-path record that destroys interference unless it is uncomputed.
  • Pebble games trade time for space: log⁡2n+1\log_2 n+1 pebbles for n1.585n^{1.585} moves, and in general O(T1+ϵ)\order{T^{1+\epsilon}} time with O(Slog⁡T)\order{S\log T} space.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

Why is no set of 1- and 2-bit reversible gates universal for classical reversible computation, even with ancillas?

  1. They are all affine over F2\mathbb{F}_2, and AND is not affine
  2. They are not invertible
  3. They cannot copy bits
  4. They violate Landauer's principle
Show the answer

A. They are all affine over F2\mathbb{F}_2, and AND is not affine

All 24 permutations of {0,1}2\{0,1\}^2 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.

Question 2

In compute–copy–uncompute, why is the output copied before running R−1R^{-1}?

  1. To create the entanglement needed for a speedup
  2. Because R−1R^{-1} would otherwise erase the output along with the garbage
  3. Because Toffoli gates are not their own inverses
  4. To get around the no-cloning theorem
Show the answer

B. Because R−1R^{-1} would otherwise erase the output along with the garbage

R−1R^{-1} returns every register RR touched to its initial value, including the one holding f(x)f(x). Copying f(x)f(x) into a register that RR never touches preserves it.

Question 3

Recursive halving reaches node nn of the pebble game with only log⁡2n+1\log_2 n+1 pebbles. What is the price?

  1. Exponentially many moves
  2. A nonzero error probability
  3. Some irreversible steps
  4. nlog⁡23≈n1.585n^{\log_2 3}\approx n^{1.585} moves instead of about 2n2n
Show the answer

D. nlog⁡23≈n1.585n^{\log_2 3}\approx n^{1.585} moves instead of about 2n2n

M(n)=3M(n/2)M(n) = 3M(n/2) gives 3log⁡2n=nlog⁡233^{\log_2 n} = n^{\log_2 3}: polynomially more time for exponentially less space. Splitting into mm segments brings the exponent down to log⁡m(2m−1)→1\log_m(2m-1)\to1.

Question 4

A phase oracle leaves the computed bit itself as garbage, g(x)=f(x)g(x) = f(x). Between which basis states ∣x⟩\ket{x}, ∣x′⟩\ket{x'} does coherence survive?

  1. None
  2. All pairs
  3. Pairs with f(x)=f(x′)f(x)=f(x')
  4. Pairs with f(x)≠f(x′)f(x)\ne f(x')
Show the answer

C. Pairs with f(x)=f(x′)f(x)=f(x')

⟨g(x′)∣g(x)⟩=⟨f(x′)∣f(x)⟩=δf(x)f(x′)\braket{g(x')|g(x)} = \braket{f(x')|f(x)} = \delta_{f(x)f(x')}, so only coherences within each level set of ff survive. That is why the uncleaned circuit in the widget gives 0000 or 1111 at random instead of always 1111: 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).