Reversible Computation

Ordinary logic forgets: an AND gate turns two bits into one, and the lost bit must go somewhere — Landauer showed it goes into heat. If we forbid forgetting, computation becomes a permutation of states, information-preserving and (in principle) dissipationless. This reversible model is not a curiosity: it is the exact classical shadow of quantum computing, where every gate is unitary — hence invertible — by the laws of physics. The CNOT and Toffoli gates you build here reappear, unchanged, as quantum gates in Term 2.

Learning Objectives

By the end of this lesson you will be able to:

State and motivate Landauer's principle ( $\ge kT\ln 2$ of heat per erased bit) and connect logical irreversibility to thermodynamic cost.
Define logical reversibility as bijectivity of the gate's input→output map, and explain why irreversible gates lose information.
Write the truth tables of NOT, CNOT, Toffoli (CCNOT), and Fredkin (CSWAP), and verify each is a bijection (permutation).
Argue that Toffoli is universal for reversible classical computation.
Embed any irreversible function reversibly using ancillas and uncomputation (garbage management), and quantify the qubit/bit overhead.
Explain the bridge to quantum: quantum gates are unitary $\Rightarrow$ reversible; CNOT and Toffoli are quantum gates; reversibility underlies no-cloning and the structure of Term 2.

Intuition

Watch an AND gate run: inputs $(1,0)$ give output $0$ , but so do $(0,0)$ and $(0,1)$ . From the output alone you cannot reconstruct the input — the gate is 2-to-1, it merges states and destroys information. Rolf Landauer's 1961 insight: this logical erasure is not free. Merging two possible states into one halves the system's state space, lowering its entropy by $k\ln 2$ — and the Second Law demands that entropy be dumped into the environment as heat, $\ge kT\ln 2$ per bit erased. Logical irreversibility implies thermodynamic irreversibility.

