Uncomputation

Uncomputation runs the inverse of the gates that produced a temporary value, in reverse order, so helper qubits return to |0⟩ and stop being entangled with the data you care about. Resetting them instead is not equivalent: reset is non-unitary and destroys the phase relationships that later interference depends on.

What problem does uncomputation solve?

Real circuits use scratch space. An ancilla is a helper qubit that starts in |0⟩, holds a temporary value mid-computation, and should end in |0⟩ so it can be reused. The trap is what happens in between.

When a controlled gate writes a temporary value onto an ancilla, the ancilla usually becomes entangled with the data qubits: the joint state correlates them so strongly that neither qubit can be described on its own any more. An ancilla left in that condition is called garbage — a leftover record of which computational branch produced it.

Why does garbage matter? Quantum algorithms get their power from interference: amplitudes from different branches adding together or cancelling out. Branches can only interfere if they are identical in every qubit — amplitudes add only when they flow into the same final outcome, and two branches that differ on even one helper qubit lead to different outcomes, so their amplitudes never meet. A garbage qubit that remembers "branch A" versus "branch B" makes the branches distinguishable, and the interference silently stops working.

You cannot just overwrite the ancilla — the previous lesson, Reversible Computation, showed that no gate erases information. The fix is uncomputation: run the inverse of the gates that created the temporary value, in reverse order, so the ancilla coherently returns to |0⟩.