The Fredkin Gate

The Toffoli gate earns its keep by flipping a bit under a condition. Its great rival — proposed by Ed Fredkin — never flips anything at all. The Fredkin gate, or controlled-SWAP, only ever rearranges: one control bit c decides whether two data bits x and y pass straight through or trade places.

(c, x, y) \;\longmapsto\; \begin{cases} (c, x, y) & \text{if } c = 0 \quad \text{(straight through)}\\[2pt] (c, y, x) & \text{if } c = 1 \quad \text{(swapped)} \end{cases}

Think of a railway switch: two trains (the data bits) roll in on two tracks, and the signalman (the control) sets the points — either each train keeps its own track, or the tracks cross. No train is ever created, destroyed, or altered. Computation as routing — an idea this gate will carry all the way into the next lesson.

The truth table

Writing the outputs with conditional expressions, the middle output is c \mathbin{?} y : x and the last is c \mathbin{?} x : y. All eight rows:

cxy in	cxy out	what happened
000	000	c = 0 — straight through
001	001	straight through
010	010	straight through
011	011	straight through
100	100	c = 1 — swap (nothing to see: x = y)
101	110	swap: the 1 moves to the other track
110	101	swap: the 1 moves back
111	111	swap (invisible again: x = y)

Every pattern appears once on the right: a permutation — in cycle notation the transposition (\,101\;110\,). And a swap done twice is no swap at all, so the Fredkin gate is self-inverse. But look closer at the table and a new property appears, one the Toffoli gate does not have: every output row contains exactly as many 1s as its input row. Of course it does — swapping two bits can shuffle the 1s between wires but can never mint or melt one. The Fredkin gate conserves the number of 1s, as if they were particles.

The circuit symbol

A filled dot on the control wire, a × on each of the two data wires, one vertical line through all three. Step the figure to see the two settings of the railway switch:

All of logic, from a switch and some constants

A gate that only reroutes sounds too polite to compute. It isn't — feed it constants, exactly as we fed the Toffoli gate an ancilla, and ordinary logic falls out of the routing. Write F(c, x, y) for the gate's three outputs and work each case from the rule "c = 1 means swap":

AND. Compute F(x, y, 0) — the first input bit is the control now. If x = 0: no swap, outputs (x, y, 0). If x = 1: swap, outputs (x, 0, y). The third output is 0 when x = 0 and y when x = 1 — that is exactly x \wedge y. (The middle output, \bar{x} \wedge y, comes along for the ride.)
OR. Compute F(x, 1, y). Third output: y when x = 0, and (after the swap) 1 when x = 1 — that is x \vee y.
NOT and FAN-OUT, in one go. Compute F(c, 0, 1). If c = 0: (c, 0, 1); if c = 1: (c, 1, 0). Read the outputs as (c,\; c,\; \bar{c}) — the middle wire is a fresh copy of c and the last wire is \bar{c}. One gate, two constants, and you get both the copier and the inverter.

Check the AND case against the truth table if you like: F(1, 1, 0) is row 110 \to 101, third bit 1 = 1 \wedge 1; and F(1, 0, 0) is row 100 \to 100, third bit 0 = 1 \wedge 0. ✓

maps (c, x, y) \mapsto (c,\; c \mathbin{?} y : x,\; c \mathbin{?} x : y): the control passes through, and the two data bits swap exactly when c = 1;
is the transposition (\,101\;110\,) of the 8 patterns, and is self-inverse;
conserves the number of 1s — outputs always carry exactly as many 1s as the inputs;
with constants it yields AND (F(x, y, 0), third output), OR (F(x, 1, y), third output), and NOT plus a copy (F(c, 0, 1) = (c, c, \bar{c})) — so Fredkin gates plus constants can build any Boolean circuit.

Both gates are 3-bit, self-inverse, single-transposition permutations, and both (as the theorem pane says, and the universality lesson proves) can build all of logic from constants. So why keep two? The difference is what they promise physics. The Toffoli gate changes the number of 1s in its word (row 110 \to 111 creates a 1 from nowhere), so a 1 cannot be a conserved physical object. The Fredkin gate never does — which means its 1s can be actual things: charge packets, billiard balls, photons in a rail, trains on a track. That single property opens the door to building logic out of collisions and routing alone, the "conservative logic" of the next lesson. Choose Toffoli and your hardware must make and unmake; choose Fredkin and it need only steer.

The classic slip with Fredkin embeddings is grabbing the wrong wire. In F(x, y, 0) it is the third output that carries x \wedge y; the middle one carries the less famous \bar{x} \wedge y. Swap the two constant positions — F(x, 0, y) — and the roles trade places: now the middle output is x \wedge y. There is no substitute for the two-line sanity check: set c = 0 (no swap) and c = 1 (swap), write out both output triples, and read off which wire behaves like the function you want. Ten seconds of table work beats a memorised formula you half-remember.