Fredkin gate

The Fredkin gate is a universal reversible logic gate with three inputs and three outputs, invented by Edward Fredkin in the early 1980s. It is a controlled swap gate: if the first input (the control bit) is 0, the second and third inputs pass through unchanged; if the control bit is 1, the second and third inputs are swapped. Like the Toffoli gate, the Fredkin gate is its own inverse — applying it twice returns the original state — and it is computationally universal, meaning any conventional Boolean circuit can be constructed from Fredkin gates alone.

The gate's significance extends beyond circuit design. In reversible computation, the Fredkin gate demonstrates that logical universality does not require information destruction. Every bit of output can be traced backward to a unique bit of input, preserving the bijective mapping that makes reversal possible. This property connects the Fredkin gate to the physical foundations of computation: since Landauer's principle identifies information erasure as the source of thermodynamic cost in computing, a Fredkin-gate computer can, in principle, operate arbitrarily close to zero energy dissipation.

The Fredkin gate also has a remarkable conservation property: it conserves the number of 1s in its inputs. This "billiard ball" character — it merely rearranges bits without creating or destroying them — makes it a natural primitive for conservative logic, a branch of reversible computing where not only information but also other conserved quantities (charge, particle number) are preserved. Fredkin and Tommaso Toffoli showed that conservative logic is sufficient for universal computation, establishing that the constraints of reversibility and conservation are not obstacles to computational power but merely different design rules.

In the broader landscape of computation, the Fredkin gate stands as evidence that the classical notion of irreversible Boolean logic is a contingent engineering choice, not a necessary feature of computation. The universe at the quantum level is reversible; irreversibility is an emergent property of large ensembles. The Fredkin gate is a bridge between these scales — a classical device that respects the same conservation laws as its quantum substrate.

The Fredkin gate is not merely a curiosity of reversible logic. It is a proof that the apparent irreversibility of ordinary computation is an artifact of abstraction, not physics. Every time a programmer writes `x = 0` and destroys the previous value, they are performing an operation that the universe itself avoids. The Fredkin gate suggests that the computational paradigms we consider natural are, in fact, thermodynamically extravagant — and that a deeper understanding of computation requires us to unlearn the habit of throwing information away.