Reversible Computation

Every logic gate you have ever used throws information away. The AND gate takes two bits and returns one — three of its four inputs map to output $0$ — so watching a $0$ emerge tells you nothing about which input produced it. That lost bit is not a bookkeeping nuisance: Rolf Landauer showed in 1961 that erasing it in contact with a reservoir at temperature $T$ must dump at least $k_B T\ln 2$ of heat into the surroundings, the thermodynamic price of logical irreversibility, independent of the device. Reversible computation is the discipline of never paying that price. It restricts every elementary step to a bijection — a permutation of the configuration space that always sends distinct inputs to distinct outputs — so the input can be reconstructed from the output and no information is ever destroyed. Charles Bennett proved in 1973 that this costs almost nothing in principle: any ordinary computation can be rebuilt from reversible primitives, run, and cleaned up, at modest overhead in extra wires. The reversible gate set is larger than the classical one — the Toffoli (controlled-controlled-NOT) and Fredkin (controlled-SWAP) gates each suffice to simulate all of Boolean logic — but every gate is now a permutation matrix on $2^n$ strings. This classical theory turns out to be the skeleton of quantum computing: a unitary satisfies $U^\dagger U=I$ , so it is invertible by construction, and quantum evolution is reversible whether we like it or not. Running any classical subroutine on a quantum machine therefore means first translating it into this reversible dialect — AND becomes Toffoli, copy becomes CNOT — and carefully erasing the leftover junk.

Key takeaways

Reversible computation restricts logic to bijective maps on the state space: every operation has an inverse, so no information is erased and the computation can be run backwards.
Landauer's principle ties logical irreversibility to physics — erasing one bit at temperature $T$ dissipates at least $k_B T\ln 2\approx 2.87\times10^{-21}\,\mathrm{J}$ at $300\,\mathrm{K}$ — while reversible operations have no such fundamental floor.
Irreversible gates (AND, OR, fan-out) are made reversible by keeping the inputs, giving universal reversible gates like the Toffoli (CCNOT) and Fredkin (controlled-SWAP); an $n$ -bit reversible gate is one of the $(2^n)!$ permutations of the strings.
Quantum gates generalize this: unitarity $U^\dagger U=I$ forces reversibility, and classical permutation matrices are exactly the real $0/1$ unitaries — a measure-zero corner of the continuous group $U(2^n)$ .
Bennett's compute–copy–uncompute returns ancillas to $|0\rangle$ so garbage does not stay entangled with the answer and spoil the interference quantum algorithms depend on.
Key idea: reversibility = bijectivity of the global map; quantum mechanics enforces it through unitarity ( $U^\dagger U=I$ ), so classical logic must be rebuilt as permutations (Toffoli, Fredkin) before it can live inside a quantum circuit.

Where this lives today

Reversible computation became a working constraint the moment people started compiling real quantum programs. Every classical subroutine a quantum algorithm needs — the modular exponentiation at the heart of Shor's factoring, the arithmetic inside Grover oracles, the lookup tables of quantum chemistry — must be synthesized as a reversible circuit of Toffoli and CNOT gates, with all intermediate carries and products uncomputed so the interference in the data register survives. In fault-tolerant architectures the Toffoli is the expensive gate: on the surface code it is not transversal and must be built from magic states, so the Toffoli count (equivalently the T-count, since a Toffoli costs about seven $T$ gates) is the dominant cost metric quantum compilers optimize, and shaving Toffolis out of a quantum adder is worth real physical-qubit-hours. Meanwhile Landauer's bound has moved from principle to measurement: the 2012 Bérut experiment tracked a micron-scale particle in a double-well optical trap and confirmed that erasing its one bit released the predicted $k_B T\ln 2$ , and later single-electron and nanomagnet experiments pushed the test to nanoscale devices. On the classical side, adiabatic and reversible CMOS — and superconducting reversible logic — chase the same target, recovering switching energy instead of dumping it, in the hope of one day computing near the thermodynamic limit Landauer and Bennett drew half a century ago.

The physical picture

