Every logic gate in an ordinary chip throws information away, because an AND gate that outputs 0 cannot say whether its inputs were 00, 01 or 10. In 1961 Rolf Landauer of IBM argued that such forgetting costs heat, and two decades later Edward Fredkin and Tommaso Toffoli of MIT showed how to build logic that forgets nothing.
Their field is called reversible computing, because a reversible circuit can always be run backwards to recover exactly the inputs it was given. It began as a question about heat and ended up at the heart of quantum computing, where every gate must be reversible.
Landauer and the cost of forgetting
Landauer’s paper, “Irreversibility and Heat Generation in the Computing Process”, set the minimum heat from erasing one bit at kT ln 2, where k is Boltzmann’s constant and T is the temperature. At room temperature that comes to about 3 × 10⁻²¹ joules, a very small amount of energy.
Today’s chips give off far more than this for each operation, so the limit is a floor rather than a bill anyone yet pays. The deeper point was that information is physical, and Quantum Zeitgeist has explained why erasing a bit generates heat in more detail.
Bennett shows it can be done
Charles Bennett, also at IBM, took the next step in his 1973 paper “Logical Reversibility of Computation”, which showed that any calculation can be done reversibly. The machine runs forwards while keeping a record of every step, copies the answer and then runs backwards to wipe the record, leaving only the input and the answer behind.
That settled the question in principle, but Bennett worked with Turing machines, an abstract model of a computer. Fredkin and Toffoli wanted reversible logic at the level of the gates and wires that engineers actually build with.
Fredkin’s reversible universe
Fredkin was an MIT professor who had never finished college, and he directed Project MAC, MIT’s large computing laboratory, from 1971 to 1974. He then spent a year at Caltech trading lessons with Richard Feynman, convinced that physics is reversible at the smallest scale and that a computer which respected it should be too.
Toffoli, an Italian-born computer scientist, came to MIT to build machines for cellular automata, which are grids of cells that update by fixed local rules. His work there ran under a grant that Fredkin held at MIT’s Laboratory for Computer Science, and the two became close collaborators.
The Toffoli gate
In 1980 Toffoli published “Reversible Computing” in the proceedings of a computer science conference, setting out the gate now named after him. The Toffoli gate has three wires and flips the third bit only when the first two are both 1, which is why it is also called the controlled-controlled-NOT.
Fix the third input at 0 and the third output is the AND of the first two, while fixing it at 1 gives NAND instead. NAND alone is enough to build any logic circuit, but no reversible gate on just two wires can do the same, so classical reversible logic needs gates with at least three.
Conservative logic and the Fredkin gate
Fredkin and Toffoli’s joint paper, “Conservative Logic”, appeared in the International Journal of Theoretical Physics in 1982 and added a second rule on top of reversibility. Signals should behave like physical objects that are moved around but never created or destroyed, so the number of 1s going into a gate must always equal the number coming out.
The Fredkin gate obeys both rules, swapping two data bits or leaving them alone depending on the value of a control bit. Fed with constant 0s and 1s, it can make AND, OR, NOT and copies of bits, which together are everything an ordinary computer’s logic needs.
A network of Fredkin gates can therefore carry out any calculation, at the cost of a pile of spare outputs that the paper calls garbage. Fredkin and Toffoli showed how to clean up the garbage, so the constants used up grow only with the number of inputs and outputs, not with the number of gates. The same paper imagined building the whole thing from colliding balls, an idea explained in our page on the billiard ball computer.
Margolus and the digital billiard table
Norman Margolus, a younger member of Fredkin’s group at MIT, moved the billiard balls into software. In “Physics-like Models of Computation”, published in Physica D in 1984, he built the billiard ball model into a reversible cellular automaton whose every step was digital, leaving no drift to amplify. Toffoli and Margolus went on to build special hardware for running cellular automata, and MIT Press published their book, Cellular Automata Machines, in 1987.
From reversible logic to quantum computers
The link to quantum computing came quickly, when in 1980 Paul Benioff of Argonne National Laboratory described a computer that runs by the rules of quantum mechanics. In May 1981 Feynman gave the keynote at the Physics of Computation conference, which Fredkin helped organise, and argued that simulating nature would need a computer built from quantum parts.
Quantum computers then turned reversibility into a rule, because an isolated quantum system always changes reversibly. Every quantum gate must therefore be reversible too, and in an ideal circuit information is lost only when a qubit is measured or reset.
Any ordinary calculation inside a quantum algorithm, such as the arithmetic in Shor’s factoring algorithm, has to be built as a reversible circuit, often from Toffoli and CNOT gates. Our explainer on why quantum computers are reversible goes further. Reversible chips for ordinary computing remain a research topic, but the energy cost of training AI has revived interest in reversible computing as a way to save power.




See today’s quantum computing news on Quantum Zeitgeist for the latest breakthroughs in qubits, hardware, algorithms, and industry deals.
