Skip to content

Reversible Computing

Abstract

Reversible computing is the idea that a computer need not throw information away, and so need not pay the minimum energy cost that physics charges for throwing it away. Rolf Landauer at IBM set the price in 1961: erasing one bit must release at least kT ln 2 of heat. Charles Bennett showed in 1973 that any computation can be done without erasing anything, and at MIT in the early 1980s Edward Fredkin, Tommaso Toffoli and Norman Margolus built a logic of reversible gates and computers made of colliding billiard balls. Their gates ended up as the basic parts of quantum computing. The energy-saving hardware was built at MIT in the 1990s and then left alone while ordinary chips kept getting cheaper, until a London start-up recovered energy on a 22-nanometre test chip in 2025.

Billiard Ball Interaction Gate
A gate in the billiard-ball model of Fredkin and Toffoli (1982): a single ball passes straight through (left); two balls arriving together collide and leave on paths that encode their logical AND (right). Image: Д.Ильин: vectorization, CC0, via Wikimedia Commons.

Landauer’s Bound

Rolf Landauer was born in Stuttgart in 1927, left Germany with his family in 1938, took his Harvard PhD in 1950 and joined IBM Research at 25 to work on semiconductors. In July 1961 he published “Irreversibility and Heat Generation in the Computing Process” in the IBM Journal of Research and Development. The argument starts from a plain observation. An AND gate that outputs 0 cannot tell you whether its inputs were 00, 01 or 10: the gate has destroyed information. Clearing a memory cell to 0 does the same thing more obviously. Landauer argued that such logically irreversible operations must dissipate heat, at least kT ln 2 per bit lost, where k is Boltzmann’s constant and T the temperature. At room temperature that is about 0.018 electron volts, or 2.9 × 10⁻²¹ joules.

Operations that lose no information carry no such minimum. Landauer himself assumed that useful computation could not do without erasure, so the bound looked like a floor under every computer ever to be built. He summed up the position thirty years later in the title of a 1991 Physics Today article, “Information Is Physical”: a bit is always a charge, a spin or a hole in a card, and the laws of thermodynamics apply to it.

Misconception: The Landauer limit is a minimum energy cost for every logic operation

The bound applies only to operations that erase information. Landauer’s own paper draws the distinction, Bennett showed in 1973 that any computation can be arranged to erase nothing, and the gates of reversible and quantum computing are built to lose no bits. The practical point is moot for now: Michael Frank estimated in 2017 that a CMOS chip spends around 5,000 electron volts per bit it erases, several hundred thousand times the bound. See Myths and Misconceptions.

Computing Without Forgetting

The escape was found by Charles Bennett, who had joined IBM Research in 1972. The French logician Yves Lecerf had described a reversible Turing machine in 1963 without connecting it to thermodynamics, and did not pursue it. Bennett’s “Logical Reversibility of Computation” (IBM Journal of Research and Development, November 1973) showed that any ordinary Turing machine can be simulated by a reversible one. The trick has three stages. Run the computation forward, writing every step’s discarded information onto a history tape instead of erasing it. Copy the answer, which is a reversible operation onto blank tape. Then run the whole computation backwards, which consumes the history and returns the machine to its starting state, holding nothing but the input and the copied output. Nothing has been erased, so Landauer’s bound does not apply.

The cost is memory for the history, which in the naive version grows with the running time. In 1989 Bennett showed in SIAM Journal on Computing how to cut that cost by splitting the computation into checkpointed segments and uncomputing them in a nested order, at the price of extra running time. The recipe of compute, copy, uncompute is now standard practice in quantum algorithms, where leftover garbage bits would spoil the result (see Bennett and Brassard).

Maxwell’s Demon

The same reasoning settled a puzzle older than computing. In 1867 James Clerk Maxwell had imagined a creature guarding a door between two chambers of gas, letting fast molecules through one way and slow ones the other, so that one side heats up without any work being done, against the second law of thermodynamics. Leó Szilárd reduced it in 1929 to an engine with a single molecule and concluded that the demon must pay for measuring which side the molecule is on. Bennett’s 1982 review “The Thermodynamics of Computation” put the cost elsewhere: measurement can in principle be done reversibly, but the demon’s memory fills up, and wiping it to start again costs at least as much as the demon gains. The demon pays for forgetting.

