Edward Fredkin never finished college, yet he became a full professor at MIT, ran one of its biggest computer laboratories and gave his name to a logic gate now used in quantum computing. He was born in Los Angeles on 2 October 1934 and died in Brookline, Massachusetts, on 13 June 2023, aged 88.

In between he was a fighter pilot, a programmer, a company founder and a physicist of an unusual kind who never held a physics degree. Some of his ideas became standard parts of computer science, while others, like his belief that the universe is itself a computer, never caught on.

From fighter pilot to programmer

Fredkin was the son of Russian immigrants and studied chemistry and physics at Caltech, but he left partway through his second year. In 1952 he joined the US Air Force to train as a fighter pilot.

The Air Force found another use for him when in 1956 it sent him to MIT’s Lincoln Laboratory to work on SAGE, an air defence network and one of the first large computer systems. That was where he learned to program.

In 1958 J.C.R. Licklider hired him at Bolt Beranek and Newman, a research firm in Cambridge, Massachusetts, which later built the first routers for ARPANET, the forerunner of the internet. After seeing a prototype in December 1959, Fredkin persuaded BBN to buy the very first PDP-1, which was also the first computer Digital Equipment Corporation ever made.

The trie and Information International

In 1960 Fredkin published a short paper on what he called trie memory, taking the name from the middle of the word “retrieval”. A trie stores words as paths through a branching tree, one letter at each step, so looking a word up takes as many steps as the word has letters however many words are stored.

Spell checkers and autocomplete still rely on the idea more than sixty years later. In 1962 Fredkin founded Information International Inc., a company that built high-precision machines for moving images between film and computers.

A professor without a degree

Marvin Minsky then brought him to MIT, and in 1968 Fredkin became a full professor there although he had never graduated from college. From 1971 to 1974 he directed Project MAC, MIT’s large computing laboratory, which had grown out of early work on letting many people share one computer at the same time.

He then spent a year at Caltech as a Fairchild Distinguished Scholar, on a deal he liked to describe. As Fredkin told it, he would teach Richard Feynman about computers and Feynman would teach him quantum mechanics in return.

Reversible computing and the Fredkin gate

Fredkin’s deepest interest was what the laws of physics allow a computer to do. In 1961 Rolf Landauer of IBM had argued that erasing a single bit of information must give off a small amount of heat, so Fredkin set out to design a computer that erased nothing.

He and Tommaso Toffoli set out an answer in a 1982 paper called “Conservative Logic”, whose centrepiece is the Fredkin gate. This three-wire switch swaps two bits or leaves them alone depending on a third bit, the control, and it never loses information or changes the number of 1s that pass through it.

Fed with fixed 0s and 1s, a network of Fredkin gates can carry out any calculation an ordinary computer can. The same paper went further and showed that such gates could in principle be built from colliding balls, in what became known as the billiard ball computer.

Every gate on a quantum computer must also be reversible, so this work carried straight over, and our page on Fredkin and Toffoli’s reversible computing tells the wider story. The gate’s quantum version, the controlled swap, is used in the swap test, which estimates how alike two quantum states are by measuring only a helper qubit, over many repeats.

Fredkin did not design the other standard quantum gates, such as CNOT, which came from other people. His contribution was the controlled swap and the case that computing need not throw information away.

The chess prize

In 1980 Fredkin put up the Fredkin Prize of $100,000 for the first computer to beat a world chess champion. IBM’s Deep Blue team collected it in 1997, after their machine beat the reigning world champion, Garry Kasparov, in a six-game match held in New York City.

Fredkin joined Carnegie Mellon in 1984, won its Dickson Prize in Science the same year and later taught physics at Boston University. 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”.

Digital philosophy

His boldest idea was that the universe works like a computer, with space, time and matter made of discrete bits following simple rules at the smallest scale. He called this digital philosophy and hoped it would one day explain quantum mechanics, though few physicists have followed him.

Stephen Wolfram, who knew him for decades, wrote a long memoir of Fredkin that covers his life and ideas in detail. The trie he named runs inside software everywhere, and his gate is now part of quantum computing, built on the quantum mechanics he had hoped bits would one day explain.

More like this