# 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: 1. **State and motivate** Landauer's principle ($\ge kT\ln 2$ of heat per erased bit) and connect logical irreversibility to thermodynamic cost. 2. **Define** logical reversibility as bijectivity of the gate's input→output map, and explain why irreversible gates lose information. 3. **Write the truth tables** of NOT, CNOT, Toffoli (CCNOT), and Fredkin (CSWAP), and verify each is a bijection (permutation). 4. **Argue** that Toffoli is universal for reversible classical computation. 5. **Embed** any irreversible function reversibly using ancillas and **uncomputation** (garbage management), and quantify the qubit/bit overhead. 6. **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: 1. **Compute** $f$ forward, producing scratch: $(x, 0, 0)\to(x, g(x), f(x))$. 2. **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))$. 3. **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: 1. **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. 2. **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](../../term-2-qc-core/c01-gates-circuits/01-single-qubit-gates.md) 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. 3. **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}})$: 1. $\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)$. 2. 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: 3. **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. ```python """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](../../appendix/B-python-numpy-refresher.md)). 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.
--- ## Further Reading - **[NC §3.2.5]** Nielsen & Chuang — reversible computation, Landauer's principle, the Toffoli and Fredkin gates, universality, and the embedding/uncomputation construction. The closest match to this lesson and the bridge into Part II's quantum circuits. - **[Bar95]** Barenco et al., "Elementary gates for quantum computation" — Toffoli/CCNOT decompositions and the gate-universality results, where these classical gates become quantum. - **[Ben73]** C. H. Bennett, "Logical reversibility of computation" — the original ancilla+uncomputation argument that reversibility costs only polynomial overhead. (See [NC §3.2.5] for the textbook account.) - **[AB §6]** Arora & Barak — the circuit model these reversible circuits specialize, for the complexity-preservation claim. --- ← Prev: [Complexity Classes](02-complexity-classes.md) · Up: [Term 0](../README.md) · Next: [The State Postulate](../../term-1-quantum-mechanics/c01-postulates/01-state-postulate.md) →