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

Edward Fredkin, a college dropout who became an MIT professor, designed a logic gate that never throws information away. Forty years on, his controlled swap is a standard part of quantum computing. 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. Three wires. One control wire and two data wires go in and three wires come out, with the control passing through unchanged. Control 0, no change. The two data wires go straight through, and nothing happens to them. Control 1, swap. The two data wires trade places, which is why it is also called a controlled swap, or CSWAP. Nothing is lost. Each of the eight inputs gives its own output, so the input can always be recovered. Running the gate twice gives back exactly what went in. Bits are conserved. The number of 1s coming out always equals the number going in, because bits are moved but never…