Think of a computation as shuffling a deck of cards. A reversible step is a genuine shuffle — a permutation you could undo by shuffling back. An irreversible step like AND is more like throwing cards away: once gone, you cannot deal the original hand again. Reversible computing forbids discarding; if you must set cards aside, you keep them in a garbage register for later clean reinsertion. The first figure draws this contrast at the truth-table level — the AND gate collapsing four inputs onto two outputs, beside the Toffoli merely permuting all eight of its three-bit strings.

Figure

Irreversible AND versus reversible Toffoli: AND maps four inputs onto two outputs, so three inputs collapse onto 0 and the input cannot be recovered, while the Toffoli gate is a bijection of the eight three-bit strings that exchanges only 110 ↔ 111 and leaves the other six fixed

The deep reason quantum computers care is that the laws of motion never throw information away. Schrödinger evolution is a unitary rotation of the state vector, and rotations are invertible; so every quantum gate is a reversible map by birth, and a classical algorithm cannot even be expressed as a unitary until it is translated into this reversible dialect. The bridge between "losing information" and "producing heat" is Landauer's principle: squeezing a two-state phase-space cell into a one-state cell halves the accessible volume, lowering the bit's entropy by $k_B\ln 2$ , and the second law forces that entropy out into the environment as heat $Q\ge k_B T\ln 2$ . The second figure follows one bit through erasure and reads off the number.

Figure

Landauer's principle for one erased bit: an unknown bit occupies two equally likely cells with entropy S = k_B ln2 = 9.57×10⁻²⁴ J/K; resetting it to 0 lowers its entropy to zero and forces at least that much entropy into the reservoir, so at T = 300 K the heat exported is Q ≥ k_B T ln2 = 2.87×10⁻²¹ J

Reversible computation sidesteps this floor entirely — a permutation neither shrinks nor grows the phase-space volume, so its lower bound on dissipation is zero. Two facts round out the picture. First, keeping information alive is not free of space: the price of never erasing is extra wires carrying copies of inputs and intermediate junk, and managing those wires is the central engineering problem. Second, the Pauli $X$ is the reversible NOT, the CNOT is reversible XOR-with-copy, and the Toffoli is the reversible AND — the whole classical reversible gate set sits inside the unitary group as the real permutation matrices, a discrete skeleton around which quantum mechanics wraps continuous amplitudes and phase.

The core equations

The definition is group-theoretic: a reversible gate on $n$ bits is exactly a bijection of the $2^n$ bit strings, an element of the symmetric group. Everything downstream follows from this one identification.

f:\{0,1\}^n \to \{0,1\}^n \ \text{reversible} \iff f \in S_{2^n} \qquad (1)

where: $f$ — the global transition function of the gate or circuit; $\{0,1\}^n$ — the set of $2^n$ length- $n$ bit strings; $S_{2^n}$ — the symmetric group of permutations of $2^n$ objects. The reading: reversibility is injectivity on a finite set, which for equal-size domain and range means bijectivity — the map is a $2^n\times 2^n$ permutation matrix, automatically invertible. Quantum mechanics hands us reversibility for nothing: a gate is a unitary operator, and unitarity says the adjoint is the inverse, so no quantum gate can ever be many-to-one.

U^\dagger U = U U^\dagger = I \;\Rightarrow\; U^{-1} = U^\dagger \qquad (2)

where: $U$ — a quantum gate (unitary operator); $U^\dagger$ — the conjugate transpose (adjoint) of $U$ ; $I$ — the identity. The reading: since $U^{-1}$ always exists and equals $U^\dagger$ , the map on states is a bijection — the quantum version of "reversible" — and Schrödinger evolution never loses distinguishability. The physical cost of breaking reversibility is set by Landauer's principle: erasing one bit at temperature $T$ has an irreducible heat cost, and this is a statement about logic, not about any particular transistor.

Q_{\min} = k_B T \ln 2 \approx 2.87\times10^{-21}\,\mathrm{J}\quad (T=300\,\mathrm{K}) \qquad (3)

where: $Q_{\min}$ — minimum heat dissipated per erased bit; $k_B=1.380649\times10^{-23}\,\mathrm{J/K}$ — Boltzmann constant; $T$ — reservoir temperature. The reading: the number is tiny — a modern transistor dissipates it hundreds of millions of times over — but it is a floor no cooling and no cleverness can beat while the operation stays logically irreversible. The Toffoli, or controlled-controlled-NOT, is the canonical reversible gate: it flips its target only when both controls are $1$ — the reversible embedding of AND.