The erasure bound was measured directly in 2012. A group at the École Normale Supérieure in Lyon under Sergio Ciliberto, with the theorist Eric Lutz, trapped a single colloidal particle, a microscopic bead, in a double well formed by two focused laser beams, so that bead-left and bead-right stored one bit. They erased the bit by lowering the barrier between the wells and nudging the bead to one side. The heat released came down towards kT ln 2 as the erasure was done more slowly, and never went below it (Nature, March 2012). The philosopher of science John Norton has argued that the usual derivations of Landauer’s principle are circular; Bennett and others have answered that it follows from the second law, and the experiments have not found a way around it.

Conservative Logic at MIT

In 1974 Edward Fredkin spent a year at Caltech trading lessons with Richard Feynman, computing for physics, and came back with a model of computation built from physics: hard, perfectly elastic balls moving on a grid and bouncing off fixed mirrors, with the presence or absence of a ball at a place and time standing for a bit. Where two balls meet, they collide and leave on paths that depend on both; a ball arriving alone goes straight on. The model can compute anything a conventional computer can, and because Newtonian collisions run equally well backwards, stopping every ball and reversing it walks the whole computation back to its start (see Edward Fredkin).

Tommaso Toffoli, born in 1943 in Montereale Valcellina in northeastern Italy, came to the United States in 1969, wrote his Michigan dissertation on cellular automata in 1976, and joined Fredkin’s Information Mechanics Group at MIT in 1978. In an MIT technical report and a paper at the 1980 International Colloquium on Automata, Languages and Programming in Noordwijkerhout, titled simply “Reversible Computing,” he introduced the gate now named after him. The Toffoli gate has three inputs and three outputs; it passes two bits through unchanged and flips the third only if the first two are both 1. It is its own inverse, and every reversible Boolean circuit can be built from it alone. The Fredkin gate does the same job differently: a control bit decides whether the other two bits are swapped. Because it only moves bits around, the number of 1s going in equals the number coming out, which is what Fredkin and Toffoli meant by “conservative.” Their paper “Conservative Logic” (International Journal of Theoretical Physics, 1982) set out both the gate and the billiard-ball computer.

Norman Margolus, a student of Fredkin’s, showed in “Physics-like Models of Computation” (Physica D, 1984) that a reversible cellular automaton can simulate the billiard balls, using a block-update scheme now called the Margolus neighborhood; he took his PhD in 1987. With Toffoli he designed CAM-6, a board that plugged into an IBM PC and ran cellular automata fast enough to watch, and described it in their book Cellular Automata Machines (MIT Press, 1987).

The billiard balls later found a stranger substrate. In 2011 Yukio-Pegio Gunji and colleagues at Kobe University reported that swarms of soldier crabs (Mictyris guinotae), driven down plastic corridors by the shadow of a plate, which they flee as they would a predatory bird, merge on collision and move off in the combined direction, close enough to colliding balls to build logic gates from them (“Robust Soldier Crab Ball Gate,” Complex Systems, 2011).

Endicott House and the Quantum Turn

In May 1981 Fredkin, Landauer and Toffoli organized the Physics of Computation conference at MIT’s Endicott House in Dedham, Massachusetts. Among the roughly sixty participants were Feynman, John Wheeler, Freeman Dyson and Konrad Zuse. Feynman’s talk, “Simulating Physics with Computers,” argued that only a computer running on quantum mechanics could efficiently simulate quantum systems. A quantum computer’s elementary steps are unitary transformations, and every one of them can be undone, so every quantum computer is a reversible computer. The Toffoli and Fredkin gates carried straight over; they are how a quantum machine performs ordinary Boolean logic, and the Fredkin gate appears in textbooks as the controlled-SWAP. The energy argument that had motivated the gates was no longer the point (see Quantum Computing).

Janus

A reversible machine needs reversible programs. In 1982 two Caltech students, Christopher Lutz and Howard Derby, wrote Janus for a class, “out of curiosity over whether such an odd animal as this was possible, and because we were interested in knowing where we put information when we programmed,” Lutz wrote. Janus has no ordinary assignment: a variable can be increased, decreased or exclusive-ORed by an expression, or swapped with another, but never overwritten, and every if ends with a fi test that must agree with the opening condition, so the program running backwards knows which branch it came from. Any procedure can be run in reverse with uncall. The manual called the implementation, written in Simula on a DECSYSTEM-20, “a throw-away piece of code.” It reached the man who had started the subject by post: in April 1986 Lutz, by then at IBM’s Almaden Research Center, mailed the description to Landauer a week after hearing him lecture there on the physical limits of computation. Tetsuo Yokoyama and Robert Glück gave the language a formal semantics, a program inverter and a self-interpreter in 2007, and it has been the reference language of reversible programming research since.

