How to implement any classical function as a quantum unitary — understanding information loss, reversible embeddings, garbage bits, and Bennett's uncomputation trick.
Quantum mechanics demands that every computation be undoable
In quantum computing, every operation on qubits is described by a unitary matrix U. Unitaries have a defining property: they are always invertible. Given any output, you can always recover the input by applying U†.
This means every quantum gate is reversible — no information is ever lost. But most classical logic gates (AND, OR, NAND) are irreversible: their outputs have fewer bits than their inputs, so information is destroyed.
To run a classical function f on a quantum computer, we must first find a reversible way to compute f, then implement that reversible circuit as a unitary. This page shows you exactly how.
Seeing why standard logic gates cannot be quantum gates
A gate is reversible if you can always determine the input from the output — the input–output mapping is a bijection. If two different inputs produce the same output, information has been lost and the gate is irreversible.
Information erasure has a physical cost. Rolf Landauer showed in 1961 that erasing one bit of information must dissipate at least kT ln 2 of energy as heat (about 3×10−21 J at room temperature). Irreversible gates destroy information, so they necessarily generate heat. Reversible gates preserve all information and can, in principle, compute with zero energy dissipation. This isn't just a quantum curiosity — it's a fundamental law of physics.
Use the explorer below to see the input→output mapping for different gates. When multiple inputs collapse to the same output (red arrows), that gate is irreversible.
A universal set for reversible classical computation
To avoid information loss, reversible gates keep the number of output bits equal to the number of input bits. The key reversible gates are:
Flips a single bit. Trivially reversible (it's its own inverse).
Controlled-NOT. Flips the target b when the control a is 1. Computes XOR while preserving the control.
Controlled-controlled-NOT. Flips c only when both a and b are 1. Computes AND reversibly.
Controlled-SWAP. Swaps b and c when the control a is 1. Also universal for reversible computation.
Both the Toffoli and Fredkin gates are independently universal for reversible classical computation: any Boolean function can be computed using either one (plus ancilla bits initialized to 0 or 1). Since both gates are unitary, this bridges the gap between classical and quantum computation. In practice, quantum circuits most commonly use the Toffoli decomposition.
The canonical way to make any function f reversible
Given any classical function f : {0,1}n → {0,1}m, the standard trick is to keep the input and XOR the result into an ancilla register:
This is reversible because Uf is its own inverse — applying it twice gives back the original state:
When we set y = 0, the output register stores f(x) directly: |x⟩|0⟩ → |x⟩|f(x)⟩.
Something remarkable happens when we set the ancilla to |−⟩ = (|0⟩ − |1⟩) / √2 instead of |0⟩. For a single-bit function f:
The ancilla stays unchanged in |−⟩, but the input register picks up a phase factor (−1)f(x). This is called phase kickback — the function's value gets "kicked" from the output register into the phase of the input. The ancilla serves as a catalyst.
Phase kickback converts function values into quantum phases, which can then be manipulated by interference. This is the engine behind nearly every quantum algorithm: Deutsch's algorithm, Bernstein-Vazirani, Simon's algorithm, Grover's search, and Shor's factoring all rely on applying Uf with the ancilla in |−⟩ to encode f into phases.
Why intermediate computation ruins quantum interference
The standard embedding Uf looks clean in theory, but implementing it for a complex function requires intermediate computations — temporary ancilla bits used to store partial results. These leftover bits are called garbage.
Consider computing f(a,b,c) = (a ∧ b) ⊕ (b ∧ c). We need two AND operations, each requiring a Toffoli gate with an ancilla:
The result f is correct, but the registers holding a∧b and b∧c are garbage — they were needed for the computation but aren't part of the answer.
Imagine using this circuit in superposition. We want the state on the left, but get the state on the right:
Different branches can interfere — the output register only depends on f(x), and two inputs with the same f(x) combine coherently.
Garbage g(x) differs across branches. Even if f(x₁) = f(x₂), the garbage "tags" each branch uniquely — no interference possible. Tracing out garbage yields a mixed state.
Garbage bits become entangled with the computation. They act as a "which-path" marker, effectively decohering the quantum state. This destroys the speedup that relies on interference between branches of the superposition.
This demo shows a 2-input function where f(0) = f(1) (constant). Without garbage, the two branches combine coherently. With garbage, each branch is "tagged" differently and interference is destroyed.
Compute → Copy → Uncompute: the elegant solution to garbage
Charles Bennett (1973) discovered a beautiful solution: after computing the result, copy it to a clean output register, then reverse the entire computation to erase all garbage. Since the circuit is reversible, running it backwards is always possible.
1Compute — Run the circuit forward. The result appears, but garbage accumulates in ancilla registers.
2Copy — Use CNOTs to copy the result into a fresh output register. This is the only step that writes to the final output.
3Uncompute — Run the circuit backwards (apply each gate in reverse order). All garbage bits return to 0.
Walk through Bennett's trick step by step. Choose a function, toggle the input values, and step through each gate to see garbage appear during the forward computation and then vanish during uncomputation.
The key insight is that copying a classical bit value with CNOT does not create garbage — it just fans out the result. And because the entire forward computation is reversible, we can always run it backwards to clean up. The final state has:
Bennett's trick trades time for space cleanliness: we run the computation forward, then backward — roughly doubling the gate count. But we get a clean reversible implementation with no garbage, which is essential for using Uf inside quantum algorithms where interference must be preserved.
The complete recipe for implementing classical functions as quantum unitaries
Express f using reversible gates (Toffoli + CNOT + NOT), adding ancilla qubits as needed for intermediate values.
Ancilla registers that are non-zero after the forward computation are garbage — they carry information about the input.
Copy the result to a clean output register, then run the computation backwards to erase all garbage.
The resulting clean circuit implements Uf: |x⟩|0⟩ → |x⟩|f(x)⟩ with no extra entanglement. It can now be used inside any quantum algorithm.
If the original irreversible circuit for f uses T gates and S ancilla bits:
More advanced techniques (pebble games, incremental uncomputation) can reduce the overhead, but Bennett's basic trick captures the essential idea.
The Uf embedding and phase kickback are the engine behind nearly every quantum algorithm in this course:
In every case, the function must be implemented as a clean reversible circuit — garbage would destroy the interference these algorithms rely on.
Check your grasp of reversible computation and garbage removal