\mathrm{Toffoli}\,|a,b,c\rangle = |a,\,b,\,c\oplus ab\rangle \qquad (4)

where: $a,b$ — the two control bits; $c$ — the target bit; $\oplus$ — addition modulo $2$ (XOR); $ab$ — logical AND of the controls. The reading: with $c=0$ the target becomes $ab$ , so the third wire carries the AND while $a,b$ survive; the gate permutes eight strings, exchanging only $|110\rangle\leftrightarrow|111\rangle$ , hence is its own inverse. The Fredkin, or controlled-SWAP, is the other standard universal reversible gate: its control decides whether to exchange two data bits, and because it never changes the number of $1$ s it is conservative.

\mathrm{Fredkin}\,|c,a,b\rangle = \begin{cases}|c,a,b\rangle & c=0\\[2pt] |c,b,a\rangle & c=1\end{cases} \qquad (5)

where: $c$ — the control bit; $a,b$ — the two target bits, swapped when $c=1$ . The reading: with $b=0$ one output wire carries $c\cdot a$ (an AND), so Fredkin computes AND without ever creating or destroying a $1$ — a bit-conserving reversible gate. The CNOT is the two-bit workhorse: reversible XOR, and the tool that copies a classical value onto a fresh ancilla.

\mathrm{CNOT}\,|a,b\rangle = |a,\,b\oplus a\rangle \qquad (6)

where: $a$ — control bit, passed through unchanged; $b$ — target bit, replaced by $b\oplus a$ . The reading: with $b=0$ the target becomes a copy of $a$ , so CNOT is reversible fan-out for classical bits — the operation Bennett's construction uses to read an answer out of the work register. Bennett's compute–copy–uncompute keeps reversibility from drowning in garbage: compute the answer plus junk, copy the answer to a clean register, then run the computation backwards to wipe the junk.

|x,0,0\rangle \xrightarrow{\,U_f\,} |x,g(x),0\rangle \xrightarrow{\,\text{copy}\,} |x,g(x),f(x)\rangle \xrightarrow{\,U_f^{-1}\,} |x,0,f(x)\rangle \qquad (7)

where: $x$ — input register; $g(x)$ — the work register holding $f(x)$ tangled with garbage; $U_f^{-1}$ — the inverse subroutine that erases the garbage without touching the copied output. The reading: the middle register returns to $0$ , ready for reuse, and the answer sits alone in the third register. Finally, the count: because an $n$ -bit reversible gate is a permutation of $2^n$ strings, the gates are literally counted by a factorial.

\#\{n\text{-bit reversible gates}\} = (2^n)! \qquad (8)

where: $(2^n)!$ — permutations of the $2^n$ configurations. The reading: $n=1$ gives $2!=2$ (identity and NOT), $n=2$ gives $4!=24$ (including CNOT and SWAP), $n=3$ gives $8!=40320$ , of which the Toffoli is one — a finite, discrete set inside the continuous group $U(2^n)$ of real dimension $4^n$ .

Derivation AWhere the Landauer k_B T ln2 comes from

The goal is to derive the minimum heat released when one bit of information is erased, starting only from the Boltzmann definition of entropy and the second law, and to see why the bound attaches to the logical act of erasure rather than to any hardware. We treat the bit as a two-state system, compute how much its entropy falls when it is forced to a known value, insist that total entropy cannot decrease, and read off the heat the environment at temperature $T$ must absorb.

Step 1. An unknown bit is equally likely to be $0$ or $1$ , so it explores $\Omega=2$ microstates and carries entropy $S=k_B\ln\Omega=k_B\ln 2$ . Numerically $k_B\ln 2 = 1.380649\times10^{-23}\times 0.6931 = 9.57\times10^{-24}\,\mathrm{J/K}$ . Why: entropy measures our ignorance of which state the system is in, and a fair bit is maximally ignorant among its two options — this is the entropy that erasure will have to remove.