The escape hatch: never merge. If a gate's map is a bijection — every output comes from exactly one input — no information is lost, the computation can be run backward, and Landauer's bound for the logic itself drops to zero. The price is that we cannot literally implement AND as a 2-bit→1-bit gate; we must keep enough extra wires to stay invertible. That bookkeeping — ancillas (scratch bits) and uncomputation (cleaning up scratch so it doesn't accumulate as "garbage") — is the entire craft of reversible computing.

Why a quantum course cares: in quantum mechanics, closed-system evolution is unitary, and unitary operators are invertible ( $U^{-1}=U^\dagger$ ). So every quantum gate is automatically reversible — there is no quantum AND-as-written, no quantum erasure mid-circuit. Reversible classical logic is exactly the sandbox where you learn to compute without forgetting, before the complex amplitudes of Term 1–2 arrive. The Toffoli gate you meet here is, bit-for-bit, the classical core of a quantum universal gate set.

Theory

1. Landauer's principle

Landauer's principle. Erasing one bit of information in a computation at temperature $T$ dissipates at least
$E_{\min} \;=\; k_B\, T \ln 2$
of energy as heat, where $k_B$ is Boltzmann's constant.

Why $\ln 2$ . A bit has two equally likely states; its information entropy is $\log_2 2 = 1$ bit, or $S = k_B\ln 2$ in thermodynamic (nat) units. Erasure — forcing the bit to a known value $0$ regardless of its prior value — collapses two microstates into one, reducing the bit's entropy by $\Delta S = k_B \ln 2$ . By the Second Law, the total entropy of (bit + environment) cannot decrease, so the environment must absorb at least $\Delta S$ , releasing heat $Q = T\,\Delta S = k_B T \ln 2$ . At room temperature $T\approx 300\,\mathrm K$ this is a tiny $\approx 2.9\times10^{-21}\,\mathrm J$ — but it is a floor no clever engineering can undercut for an irreversible erasure, and it has been confirmed experimentally [NC §3.2.5].

The lever for computing: logically reversible operations need not erase, so they are not subject to the $kT\ln 2$ floor — at least not from the logic. (Real devices still dissipate for other engineering reasons; the principle sets the fundamental limit.) This is the thermodynamic motivation for studying reversible computation, due to Bennett.

2. Logical reversibility

A gate computing $g:\{0,1\}^n\to\{0,1\}^m$ is logically reversible iff $g$ is a bijection — equivalently, $n=m$ and $g$ is a permutation of $\{0,1\}^n$ , so the input is uniquely recoverable from the output via $g^{-1}$ .

NOT ( $x\mapsto \lnot x$ ) is reversible: it is its own inverse, a 2-element permutation.
AND, OR, NAND, XOR (as $2\to1$ maps) are not reversible: they are 2-to-1, hence not injective, hence lose information. (NAND's universality — Lesson 1 — is unrelated to its irreversibility.)

The key structural theorem: any $n$ -bit reversible gate is a permutation of the $2^n$ bit-strings, and conversely every permutation is a reversible gate. Reversible computation is therefore the study of which permutations are realizable from a small gate set — the direct classical analogue of "which unitaries are realizable from a universal quantum gate set" (Term 2.2).

3. The reversible gate zoo

We build reversibility by adding control wires that are passed through untouched, flipping a target only on certain control patterns.

NOT — 1 bit

\begin{array}{c|c} x & \text{NOT}\\\hline 0 & 1\\ 1 & 0 \end{array}

A transposition; trivially a bijection.

CNOT (controlled-NOT) — 2 bits

Control $c$ , target $t$ ; flip $t$ iff $c=1$ . Output $(c,\ t\oplus c)$ .

\begin{array}{cc|cc} c & t & c' & t'\\\hline 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 1\\ 1 & 0 & 1 & 1\\ 1 & 1 & 1 & 0 \end{array}

The map $(c,t)\mapsto(c,t\oplus c)$ is its own inverse (apply twice: $t\oplus c\oplus c=t$ ), so CNOT is reversible. With $t=0$ fixed it computes $(c,0)\mapsto(c,c)$ — a fan-out/copy of a classical bit into a fresh wire. (Note: this copies classical bits only; the quantum no-cloning theorem says the same circuit cannot copy an unknown superposition — more below.)

Toffoli / CCNOT (controlled-controlled-NOT) — 3 bits

Two controls $a,b$ , target $c$ ; flip $c$ iff $a=b=1$ . Output $(a,\ b,\ c\oplus(a\land b))$ .

\begin{array}{ccc|ccc} a & b & c & a' & b' & c'\\\hline 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 1\\ 0 & 1 & 0 & 0 & 1 & 0\\ 0 & 1 & 1 & 0 & 1 & 1\\ 1 & 0 & 0 & 1 & 0 & 0\\ 1 & 0 & 1 & 1 & 0 & 1\\ 1 & 1 & 0 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1 & 0 \end{array}

Again self-inverse. The magic: set the target $c=0$ and Toffoli outputs $(a,b,a\land b)$ — a reversible AND with the inputs preserved. Set $c=1$ with the same controls and you get $a\land b$ negated... and combined with the bit-copy from CNOT, this is enough for universality.

Fredkin / CSWAP (controlled-SWAP) — 3 bits

Control $c$ ; swap targets $x,y$ iff $c=1$ .

\begin{array}{ccc|ccc} c & x & y & c' & x' & y'\\\hline 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 1\\ 0 & 1 & 0 & 0 & 1 & 0\\ 0 & 1 & 1 & 0 & 1 & 1\\ 1 & 0 & 0 & 1 & 0 & 0\\ 1 & 0 & 1 & 1 & 1 & 0\\ 1 & 1 & 0 & 1 & 0 & 1\\ 1 & 1 & 1 & 1 & 1 & 1 \end{array}

Self-inverse, and conservative: it preserves the number of $1$ s (Hamming weight) in $(x,y)$ , which models a billiard-ball / charge-conserving physical implementation. With $y=0$ it computes $(c,x,0)\mapsto(c,\ c\land\lnot? ...)$ — concretely $x'=c\land x$ is not quite it; rather with $x=1,y=0$ it routes the $1$ to $x'$ or $y'$ depending on $c$ , realizing AND and fan-out (Example 1).

4. Toffoli is universal for reversible computation

Theorem. The Toffoli gate (together with the ability to introduce constant ancilla bits set to $0$ or $1$ and to ignore output "garbage" bits) is universal for reversible classical computation: any Boolean function can be computed by a circuit of Toffoli gates [NC §3.2.5], [Bar95].

Proof sketch. It suffices to realize a functionally complete set (Lesson 1) reversibly with Toffolis:

AND: $\text{TOFFOLI}(a,b,0) = (a,b,\ a\land b)$ . The third output is $a\land b$ .
NOT: $\text{TOFFOLI}(1,1,x) = (1,1,\ x\oplus 1) = (1,1,\lnot x)$ — feed two ancillas set to $1$ . (Or use a bare NOT gate, itself a special Toffoli with the controls hardwired.)
FANOUT/COPY: $\text{TOFFOLI}(a,1,0) = (a,1,\ a\land 1) = (a,1,a)$ — copy $a$ to a fresh wire.

Since $\{\text{AND}, \text{NOT}\}$ is complete (it gives NAND, hence everything — Lesson 1), and we can COPY to feed a bit to multiple gates, any Boolean circuit can be rebuilt out of Toffolis. The ancillas supply the needed constants and scratch; some output wires hold intermediate "garbage" we clean up next. $\blacksquare$

A subtlety worth stating: no $2$ -bit reversible gate is universal in this sense (the $2$ -bit reversible gates are all linear over $\mathbb F_2$ — XOR-type — and cannot generate the nonlinear AND). You genuinely need a $3$ -bit gate like Toffoli. This mirrors the quantum fact that entangling two-qubit gates plus single-qubit gates are needed for quantum universality (Term 2.2).

5. Embedding irreversible functions: ancillas, garbage, uncomputation

Given an arbitrary $f:\{0,1\}^n\to\{0,1\}^m$ (possibly many-to-one, hence irreversible), how do we compute it reversibly? The standard construction makes $f$ a permutation on a larger space by carrying the input along:

U_f:\quad (x,\ y) \;\longmapsto\; (x,\ y\oplus f(x)), \qquad x\in\{0,1\}^n,\ y\in\{0,1\}^m.

This is a bijection for any $f$ — its own inverse, since $y\oplus f(x)\oplus f(x)=y$ — because we keep $x$ . Setting $y=0$ reads out $f(x)$ in the second register: $(x,0)\mapsto(x,f(x))$ . This is exactly the oracle/query model of Term 3.1 (which is why $\oplus$ appears everywhere in quantum algorithms).

But a circuit computing $f(x)$ usually generates intermediate scratch $g(x)$ ("garbage") on ancilla wires:

(x,\ 0_{\text{anc}},\ 0_{\text{out}}) \xrightarrow{\ \text{compute}\ } (x,\ g(x),\ f(x)).

Garbage is a problem in two ways: it wastes wires, and — critically for quantum — if those ancillas stay entangled with the answer register, interference (the source of quantum speedup) is spoiled. Bennett's uncomputation trick removes it:

Compute $f$ forward, producing scratch: $(x, 0, 0)\to(x, g(x), f(x))$ .
Copy out the answer to a fresh clean register with CNOTs: $(x, g(x), f(x), 0)\to(x, g(x), f(x), f(x))$ .
Uncompute by running the forward circuit in reverse (every reversible gate has an inverse), which restores the scratch to $0$ and erases the working copy of $f(x)$ : $(x,\ g(x),\ f(x),\ f(x)) \xrightarrow{\ \text{reverse compute}\ } (x,\ 0,\ 0,\ f(x)).$

Net effect $(x,0,0,0)\mapsto(x,0,0,f(x))$ : the answer survives, all scratch is returned to $0$ and can be reused, and there is no leftover garbage. The cost is roughly double the gate count (forward + reverse) and a constant-factor increase in wires — a small, polynomial overhead. Crucially, any computation can be made reversible with at most polynomial blow-up in time and space [Ben73], so reversibility costs us nothing in complexity terms — it does not move problems between the classes of the previous lesson.

6. The bridge to quantum computing

This is the payoff. Three facts lock reversible classical logic to quantum computing:

Unitary ⇒ reversible. A quantum gate is a unitary $U$ with $U^\dagger U = I$ , so $U^{-1}= U^\dagger$ always exists. Every quantum circuit is therefore reversible; there is no built-in erasure. Mid-circuit "forgetting" only happens at measurement, which is the one non-unitary, irreversible step (Term 1.3). Everything before it is a permutation-like, invertible evolution — exactly the regime you practiced here.
CNOT and Toffoli are quantum gates. Read the truth tables above as the action on computational basis states $\lvert\cdot\rangle$ and they define unitary permutation matrices:
$\text{CNOT}\,\lvert c,t\rangle = \lvert c,\ t\oplus c\rangle, \qquad \text{TOFFOLI}\,\lvert a,b,c\rangle = \lvert a,b,\ c\oplus(a\land b)\rangle .$
These same gates run quantum circuits in Term 2.1 · Single-Qubit Gates and beyond — CNOT is the canonical entangler, Toffoli is the workhorse of arithmetic and oracles. The matrices are exactly the permutation matrices of the truth tables.
No-cloning is reversibility's quantum twist. CNOT copies a classical bit ( $\lvert c,0\rangle\to\lvert c,c\rangle$ ) — yet the no-cloning theorem (Term 2.2) proves no unitary can copy an arbitrary unknown state $\alpha\lvert0\rangle+\beta\lvert1\rangle$ . The resolution: linearity. CNOT on a superposition control gives $\alpha\lvert00\rangle+\beta\lvert11\rangle$ (an entangled Bell-type state), not the product $(\alpha\lvert0\rangle+\beta\lvert1\rangle)^{\otimes2}$ . Reversibility is necessary for unitarity, but unitarity also forbids cloning — a constraint with no classical analogue, and a recurring theme from Term 2 onward.

So the reversible-computing skills here — control wires, ancillas, uncomputation, thinking of computation as a permutation — are not a detour. They are the literal classical substrate of quantum circuits, learned without yet needing complex amplitudes.

Worked Examples

Example 1 — Fredkin computes AND, OR, and fan-out

Set the control to the data and use a constant ancilla. Recall $\text{FREDKIN}(c,x,y) = (c,\ x',\ y')$ swaps $x,y$ iff $c=1$ , so $x' = (\lnot c)\,x \lor c\,y$ and $y' = (\lnot c)\,y \lor c\,x$ .

AND ( $c\land x$ ): feed $(c,\ x,\ 0)$ . Then $y' = (\lnot c)\cdot 0 \lor c\cdot x = c\land x$ . The third output is $c\land x$ .
OR: feed $(c,\ 1,\ x)$ . Then $x' = (\lnot c)\cdot 1 \lor c\cdot x = \lnot c \lor (c\land x) = \lnot c \lor x$, and the first kept wire... cleaner is to use De Morgan with AND/NOT, but the AND realization plus a NOT suffices via universality.
FAN-OUT of $c$ : feed $(c,\ 1,\ 0)$ . Then $x' = (\lnot c)\cdot1 \lor c\cdot0 = \lnot c$ and $y' = (\lnot c)\cdot0 \lor c\cdot1 = c$ . Outputs carry $c$ and $\lnot c$ — both copies recoverable.

Fredkin is conservative (Hamming-weight–preserving), so these come "for free" thermodynamically. This is why Fredkin models billiard-ball computing. (Toffoli is the more common building block because its AND is more direct; we verify both in code.)

Example 2 — Uncomputation on a 2-bit function

Let $f(x_1,x_2) = (x_1\land x_2)\oplus(\lnot x_1)$ , computed with one scratch wire. Forward circuit on registers $(x_1, x_2,\ a{=}0_{\text{scratch}},\ o{=}0_{\text{out}})$ :

$\text{TOFFOLI}(x_1,x_2,a)$ : now $a = x_1\land x_2$ . State $(x_1,x_2,\ x_1\land x_2,\ 0)$ .
CNOT $a\to o$ : $o = x_1\land x_2$ . Then NOT-controlled-by- $\lnot x_1$ via $\text{TOFFOLI}(\bar{}, \dots)$ — concretely, flip $o$ when $x_1=0$ using an X-then-Toffoli trick. After this, $o = (x_1\land x_2)\oplus\lnot x_1 = f$ .

Now the scratch $a=x_1\land x_2 \ne 0$ is garbage entangled with the inputs. Uncompute:

Reverse step 1: $\text{TOFFOLI}(x_1,x_2,a)$ again (self-inverse) resets $a\to 0$ .

Final state: $(x_1, x_2,\ 0,\ f(x_1,x_2))$ — inputs intact, scratch clean, answer in $o$ . We do not uncompute $o$ , since it holds the wanted result; we uncompute only the scratch. The code below implements this end-to-end and asserts the scratch returns to $0$ for all four inputs.

Hands-on (Python)

Self-contained, dependency-free. We represent each gate as a permutation of bit-strings and verify reversibility by checking the permutation is a bijection (and self-inverse). Then we demonstrate uncomputation cleaning up an ancilla.

"""Reversible Computation — gates as bit-string permutations (plain Python)."""

from itertools import product

# ---------------------------------------------------------------------------
# Represent an n-bit state as a tuple of ints in {0,1}. A reversible gate is a
# function state->state; we verify it is a BIJECTION over all 2**n states.
# ---------------------------------------------------------------------------

def NOT(bits):                       # 1-bit:  x -> ¬x
    (x,) = bits
    return (1 - x,)

def CNOT(bits):                      # 2-bit:  (c, t) -> (c, t XOR c)
    c, t = bits
    return (c, t ^ c)

def TOFFOLI(bits):                   # 3-bit:  (a, b, c) -> (a, b, c XOR (a AND b))
    a, b, c = bits
    return (a, b, c ^ (a & b))

def FREDKIN(bits):                   # 3-bit:  (ctrl, x, y) -> swap x,y if ctrl=1
    ctrl, x, y = bits
    return (ctrl, y, x) if ctrl == 1 else (ctrl, x, y)

def all_states(n):
    return list(product((0, 1), repeat=n))

def is_reversible(gate, n):
    """A gate is reversible iff it permutes the 2**n states bijectively."""
    images = [gate(s) for s in all_states(n)]
    return len(set(images)) == 2 ** n           # no two inputs collide => bijection

def is_self_inverse(gate, n):
    return all(gate(gate(s)) == s for s in all_states(n))

for name, gate, n in [("NOT", NOT, 1), ("CNOT", CNOT, 2),
                      ("TOFFOLI", TOFFOLI, 3), ("FREDKIN", FREDKIN, 3)]:
    rev = is_reversible(gate, n)
    inv = is_self_inverse(gate, n)
    print(f"{name:8s} reversible={rev}  self-inverse={inv}")
    assert rev and inv

# Contrast: AND as a 2->1 map is NOT reversible (it collides inputs).
def AND_irreversible(bits):
    a, b = bits
    return (a & b,)                               # 2 bits in, 1 bit out
images = [AND_irreversible(s) for s in all_states(2)]
print(f"\nAND (2->1): distinct outputs = {len(set(images))} of 4 inputs "
      f"-> reversible={len(set(images)) == 4}")   # collides -> not reversible


# ---------------------------------------------------------------------------
# Toffoli is universal: realize AND, NOT, COPY as the lesson's special cases.
# ---------------------------------------------------------------------------
print("\nToffoli realizing classical gates:")
print("  AND(a,b)  via TOFFOLI(a,b,0):", [TOFFOLI((a, b, 0))[2]
                                          for a, b in all_states(2)])   # a AND b
print("  NOT(x)    via TOFFOLI(1,1,x):", [TOFFOLI((1, 1, x))[2]
                                          for (x,) in all_states(1)])   # ¬x
print("  COPY(a)   via TOFFOLI(a,1,0):", [TOFFOLI((a, 1, 0))[2]
                                          for (a,) in all_states(1)])   # = a


# ---------------------------------------------------------------------------
# Uncomputation: compute f(x1,x2) = (x1 AND x2) using a SCRATCH ancilla, copy
# the answer to an output wire, then run the scratch-producing gate in REVERSE
# to clean the ancilla back to 0. Registers: (x1, x2, scratch, out).
# ---------------------------------------------------------------------------
def compute_with_uncompute(x1, x2):
    a, o = 0, 0                                   # scratch=0, out=0
    # 1. forward: scratch <- x1 AND x2  (Toffoli on (x1,x2,scratch))
    _, _, a = TOFFOLI((x1, x2, a))
    # 2. copy answer to out via CNOT(scratch -> out)
    _, o = CNOT((a, o))                           # out = scratch = x1 AND x2
    # 3. UNCOMPUTE: reverse step 1 (Toffoli is self-inverse) -> scratch back to 0
    _, _, a = TOFFOLI((x1, x2, a))
    return x1, x2, a, o                           # expect scratch a == 0

print("\nUncomputation (x1, x2, scratch, out):")
for x1, x2 in all_states(2):
    res = compute_with_uncompute(x1, x2)
    print(f"  in=({x1},{x2}) -> {res}   out=f={res[3]}  scratch_clean={res[2]==0}")
    assert res[2] == 0, "scratch must be uncomputed back to 0"
    assert res[3] == (x1 & x2), "output must equal f(x1,x2)"
print("Scratch returns to 0 for all inputs; answer preserved. ✓")

Expected output:

NOT      reversible=True  self-inverse=True
CNOT     reversible=True  self-inverse=True
TOFFOLI  reversible=True  self-inverse=True
FREDKIN  reversible=True  self-inverse=True

AND (2->1): distinct outputs = 3 of 4 inputs -> reversible=False

Toffoli realizing classical gates:
  AND(a,b)  via TOFFOLI(a,b,0): [0, 0, 0, 1]
  NOT(x)    via TOFFOLI(1,1,x): [1, 0]
  COPY(a)   via TOFFOLI(a,1,0): [0, 1]

Uncomputation (x1, x2, scratch, out):
  in=(0,0) -> (0, 0, 0, 0)   out=f=0  scratch_clean=True
  in=(0,1) -> (0, 1, 0, 0)   out=f=0  scratch_clean=True
  in=(1,0) -> (1, 0, 0, 0)   out=f=0  scratch_clean=True
  in=(1,1) -> (1, 1, 0, 1)   out=f=1  scratch_clean=True
Scratch returns to 0 for all inputs; answer preserved. ✓

The AND(a,b) = [0,0,0,1] line reads off the truth table of AND from Toffoli's third output, and the uncomputation block shows the scratch wire faithfully returning to $0$ — the discipline that keeps quantum ancillas disentangled.

Linking to Appendix B. The same gates appear there as matrices (e.g. the explicit CNOT in Appendix B §5). A permutation of basis strings is a permutation matrix — that is precisely why these classical reversible gates are already valid unitary quantum gates.

Exercises

1. (Easy) Self-inverse check. Verify by hand that Toffoli is its own inverse: compute $\text{TOFFOLI}(\text{TOFFOLI}(a,b,c))$ symbolically.

Solution

$\text{TOFFOLI}(a,b,c) = (a,b,\,c\oplus(a\land b))$ . Applying again, the controls $a,b$ are unchanged, so the target becomes $\big(c\oplus(a\land b)\big)\oplus(a\land b) = c\oplus\big((a\land b)\oplus(a\land b)\big) = c\oplus 0 = c $. Thus$ \text{TOFFOLI}^2 = \text{Id} $: self-inverse.$ \blacksquare$

2. (Easy–Medium) Landauer arithmetic. A chip irreversibly erases $10^{12}$ bits per second at $T=300\,\mathrm K$ . What is the minimum power dissipated by erasure alone? ($k_B = 1.38\times10^{-23}, \mathrm{J/K}$.)

Solution

Per bit: $k_B T\ln 2 = (1.38\times10^{-23})(300)(0.693) \approx 2.87\times10^{-21}\,\mathrm J$ . Times $10^{12}$ erasures/s: $P_{\min}\approx 2.9\times10^{-9}\,\mathrm W \approx 2.9\,\mathrm{nW}$ . Tiny — real chips dissipate ~ $10^9$ times more for other reasons — but it is a hard floor for irreversible operation, and exactly $0$ (from logic) for reversible operation.

3. (Medium) SWAP from CNOTs. Show that SWAP $(x,y)\mapsto(y,x)$ equals three CNOTs alternating control/target. Verify it is reversible.

Solution

Apply CNOT $_{x\to y}$ , then CNOT $_{y\to x}$ , then CNOT $_{x\to y}$ :

(x,y)\to(x,\,x\oplus y)\to\big((x)\oplus(x\oplus y),\ x\oplus y\big)=(y,\,x\oplus y)\to(y,\ y\oplus(x\oplus y))=(y,x).

Each CNOT is reversible (self-inverse), so their composition is a reversible permutation (it is its own inverse here by symmetry). SWAP itself is obviously a bijection. This identity reappears verbatim for qubits in Term 2. $\blacksquare$

4. (Medium) Why no 2-bit universal reversible gate. Argue that every $2$ -bit reversible gate is "linear" (an affine $\mathbb F_2$ map) and therefore cannot, even with constant ancillas on 2 wires, compute the nonlinear AND. (Hence universality needs $\ge 3$ bits, e.g. Toffoli.)

Solution

The $2$ -bit reversible gates form the symmetric group on $4$ states. The ones realizable as bitwise/control logic — NOT, CNOT, SWAP, and compositions — are all affine over $\mathbb F_2$ : each output bit is a XOR of input bits plus a constant. Affine maps are closed under composition, and composing affine maps with constant-input wires stays affine. But $a\land b$ is nonlinear (its algebraic normal form contains the product term $ab$ ), so no affine circuit produces it. The nonlinearity requires a gate whose action mixes three wires multiplicatively — Toffoli's $c\oplus(a\land b)$ — which is why $3$ bits are necessary for universality. (This is the precise classical shadow of needing two-qubit entangling gates for quantum universality.)

5. (Hard) Garbage and interference. Explain, in terms of the embedding $U_f:(x,0)\mapsto(x,f(x))$ plus uncomputed scratch, why leftover garbage entangled with the answer would ruin a quantum algorithm, even though it is harmless classically.

Solution

Classically, garbage $g(x)$ on idle wires is merely wasted space — the answer $f(x)$ is read out regardless. Quantumly, run $U_f$ on a superposition input $\sum_x\alpha_x\lvert x\rangle$ : without uncomputation the state is $\sum_x\alpha_x\lvert x\rangle\lvert g(x)\rangle\lvert f(x)\rangle$ . The register holding $g(x)$ is entangled with the index $x$ , so distinct branches are distinguishable by their garbage and cannot interfere. Quantum speedups (Deutsch–Jozsa, Shor, Grover) rely precisely on amplitudes for different $x$ interfering in the answer register. Uncomputation resets $g(x)\to 0$ for every branch, yielding $\sum_x\alpha_x\lvert x\rangle\lvert 0\rangle\lvert f(x)\rangle $— the garbage factors out, branches with the same$ f(x)$ recombine, and interference is restored. That is why Bennett's trick is mandatory, not merely tidy, in quantum algorithms (Term 3.1).

6. (Hard) No-cloning vs. CNOT-copy. CNOT maps $\lvert c,0\rangle\to\lvert c,c\rangle$ , seemingly copying $c$ . Reconcile this with the no-cloning theorem by computing CNOT on the superposition control $\lvert\psi\rangle=\alpha\lvert0\rangle+\beta\lvert1\rangle$ and target $\lvert0\rangle$ .

Solution

By linearity of the unitary CNOT,

\text{CNOT}\big((\alpha\lvert0\rangle+\beta\lvert1\rangle)\otimes\lvert0\rangle\big) =\alpha\,\text{CNOT}\lvert00\rangle+\beta\,\text{CNOT}\lvert10\rangle =\alpha\lvert00\rangle+\beta\lvert11\rangle.

A genuine clone would be $\lvert\psi\rangle\otimes\lvert\psi\rangle = \alpha^2\lvert00\rangle+\alpha\beta\lvert01\rangle+\alpha\beta\lvert10\rangle+\beta^2\lvert11\rangle$. These agree only when $\alpha\beta=0$ , i.e. for the basis states $\lvert0\rangle$ or $\lvert1\rangle$ — exactly the classical bits CNOT does copy. For a general superposition CNOT produces an entangled state, not two copies. So CNOT copies in the computational basis but cannot clone an unknown state; no contradiction with no-cloning (proved fully in Term 2.2). $\blacksquare$

Checkpoint

1. State Landauer's principle and the source of the $\ln 2$.

Erasing one bit at temperature $T$ dissipates $\ge k_B T\ln 2$ as heat. The $\ln 2$ is the entropy $k_B\ln 2$ of one bit's two equally likely states; erasure removes that entropy from the bit, and the Second Law forces it into the environment as heat.

2. Define logical reversibility. Is AND reversible? Is CNOT?

A gate is reversible iff its input→output map is a bijection (a permutation of bit-strings). AND ( $2\to1$ ) is not — it is 2-to-1 and loses a bit. CNOT, $(c,t)\mapsto(c,t\oplus c)$ , is a bijection (and self-inverse).

3. How does Toffoli compute a reversible AND, and why is that enough for universality?

$\text{TOFFOLI}(a,b,0)=(a,b,a\land b)$ outputs AND while preserving inputs. With Toffoli also giving NOT (controls $=1$ ) and COPY (one control $=1$ , target $0$ ), and $\{\text{AND},\text{NOT}\}$ being functionally complete, every Boolean function is buildable — Toffoli is universal for reversible computation.

4. What problem does uncomputation solve, and how?

It removes garbage (intermediate scratch entangled with the answer). After computing $f$ forward and copying the answer to a clean register, you run the forward circuit in reverse to reset all scratch ancillas to $0$ , leaving $(x,0,f(x))$ with reusable, disentangled ancillas.

5. Why is every quantum gate reversible?

A quantum gate is a unitary $U$ ( $U^\dagger U=I$ ), so $U^{-1}=U^\dagger$ exists — it is always invertible. Closed-system quantum evolution never erases; the only irreversible step is measurement.

6. CNOT copies a classical bit; why is this not cloning?

On basis states CNOT copies ( $\lvert c,0\rangle\to\lvert c,c\rangle$ ), but by linearity a superposition control yields the entangled $\alpha\lvert00\rangle+\beta\lvert11\rangle$ , not the product $\lvert\psi\rangle\otimes\lvert\psi\rangle$ . Copying basis states is allowed; cloning an unknown superposition is forbidden by no-cloning.

Reversible Computation

Learning Objectives

Intuition

Theory

1. Landauer's principle

2. Logical reversibility

3. The reversible gate zoo

NOT — 1 bit

CNOT (controlled-NOT) — 2 bits

Toffoli / CCNOT (controlled-controlled-NOT) — 3 bits

Fredkin / CSWAP (controlled-SWAP) — 3 bits

4. Toffoli is universal for reversible computation

5. Embedding irreversible functions: ancillas, garbage, uncomputation

6. The bridge to quantum computing

Worked Examples

Example 1 — Fredkin computes AND, OR, and fan-out

Example 2 — Uncomputation on a 2-bit function

Hands-on (Python)

Exercises

Checkpoint

Further Reading