Edward Fredkin and the Fredkin Gate, the Logic That Never Forgets

The Fredkin gate is a three-wire logic gate that swaps two bits when a third, the control, is 1, and leaves them alone when it is 0. Edward Fredkin and Tommaso Toffoli of MIT published it in 1982. It loses no information, it can be wired into any calculation, and its quantum version is used to compare quantum states.

Every ordinary computer forgets as it works, because an AND gate takes two bits and hands back one, and physics says the information lost along the way has to show up somewhere as heat. Edward Fredkin spent much of the 1970s asking whether a computer could be built that never forgot anything at all, and he came to believe that it could.

His answer was a three-wire switch, now called the Fredkin gate, that throws nothing away, can be wired into any calculation an ordinary computer can do and runs backwards as easily as forwards. That last property mattered far more than Fredkin expected, because every gate on a quantum computer has to be reversible too.

Who was Edward Fredkin

Edward Fredkin was born in Los Angeles on 2 October 1934 to Russian immigrant parents. He studied chemistry and physics at Caltech but left partway through his second year to train as a fighter pilot in the US Air Force in 1952. Computers came next, when in 1956 the Air Force sent him to MIT’s Lincoln Laboratory to work on SAGE, an early air defence network and one of the first large computer systems.

Fredkin never finished his degree, but in 1958 J.C.R. Licklider hired him at Bolt Beranek and Newman in Cambridge, Massachusetts. After seeing a prototype in December 1959, he persuaded BBN to buy the very first PDP-1. In 1960 he published a paper on what he called trie memory, from “retrieval”, and the trie is still a standard way to store words for fast lookup.

In 1962 he founded Information International Inc., which built high-precision machines for moving images between film and computers, before Marvin Minsky brought him to MIT. In 1968 Fredkin became a full professor there without ever having graduated from college, and from 1971 to 1974 he ran Project MAC, MIT’s large computing laboratory.

In 1980 he put up the Fredkin Prize of $100,000 for the first computer to beat a world chess champion, which IBM’s Deep Blue team collected in 1997. Fredkin joined Carnegie Mellon in 1984, won its Dickson Prize in Science the same year and later taught physics at Boston University.

He died at home in Brookline, Massachusetts, on 13 June 2023, aged 88. Raj Reddy, who had set up the chess prize with him, told Carnegie Mellon that “Ed could have more ideas in a day than many of us could in a month”.

The problem with forgetting, and why it costs heat

The physics behind the Fredkin gate starts with Rolf Landauer of IBM, who argued in 1961 that erasing one bit of information must give off a small minimum of heat set only by temperature. Forgetting, in other words, has a price, and although the amount is tiny it ties the abstract business of computing to thermodynamics, the physics of heat and energy. Quantum Zeitgeist has explained why erasing a bit generates heat in more detail.

Ordinary logic erases all the time, since an AND gate that outputs 0 cannot tell you whether its inputs were 00, 01 or 10, so two bits of history have been squeezed into one. Charles Bennett, also at IBM, showed in 1973 that a computer could in principle avoid this cost by working reversibly, keeping enough information at every step to run the whole calculation backwards.

Fredkin came at the same question from a different direction, drawn by the idea that the universe itself might be a kind of computer. The laws of physics at the smallest scale are reversible, so a computer that mirrored nature, he reasoned, should be reversible too. His MIT students were already writing about reversible logic by 1978, according to Stephen Wolfram’s long memoir of Fredkin.

How the Fredkin gate works

The Fredkin gate has three inputs and three outputs, and its first wire, the control, passes through untouched while the other two carry data bits that may or may not end up swapped. If the control is 0 the data wires go straight through, and if it is 1 they swap places.

That is why the gate is also called a controlled swap, or CSWAP, and three useful properties follow from the rule. The first is that nothing is lost, because each of the eight possible inputs gives a different output, so the input can always be worked out from the output.

The second is that the gate is its own inverse, so running the outputs through a second Fredkin gate gives back the original inputs, since swapping twice is the same as not swapping. The third is that the number of 1s never changes, because the gate only moves bits around and never creates or destroys one.

Fredkin and Tommaso Toffoli called that last property conservation, comparing signals to physical objects that “can be moved around in the course of a computation but never created or destroyed”. One historical wrinkle is that their original table crossed the data wires when the control was 0, while today’s textbooks swap on 1, though both versions do the same job.

One gate that can build any computer, even one made of billiard balls

A gate that only shuffles bits sounds too weak to compute anything useful. The surprise in Fredkin and Toffoli’s paper, “Conservative Logic”, received in May 1981 and published in the International Journal of Theoretical Physics in 1982, is that it is enough. Hold one or two of the inputs at fixed values of 0 or 1 and a chosen output becomes AND, OR or NOT.

The gate can also copy a bit, which ordinary logic does by splitting a wire, so with AND, OR, NOT and copying in hand a network of Fredkin gates can carry out any calculation. The price is a supply of fixed input bits and spare output bits, which the paper calls garbage and which must be kept, or cleared by running the circuit backwards, rather than erased.