Step 2. Erasure forces the bit to a fixed value, say $0$ , so afterwards $\Omega=1$ and its entropy is $S=k_B\ln 1=0$ . The bit's entropy change is therefore $\Delta S_{\text{bit}}=-k_B\ln 2$ . Why: "erase" means make the outcome certain regardless of what was there before — a two-to-one map on the state space — and certainty is zero entropy.

Step 3. The second law forbids the total entropy of bit-plus-environment from decreasing, so whatever entropy the bit shed must reappear elsewhere: $\Delta S_{\text{env}}\ge +k_B\ln 2$ . Why: the local order we imposed on the bit is paid for by disorder exported to the surroundings — you cannot make one part of a closed system more certain for free.

Step 4. At temperature $T$ that entropy is carried by heat through $Q=T\,\Delta S_{\text{env}}$ , giving $Q\ge k_B T\ln 2$ . At $T=300\,\mathrm{K}$ this is $Q\ge 1.380649\times10^{-23}\times 300\times 0.6931 = 2.87\times10^{-21}\,\mathrm{J}$ . Why: heat is the currency in which entropy is settled with a reservoir, so the entropy debt of Step 3 becomes a minimum dissipated energy — the Landauer bound, saturated only by idealized quasi-static erasure. *Note: $k_B\ln 2 = 9.57\times10^{-24}\,\mathrm{J/K}$ and $k_B T\ln 2 = 2.87\times10^{-21}\,\mathrm{J}$ at $300\,\mathrm{K}$ ; a reversible (bijective) step has $\Delta S_{\text{bit}}=0$ and hence $Q_{\min}=0$ .*

Go deeper · Derivation B · 2 minAND is irreversible; embedding it in the Toffoli

Derivation BAND is irreversible; embedding it in the Toffoli

The goal is to show rigorously that the AND gate cannot be reversible — no permutation implements it — and then to construct the smallest reversible gate that contains AND as a special case, the Toffoli. We count preimages to prove non-injectivity, add an ancilla wire to restore a bijection, check that the enlarged map is invertible on all eight strings, and confirm it is its own inverse.

Step 1. Count sizes. The domain $\{0,1\}^2$ has $4$ elements; a single output bit has $2$ values. By pigeonhole at least two inputs share an output, and in fact three of them — $(0,0),(0,1),(1,0)$ — all map to $0$ . A map with a three-element preimage is not injective, so it has no inverse and cannot be a permutation. Why: reversibility is exactly injectivity, and any gate that shrinks the number of live configurations has already destroyed the information distinguishing them.

Step 2. Repair it by widening the map so nothing is discarded: send $(a,b,c)\mapsto(a,b,c\oplus ab)$ on three bits, keeping the inputs $a,b$ untouched. Domain and range now have equal size $8$ , so a bijection is at least possible. Why: the input bits were the information AND threw away; carrying them along on their own wires is the cheapest way to keep the input recoverable.

Step 3. Check injectivity directly. Given an output $(a,b,d)$ with $d=c\oplus ab$ , read $a$ and $b$ straight off the first two wires, form $ab$ , and recover $c=d\oplus ab$ using $ab\oplus ab=0$ . Every output has a unique input, so the map is a bijection — a genuine permutation of the eight strings, the Toffoli gate. Why: the two controls survive precisely so the receiver can recompute $ab$ and undo the XOR, which is what makes the enlarged gate invertible where AND was not.

Step 4. Confirm it is self-inverse. Applying Toffoli twice sends $c\mapsto c\oplus ab\mapsto (c\oplus ab)\oplus ab = c$ , with $a,b$ never moving, so $\mathrm{Toffoli}^2=I$ . Setting the ancilla $c=0$ then leaves the AND in the third wire: $(a,b,0)\mapsto(a,b,ab)$ . Why: a clean reversible gate should undo itself, so that a subroutine and its uncomputation are literally the same circuit run twice — the property Bennett's construction relies on to wipe garbage. *Note: enumerating all eight inputs shows the 3-bit map is a permutation exchanging only $|110\rangle\leftrightarrow|111\rangle$ ; $\mathrm{Toffoli}^2=I$ ; with $c=1$ the third wire returns $1\oplus ab = \overline{ab}$ , the reversible NAND.*

Go deeper · Derivation C · 2 minBennett's uncomputation removes the garbage