Adiabatic Circuits

Logical reversibility alone saves nothing in a CMOS chip, whose losses come from charging and discharging wires through transistors and sit far above the Landauer bound. The energy saving needs a second idea, adiabatic switching. A conventional gate connects a capacitance abruptly to the supply rail and loses the energy as heat in the transistor’s resistance. If instead the supply voltage is ramped slowly, the charge moves with only a small voltage across the transistor, and when the ramp comes back down most of the energy flows back into the power supply. The dissipation per operation falls in proportion to how slowly the ramp is done. A chip can therefore trade speed for energy, but only if no gate ever has to discard a value while its supply is ramping, and that condition is logical reversibility again.

Charles Seitz’s group at Caltech applied the idea in “hot-clock nMOS” in 1985. Jeffrey Koller and William Athas at the University of Southern California’s Information Sciences Institute attached the word “adiabatic” to it at the 1992 Workshop on Physics and Computation in Dallas, and with Lars Svensson and others published the design principles in IEEE Transactions on VLSI Systems in December 1994. At MIT, Saed Younis and Thomas Knight demonstrated Charge Recovery Logic in 1993, the first circuit family that was both fully adiabatic and fully reversible, and followed it with Split-Level Charge Recovery Logic, the subject of Younis’s 1994 PhD thesis, Asymptotically Zero Energy Computing.

Knight’s group then built processors. From 1996 to 1999 Carlin Vieri, Michael Frank, Scott Rixner, Josephine Ammer and Nicole Love, working with Knight and Margolus, fabricated a series of reversible chips at MIT: Tick (1996), an 8-bit reversible processor that was not yet adiabatic, and Flattop (1996), an adiabatic gate array running Margolus’s billiard-ball cellular automaton. The last of them, Pendulum, completed for Vieri’s 1999 thesis, was a 12-bit implementation of the Pendulum Instruction Set Architecture: every instruction could be undone, and the processor could be switched into reverse mid-program to uncompute its intermediate results. Frank went on to the University of Florida, where in 2004 he and his student Krishna Natarajan showed in simulation that a two-level adiabatic logic family, 2LAL, could get dissipation down to about 1 electron volt per transistor per cycle.

The Dead End

None of it reached a product. The reason was the rest of the chip industry. Through the 1990s and early 2000s shrinking transistors cut the energy of each switching event by itself, and a technique that bought lower energy at the cost of lower speed, more transistors, multi-phase power clocks and a new design discipline had nothing to sell. Frank’s summary in IEEE Spectrum in 2017: “Conventional semiconductor technology improved rapidly through the 1990s and early 2000s, and so the field of reversible computing mostly languished.” Adiabatic circuits also suffer from a problem the theory ignores: modern transistors leak current even when switched off, and the leakage eats the savings that slow ramping recovers.

Frank kept the subject alive from Sandia National Laboratories, where he and colleagues described a static two-level adiabatic logic, S2LAL, at the IEEE International Conference on Rebooting Computing in 2020. His argument was that the free lunch had ended: CMOS now used around 5,000 electron volts per bit erased and could not go much below 500, so every further gain in energy efficiency would have to come from not erasing. “A conventional computer is, essentially, an expensive electric heater that happens to perform a small amount of computation as a side effect.”

Vaire and Ice River

In 2018 Rodolfo Rosini, a serial entrepreneur, came across reversible computing as what he called an “orphan technology.” In 2021 he founded Vaire Computing in London with Hannah Earley, who had done her Cambridge PhD on molecular and DNA computing and had turned to reversible logic after reading Frank’s work; she became chief technology officer. Frank joined as a senior scientist. In August 2025 the company tested its first chip, Ice River, made in a 22-nanometre CMOS process, which combined adiabatic reversible circuits with an on-chip resonator that catches the energy of each voltage ramp and returns it on the next cycle. Measured against the same circuits driven conventionally, it dissipated 1.77 times less for a capacitor array and 1.41 times less for a shift register, roughly 30 percent less energy for the same work, at 500 MHz. The results were below the company’s own simulations of about a factor of two, and Vaire said that making reversible computing practical still faced many challenges. By September 2026 the company had raised more than $12 million, and the chip designer Igor Markov still called the technology “quite early stage.” The Landauer bound itself, 0.018 electron volts per bit, is several orders of magnitude below where any of these chips operate. What the 2025 chip showed is that the energy of a switching event can be caught and reused on silicon made in a commercial process.

📚 Sources