The same paper went further and imagined building the gates out of billiard balls that bounce off each other and off fixed mirrors. A ball present at a given point in space and time stands for a 1, and an empty point stands for a 0. Because perfect collisions lose no energy, the ideal machine computes without dissipating anything.

The authors clearly enjoyed the image, writing that the behaviour of a general-purpose computer “can be reproduced by a perfect gas placed in a suitably shaped container and given appropriate initial conditions”. The paper credits one billiard ball design for the Fredkin gate itself to Richard Feynman and A. Ressler, and our page on the billiard ball computer explains how it works.

Fredkin, Toffoli and Feynman

Fredkin spent a year at Caltech from 1974 as a Fairchild Distinguished Scholar. The deal, as he told it, was that he would teach Richard Feynman about computers and Feynman would teach him quantum mechanics. The trade worked, and around 1980 Feynman was working out how a Fredkin gate could be built from nothing but colliding balls.

Toffoli had come to build machines for cellular automata, simple grid worlds whose cells update by fixed rules, under a grant Fredkin held at MIT’s Laboratory for Computer Science. His own reversible gate, the controlled-controlled-NOT now called the Toffoli gate, flips a third bit only when the first two are both 1. Both gates are reversible and either can build any classical calculation, though Fredkin, Wolfram recalls, thought the Toffoli gate was just a special case of his own.

In May 1981 Fredkin helped organise the Physics of Computation conference at MIT’s Endicott House, run jointly by MIT and IBM, where Richard Feynman gave the keynote. He argued that simulating nature efficiently would take a computer built from quantum parts, and our guide to the godfathers of quantum computing tells that story.

The quantum Fredkin gate

A quantum computer stores information in qubits, which can be in a superposition, a combination of 0 and 1 that is not secretly one or the other. Its gates must be reversible, because an isolated quantum system always evolves reversibly, and in an ideal circuit information is only thrown away by measuring or resetting qubits.

Every reversible classical gate, including Fredkin’s, has a direct quantum version, because shuffling bit patterns without losing any is a valid quantum operation. The quantum Fredkin gate follows the same rule on 0s and 1s, but when the control qubit is in a superposition the result is a superposition of the swapped and unswapped arrangements. If the two targets hold different states, this ties all three qubits together in what physicists call entanglement.

Gerard Milburn proposed the first quantum optical Fredkin gate in 1989, using single photons as qubits and a material whose effect on one beam of light depends on the intensity of another. In 1996 John Smolin and David DiVincenzo of IBM showed in Physical Review A that five gates acting on two qubits each are enough to build one.

It took until 2016 for a team at Griffith University and the University of Queensland, including Raj Patel and Geoff Pryde, to build one directly. Reported in Science Advances, their gate used entangled photons to perform the swap in one step. As with most photonic gates it worked only on the runs where the right photons were detected, but it made three-photon entangled states with fidelities of up to 93%.

The swap test, the gate’s best-known quantum job

The quantum Fredkin gate’s most famous job is the swap test, in which two quantum states sit on two registers and a single helper qubit acts as the control. The helper is put into superposition, the controlled swap is applied, and the helper is then brought back together and measured.

The helper reads 0 every time if the two states are identical, only half the time if they are completely distinguishable, and somewhere in between for states in between. Repeating the test on fresh copies and counting the 0s estimates how much the two states overlap, without anyone having to learn what either state is.

Harry Buhrman, Richard Cleve, John Watrous and Ronald de Wolf used the test in their 2001 paper on quantum fingerprinting, in Physical Review Letters. It lets two parties check whether long pieces of data match by sending much shorter quantum fingerprints.

The swap test has since turned up in proposals for quantum machine learning, where comparing data points is the core task. It also features in recent work on cutting the number of swap tests needed for harder measurements.

Why the Fredkin gate still matters

The Fredkin gate’s first lesson was that computing need not throw information away, and quantum computers take that as a law for their gates. Any ordinary calculation inside a quantum algorithm must be built as a reversible circuit, and the tricks for managing spare bits worked out by Bennett, Fredkin and Toffoli became standard practice. Shor’s factoring algorithm, for instance, runs its arithmetic on reversible circuits built from gates such as Toffoli’s.

On today’s hardware the Fredkin gate is rarely a single physical operation, because compilers break it into a Toffoli gate between two controlled-NOT gates. On an error-corrected machine it costs about as much as a Toffoli, one of the costliest of the standard operations, and a guide to quantum circuits shows how such building blocks are put together.

Fredkin himself was never much taken with standard quantum mechanics and hoped it would one day be explained by a simpler, digital picture of the universe in which everything is made of bits. He called the idea digital philosophy and it remains a minority view, yet the gate that carries his name ended up most at home in quantum computing.

Edward Fredkin and the Fredkin gate, year by year