Uncomputation in Quantum Algorithms

In classical reversible computing, garbage bits were a heat problem: leave your junk lying around and Landauer charges you for erasing it later. Annoying, but survivable — the answer register is still correct. In quantum computing the stakes are raised brutally. Junk registers become entangled with the branches of your superposition, and entangled junk does not merely cost energy — it destroys the interference your algorithm depends on. The answer comes out wrong (or rather: no better than random). Garbage has been promoted from a thermodynamic nuisance to a correctness bug. The fix, delightfully, is one you already own: Bennett's compute–copy–uncompute trick, run gate-for-gate as unitaries. This lesson shows exactly how garbage kills interference — with the amplitudes out in the open — and why uncomputation is the only clean exit.

Interference, clean: the two-branch baseline

Take the smallest interference experiment there is. A qubit sits in \tfrac{1}{\sqrt2}(|0\rangle + |1\rangle) and we apply a Hadamard. Using H|0\rangle = \tfrac{1}{\sqrt2}(|0\rangle + |1\rangle) and H|1\rangle = \tfrac{1}{\sqrt2}(|0\rangle - |1\rangle), linearity gives

H\,\tfrac{1}{\sqrt2}\big(|0\rangle + |1\rangle\big) = \tfrac{1}{2}\big(|0\rangle + |1\rangle\big) + \tfrac{1}{2}\big(|0\rangle - |1\rangle\big) = |0\rangle.

Read the bookkeeping: the amplitude of |0\rangle is \tfrac12 + \tfrac12 = 1 (two paths, constructive), the amplitude of |1\rangle is \tfrac12 - \tfrac12 = 0 (two paths, destructive). Measurement yields 0 with certainty. Every quantum algorithm is this pattern at scale: paths that add for right answers, cancel for wrong ones.

Now attach garbage — and watch the cross terms die

Suppose that along the way, each branch computed something and left junk behind — a work register holding |g(x)\rangle in the branch where the qubit is |x\rangle, with g(0) \neq g(1) distinct basis states, so \langle g(0)|g(1)\rangle = 0. The state before the Hadamard is now

\tfrac{1}{\sqrt2}\big(|0\rangle|g(0)\rangle + |1\rangle|g(1)\rangle\big).

Apply H to the first qubit (the junk register is untouched):

\tfrac{1}{2}\,|0\rangle\big(|g(0)\rangle + |g(1)\rangle\big) \;+\; \tfrac{1}{2}\,|1\rangle\big(|g(0)\rangle - |g(1)\rangle\big).

What is the probability of measuring 0? The |0\rangle part carries the (unnormalised) junk vector \tfrac12(|g(0)\rangle + |g(1)\rangle), so

P(0) = \tfrac{1}{4}\,\big\| |g(0)\rangle + |g(1)\rangle \big\|^2 = \tfrac{1}{4}\big(1 + 1 + 2\,\mathrm{Re}\langle g(0)|g(1)\rangle\big) = \tfrac{1}{4}(2 + 0) = \tfrac{1}{2}.

Compare the clean case: P(0) fell from 1 to \tfrac12, and by the same arithmetic P(1) rose from 0 to \tfrac12. The interference is simply gone — a fair coin. The culprit is visible in the algebra: the interference lived entirely in the cross term 2\,\mathrm{Re}\langle g(0)|g(1)\rangle, and orthogonal junk sets it to zero. The junk register is a perfect which-path record: because |g(0)\rangle and |g(1)\rangle are distinguishable, the two paths can no longer be "the same outcome reached two ways", and quantum mechanics refuses to interfere them. Nobody measured anything — the mere existence of the record is enough. (This is decoherence in miniature, with your own work register playing the environment.)

The fix: Bennett's trick, promoted to unitaries

You met the cure in the classical half of this course, where it saved memory and heat. Run it now as a quantum circuit. Let U_f be the (garbage-producing) reversible circuit that computes f into a work register: U_f|x\rangle|0\rangle_w = |x\rangle|f(x), g(x)\rangle_w. Sandwich a copy between U_f and its exact inverse U_f^\dagger (which exists and is just the same gates, conjugated and reversed — unitaries always rewind):

|x\rangle\,|0\rangle_w\,|c\rangle_{\text{out}} \;\xrightarrow{\,U_f\,}\; |x\rangle\,|f(x), g(x)\rangle_w\,|c\rangle \;\xrightarrow{\,\text{CNOTs}\,}\; |x\rangle\,|f(x), g(x)\rangle_w\,|c \oplus f(x)\rangle \;\xrightarrow{\,U_f^\dagger\,}\; |x\rangle\,|0\rangle_w\,|c \oplus f(x)\rangle.

Follow the work register: computed, consulted, then run backwards to |0\rangle_w. Crucially, this happens in every branch of a superposition simultaneously — after U_f^\dagger, the work register is in the same state |0\rangle_w regardless of x, so it factors out of the sum. No which-path record survives; the cross terms come back; interference works again. The net effect is the clean oracle |x\rangle|c\rangle \mapsto |x\rangle|c \oplus f(x)\rangle of the previous lesson, with the garbage handled invisibly inside.

Where you will meet it (everywhere)

Open any serious quantum algorithm and this sandwich is load-bearing. A Grover oracle that checks "is x a solution?" typically evaluates a chain of classical predicates into ancillas, flips the phase or answer qubit, then must uncompute the ancillas — otherwise the amplitude amplification, which is one giant interference pattern over all x, silently degrades into noise. Shor's algorithm computes a^x \bmod N through long towers of reversible arithmetic, and every intermediate sum, carry and product is uncomputed before the Fourier transform reads out the period — junk entangled with x would wash out precisely the periodic interference the algorithm exists to detect. The price is honest and familiar from Bennett's classical accounting: roughly twice the gates (forward plus backward) plus the copying CNOTs, in exchange for a work register you can reuse and interference you can trust.

It is worth savouring how exactly the classical and quantum stories rhyme. Bennett invented compute–copy–uncompute in 1973 to show reversible Turing machines need not drown in tape: junk cost space, and erasing it cost heat. Two decades later the quantum algorithm designers reached for the identical circuit — same boxes, same order — because junk now cost coherence. Nothing about the construction changed; only the failure mode it prevents. That is the deepest sense in which this course has been "secretly about quantum computing" all along: the discipline of never strewing garbage, learnt for thermodynamic reasons, turns out to be the exact discipline quantum mechanics enforces on pain of wrong answers. Physics billed classical waste in joules; quantum mechanics bills it in probability.

A tempting shortcut: the junk register is in the way, so just measure it and throw the result in a drawer. Fatal. Measuring the junk collapses the very superposition you were preserving: reading g(x) reveals which-path information (often enough to deduce x itself), so the state collapses onto the branches consistent with the observed junk — for fully distinguishing garbage, onto a single |x\rangle. Your carefully built superposition over 2^n inputs becomes one classical evaluation. Nor does ignoring the junk help: unread orthogonal junk kills the cross terms just as thoroughly, as the arithmetic above showed. There is no third option. Uncomputation — actively running the junk back to |0\rangle — is the only clean exit.