Derivation CBennett's uncomputation removes the garbage

The goal is to show that the compute–copy–uncompute schedule returns every ancilla to $|0\rangle$ while preserving the answer, and then to explain why in the quantum setting this cleanup is a physical necessity, not optional bookkeeping. We track three registers — input, work, output — through three reversible stages, then extend the bit-string argument to a superposition by linearity and watch what leftover garbage does to the interference.

Step 1. Compute. Starting from $|x,0,0\rangle$ , run the reversible subroutine $U_f$ on the input and work registers to reach $|x,\,g(x),\,0\rangle$ , where $g(x)$ holds the answer $f(x)$ entangled with intermediate junk. Why: any real subroutine produces scratch values — carries, partial products — alongside its result, and reversibility forbids discarding them, so they accumulate in the work register.

Step 2. Copy. With bitwise CNOTs, copy the answer bits from the work register into the fresh output register: $|x,\,g(x),\,0\rangle\mapsto|x,\,g(x),\,f(x)\rangle$ . Copying a classical value is reversible — it is fan-out via XOR — and it leaves the work register unchanged. Why: we need a clean copy of the answer that is not entangled with the junk before we destroy the junk, or we would erase the result along with it.

Step 3. Uncompute. Run the subroutine backwards, $U_f^{-1}$ , on the input and work registers: $|x,\,g(x),\,f(x)\rangle\mapsto|x,\,0,\,f(x)\rangle$ . Since $U_f^{-1}U_f=I$ on those registers and the output is untouched, the work register returns exactly to $0$ while $f(x)$ survives. Why: the same reversibility that trapped the garbage lets us retrace and unwind it — the junk is not erased (which would cost Landauer heat) but reversibly undone.

Step 4. See why it matters quantumly. By linearity the schedule acts on a superposition input as $\sum_x\alpha_x|x,0,0\rangle\mapsto\sum_x\alpha_x|x,0,f(x)\rangle$ . Had garbage remained, the state would be $\sum_x\alpha_x|x,g(x),f(x)\rangle$ , and two branches with the same $x$ and $f(x)$ but different $g(x)$ would be kept distinguishable, blocking the interference that quantum algorithms extract their answers from. Why: garbage that stays entangled with the data acts like an unread measurement record, decohering the computation — uncomputation disentangles it and restores coherence. *Note: each arrow is a composition of reversible gates so the net map is unitary; on basis inputs the work register provably returns to $0$ , and linearity carries the conclusion to arbitrary superpositions of $x$ .*

Limiting cases

Reversible structures appear as special or limiting cases of the broader gate landscape, and reading them off sharpens what "reversible" buys and costs.

Case	Result	Meaning
Classical limit of unitary gates	$U\in\{0,1\}^{2^n\times2^n},\ U^\dagger U=I$	a unitary with only $0/1$ entries is a permutation matrix — the purely classical reversible gates, a measure-zero corner of $U(2^n)$
NOT as a Pauli	$X=\left(\begin{smallmatrix}0&1\\1&0\end{smallmatrix}\right)$	the reversible NOT is the Pauli $X$ ; $Y,Z$ carry phases and have no real-permutation (classical) analogue
AND embedded reversibly	$\mathrm{Toffoli}:(a,b,0)\mapsto(a,b,ab)$	fixing the ancilla to $0$ computes the irreversible $ab$ in the third bit while $a,b$ persist as garbage
Zero-erasure limit	$Q_{\min}=k_B T\ln 2\to 0$	as the fraction of irreversible (erasing) steps goes to zero, the Landauer dissipation floor vanishes
One reversible bit	$(2^1)!=2$	on a single bit only identity and NOT are reversible — there is no room for anything nontrivial

Common trapGarbage bits are free because you can just ignore them

They are not free, and ignoring them is exactly the trap. Classically an unread scratch bit is harmless — you may leave junk in an ancilla and never look at it. Quantum-mechanically that junk stays entangled with the data: a superposition ends as $\sum_x\alpha_x|x\rangle|g(x)\rangle|f(x)\rangle$ , and the garbage $g(x)$ tags each branch, so branches that should interfere (same $x$ and $f(x)$ ) are kept distinguishable and the interference the algorithm needs is destroyed. Worse, if that ancilla later decoheres it acts like an environment silently measuring your computation. The fix is Bennett's compute–copy–uncompute: run the subroutine, copy the answer to a clean register, then run the subroutine backwards to return the ancilla to $|0\rangle$ . Reversibility means never erasing — but not never cleaning up.

