Every quantum gate is a unitary, and every unitary is reversible — you can always run it backward. But ordinary logic isn’t: an AND gate throws information away. So how do we run classical functions on a quantum computer? We make them reversible — with the help of scratch qubits we borrow and then must give back perfectly clean.
↩ before you start · keep these handy
·From QI Ch. 1: a classical bit and the idea of a logic gate (AND, OR, NOT, XOR).
·From QC 02: Toffoli flips its target only when both controls are 1 — a reversible AND.
·From QC 03: an oracle U f writes f(x) onto a wire; kickback turns that into a phase.
🔑 symbol decoder · every new mark, in plain words
reversibleyou can recover the input from the output — the map is one-to-one (a bijection).irreversibletwo inputs collapse to one output, so information is lost (e.g. AND: three inputs all give 0).ancillaa borrowed scratch qubit, started in |0⟩, used as workspace.garbageleftover junk an ancilla holds after a computation — if not cleaned, it wrecks interference.uncomputerun the scratch-making steps backward to reset the ancilla to a clean |0⟩.U f · oraclethe reversible black box |x⟩|y⟩ → |x⟩|y⊕f(x)⟩ that an algorithm queries.
feel
Why losing a bit is forbidden
A unitary is a rigid rotation — it can always be spun back. An AND gate can’t: see a 0 come out and you genuinely cannot tell which of three inputs produced it. That lost information has nowhere to live in a reversible machine. The fix is to never throw a bit away — carry the inputs along, and write the answer into fresh space rather than overwriting.
🧾 everyday picture
Borrow a friend’s whiteboard for a side calculation. You jot working notes, copy out the final answer onto your own page — then you must erase the whiteboard before handing it back, or the next person inherits your scribbles. An ancilla is that whiteboard: scratch space you borrow clean and must return clean. Forgetting to wipe it (leaving garbage) silently ruins the quantum interference you were counting on.
recapUnitaries are reversible; classical AND isn’t, so we carry inputs along and use clean scratch space.
play
Compute, copy, uncompute
Watch the three-step dance that keeps an ancilla clean. We compute f(x) = x₀ AND x₁ into a scratch qubit, copy the answer to an output, then run the computation backward so the scratch returns to |0⟩. Step through it and watch the ancilla light up clean at the end.
▸ uncomputation stepperf(x) = x₀ AND x₁
input x:
{{ r.label }}
{{ r.role }}
{{ r.v }}
{{ r.note }}
{{ c.label }}
{{ status }}
recapCompute into scratch, copy the answer out, then uncompute — the ancilla ends in clean |0⟩.
math
Embed any function, reversibly
A bare function f might be many-to-one. But this always defines a reversible (in fact self-inverse) map — the standard oracle:
U f : |x⟩|y⟩ → |x⟩|y ⊕ f(x)⟩
apply it twice → |x⟩|y ⊕ f(x) ⊕ f(x)⟩ = |x⟩|y⟩ (its own inverse)
It keeps x around (so nothing is lost) and writes the answer with XOR (so it’s undoable). Complicated f’s need scratch qubits, which come out holding garbage g(x). The Bennett trick cleans them:
compute → |x⟩|g(x)⟩|f(x)⟩ · copy out · uncompute → |x⟩|0⟩|f(x)⟩
✎ worked example · AND, made reversible by Toffoli
1.plain AND: (1,0)→0 and (0,1)→0 and (0,0)→0 — three inputs, one output: irreversible.
2.Toffoli: (a, b, c) → (a, b, c ⊕ a·b). Keep a and b; write AND into a third wire.
3.start the third wire at c = 0: output is (a, b, a·b) — the AND, with inputs preserved.
4.now it’s a bijection on 8 states; run Toffoli again to undo it. Reversible AND. ✓
recapU f keeps x and XORs the answer in; the Bennett trick uncomputes garbage back to |0⟩.
⚠ common misconceptions
“Leftover garbage is harmless — we just ignore those qubits.” No. If scratch qubits stay entangled with the answer, they secretly record “which branch” happened and destroy the interference the algorithm needs. They must be uncomputed.
“Reversible computing wastes qubits forever.” The whole point of uncomputation is the opposite — ancillas are recycled back to |0⟩ and reused. You pay a modest, temporary overhead, not a permanent one.
“The oracle is magic that already knows the answer.” An oracle is just a normal reversible circuit for f that we draw as a box to count queries. Algorithms are judged by how few times they open it.
✓ you can now
✓say why unitaries are reversible and why AND is not
✓build the reversible oracle U f|x⟩|y⟩ = |x⟩|y⊕f(x)⟩ and show it’s self-inverse
✓run the compute–copy–uncompute pattern to free an ancilla
✓explain why uncomputed garbage would kill quantum interference