Worked examples

1 · The Landauer floor versus a real processor (fully worked)

Estimate the minimum energy to erase a 64-bit register at room temperature, the maximum bit-erasure rate of a 1-watt chip held at the Landauer limit, and how far a real CMOS gate ( $\sim 1\,\mathrm{pJ}$ per switching operation) sits above that floor.

Step 1. The per-bit floor is equation (3): $Q_{\min}=k_B T\ln 2 = 1.380649\times10^{-23}\times300\times0.6931 = \mathbf{2.87\times10^{-21}\,J}$ at $T=300\,\mathrm{K}$ . Erasing a full 64-bit register that is uniformly random costs $64\times2.87\times10^{-21}=\mathbf{1.84\times10^{-19}\,J}$ . Wiping a whole register costs under a fifth of an attojoule — thermodynamics places almost no obstacle here.

Step 2. A chip dissipating $P=1\,\mathrm{W}=1\,\mathrm{J/s}$ purely on Landauer-limited erasures could erase at most $R=P/Q_{\min}=1/(2.87\times10^{-21})=\mathbf{3.5\times10^{20}}$ bits per second — the ultimate thermodynamic speed limit of irreversible logic at $1\,\mathrm{W}$ and $300\,\mathrm{K}$ . The floor is set by physics, not engineering, and it is extraordinarily permissive.

Step 3. A real switching event dissipating $\sim1\,\mathrm{pJ}=10^{-12}\,\mathrm{J}$ exceeds the floor by $10^{-12}/2.87\times10^{-21}\approx\mathbf{3.5\times10^{8}}$ . Today's transistors run about $10^{8}$ – $10^{9}$ times above the Landauer limit, which is why erasure heat is not yet the binding constraint — but it is the target reversible and adiabatic logic aim to approach.

2 · Reversible NAND from a Toffoli, and its garbage (fully worked)

Use a single Toffoli gate to compute the universal NAND of two bits, verify it on the truth table, and identify exactly what garbage is left behind.

Step 1. Initialize the target to $c=1$ and apply the Toffoli: $|a,b,1\rangle\mapsto|a,b,\,1\oplus ab\rangle$ . Since $1\oplus ab=\overline{ab}$ , the third wire now carries $\mathrm{NAND}(a,b)$ . Setting the ancilla to $1$ instead of $0$ converts the reversible AND into the reversible NAND — a universal gate — for free.

Step 2. Verify on all four inputs. $(a,b)=(0,0)\to 1\oplus0=\mathbf{1}$ ; $(0,1)\to 1\oplus0=\mathbf{1}$ ; $(1,0)\to 1\oplus0=\mathbf{1}$ ; $(1,1)\to 1\oplus1=\mathbf{0}$ . This is exactly the NAND truth table, which returns $0$ only when both inputs are $1$ . One Toffoli reproduces NAND, and because NAND is universal for classical logic, the Toffoli alone (with prepared ancillas) can build any circuit.

Step 3. Account for the wires. The output register holds $|a,b,\overline{ab}\rangle$ : alongside the answer $\overline{ab}$ the two input bits $a,b$ come out untouched. Those preserved inputs are the garbage — necessary for reversibility but useless downstream — and in a quantum circuit they must be uncomputed so they do not stay entangled with the result. One NAND leaves two garbage bits; a deep circuit accumulates them, which is precisely the ancilla-management problem Bennett's uncomputation solves.

Physics of the portrait

Reversible computation is the work of a small circle of IBM physicists who asked, against the grain of their era, whether computation had a fundamental thermodynamic cost — and answered that it did not, provided you never erase.

Origins · 1 minCharles Bennett and how this was discovered

Charles Bennett

born 1943 · reversible computation and the thermodynamics of information

Charles H. Bennett is the physicist who turned the physics of information from a curiosity into a field. Working at IBM Research alongside Rolf Landauer — whose 1961 principle had pinned the cost of computation onto the single act of erasure — Bennett proved in his 1973 paper "Logical Reversibility of Computation" that this cost is escapable: any computation can be rebuilt from reversible steps by keeping a history of its work, copying out the answer, and then reversibly undoing the history, so that in principle it dissipates nothing. That compute–copy–uncompute idea is now the standard discipline for managing ancillas in every quantum compiler. In 1982 he closed a puzzle standing since the nineteenth century, showing that Maxwell's demon does not violate the second law because the demon must eventually erase its own memory, paying exactly Landauer's $k_B T\ln 2$ per bit — the resolution now taught as the Landauer–Bennett argument. His reach did not stop there: with Gilles Brassard he invented quantum key distribution (the BB84 protocol, 1984), and with Brassard, Crépeau, Jozsa, Peres and Wootters he co-discovered quantum teleportation (1993). Across all of it runs one conviction — that information is physical, that logical operations have thermodynamic weight, and that reversibility is the hinge connecting the two. The reversible gates this article is built on, and the uncomputation trick that keeps quantum circuits coherent, are his intellectual descendants.

History

1961

— Landauer argues that erasing one bit must dissipate at least k_B T ln2 of heat

1973

— Bennett proves any computation can be made logically reversible via uncomputation

1980

— Toffoli introduces the reversible controlled-controlled-NOT gate

1982

— Fredkin and Toffoli formulate conservative logic and the controlled-SWAP gate

2012

— Bérut and colleagues measure the Landauer limit with a single colloidal particle

Going further

Texts. Nielsen & Chuang, Quantum Computation and Quantum Information, §1.4.1 (reversible computation and universal gates) and §3.2.5 · Preskill, Lecture Notes for Physics 219, Ch. 6 (classical and quantum reversible computation) · Watrous, The Theory of Quantum Information, Ch. 2 · Kitaev, Shen & Vyalyi, Classical and Quantum Computation, §7 · Mermin, Quantum Computer Science, Ch. 2 · Bennett, "Logical Reversibility of Computation," IBM J. Res. Dev. 17, 525 (1973) · Landauer, "Irreversibility and Heat Generation in the Computing Process," IBM J. Res. Dev. 5, 183 (1961). Key numerical checks: the 3-bit Toffoli map is a permutation exchanging only $|110\rangle\leftrightarrow|111\rangle$ and $\mathrm{Toffoli}^2=I$ ; the Landauer value $k_B T\ln 2 = 1.380649\times10^{-23}\times300\times0.6931 = 2.87\times10^{-21}\,\mathrm{J}$ with $k_B\ln 2 = 9.57\times10^{-24}\,\mathrm{J/K}$ ; the gate counts $(2^n)!$ give $2, 24, 40320$ for $n=1,2,3$ ; the worked numbers $64\times2.87\times10^{-21}=1.84\times10^{-19}\,\mathrm{J}$ , rate $3.5\times10^{20}\,\mathrm{s^{-1}}$ at $1\,\mathrm{W}$ , $\mathrm{pJ}$ overhead $\approx3.5\times10^{8}$ ; and the reversible NAND $1\oplus ab=\overline{ab}$ .

Prerequisites. Quantum Circuit Model · Pauli Gates (X, Y, Z) · CNOT Gate. Leads to. Controlled-U Gates · Circuit Identities and Equivalences · SWAP Gate.

Ask the tutor: ask me to make any irreversible gate reversible, run a bit string through a Toffoli or Fredkin, or compute the Landauer heat for a given erasure.

Is reversible computing just a theoretical curiosity, or does it matter in practice?

It matters twice over. First, it is not optional inside a quantum computer: because every quantum gate is unitary and therefore reversible, any classical logic you run — the arithmetic in Shor's algorithm, the oracle in Grover's — must be rebuilt from reversible gates before it can be expressed at all, and the Toffoli count of that circuit is a leading cost metric in fault-tolerant design. Second, it sets the ultimate energy target for classical computing: Landauer's principle gives irreversible erasure a hard thermodynamic floor that reversible and adiabatic logic are being developed to approach. The theory is at once a constraint on quantum programming today and a long-horizon goal for low-power computing.

Does Landauer's principle mean a reversible computer runs on zero energy?

No — it means the logical floor is zero, which is not the same as a real device using nothing. Landauer's bound $k_B T\ln 2$ per bit applies only to irreversible erasure; a perfectly reversible, bijective step has no such floor and could in principle run with arbitrarily little dissipation. But "in principle" hides two costs: approaching zero dissipation requires running quasi-statically — infinitely slowly — so there is a speed–energy tradeoff, and every physical device has friction, leakage, and control overhead far above the thermodynamic floor. Reversible logic removes the erasure floor; it does not defeat engineering losses.

Why can't I just throw away garbage bits instead of uncomputing them?

Classically you can — an unread scratch bit costs nothing until you erase it. Quantum-mechanically you cannot, because the garbage is entangled with your data. After a subroutine the state is $\sum_x\alpha_x|x\rangle|g(x)\rangle|f(x)\rangle$ , and $g(x)$ carries a distinct fingerprint for each branch. Interference — the resource that makes quantum algorithms work — requires branches with the same outcome to be genuinely indistinguishable, but the differing $g(x)$ keeps them apart. Discarding the ancilla is worse still: a discarded entangled qubit decoheres, equivalent to the environment measuring your computation. Bennett's uncomputation reversibly returns the ancilla to $|0\rangle$ , disentangling it and restoring coherence.

Is the Toffoli gate really enough to build any classical computation?

Yes. The Toffoli gate is universal for reversible classical computation: with ancilla bits prepared to fixed constants and the freedom to leave garbage on extra wires, it simulates AND (ancilla $c=0$ ), NAND ( $c=1$ ), NOT (both controls $1$ ), and fan-out/COPY. Since NAND alone is universal for Boolean logic and the Toffoli produces NAND, any classical circuit can be rewritten as a network of Toffolis. The Fredkin gate is universal in the same sense, with the extra property of being conservative — it preserves the number of $1$ s. The price of universality is space: reversible circuits need ancilla wires and accumulate garbage that must be managed.

What is the difference between reversible computation and quantum computation?

Reversible computation is the classical skeleton; quantum computation is the full body. A reversible gate is a permutation of bit strings — equivalently a unitary whose entries are all $0$ or $1$ . Quantum gates are arbitrary unitaries, allowing superposition ( $\alpha|0\rangle+\beta|1\rangle$ ), complex amplitudes, relative phases, and interference between paths. The permutation matrices are a finite, measure-zero subset of the continuous group $U(2^n)$ . So every reversible classical circuit is a legal quantum circuit (using only "classical" gates like Toffoli and CNOT), but the reverse is false: gates like the Hadamard, which create superposition, have no classical analogue and are what give quantum computing its power.

How is reversibility related to the no-cloning theorem?

Both flow from the linearity and unitarity of quantum evolution but constrain different things. Reversibility says a gate must be a bijection, so no quantum operation can be many-to-one. No-cloning says no unitary copies an unknown state $|\psi\rangle$ onto a blank register for all $|\psi\rangle$ . The connection is visible in the CNOT: it faithfully copies classical basis states, $|c\rangle|0\rangle\mapsto|c\rangle|c\rangle$ — the reversible fan-out Bennett's construction uses — but feed it a superposition and it entangles rather than duplicates, $(\alpha|0\rangle+\beta|1\rangle)|0\rangle\mapsto\alpha|00\rangle+\beta|11\rangle$ , which is not two copies. Reversibility permits copying classical information; no-cloning forbids copying quantum information, and the CNOT sits exactly on that boundary.

Does erasing information really produce heat, or is that just a metaphor?

It is real and it has been measured. Landauer's argument is thermodynamic, not figurative: forcing a bit to a known value halves its accessible phase-space volume, lowering its entropy by $k_B\ln 2$ , and the second law requires that entropy be exported to the environment as heat $Q\ge k_B T\ln 2$ . In 2012 Bérut and colleagues confirmed this directly, watching a single micron-scale particle in a double-well optical trap and measuring the heat released when its one bit was erased — it tracked the $k_B T\ln 2$ prediction. Later experiments repeated the test with single electrons and nanomagnets. So erasure heat is a genuine, laboratory-verified physical cost — which is precisely why avoiding erasure, through reversible computation, is worth the effort.