Fredkin Gate

The Fredkin gate's afterlife is almost entirely the SWAP test, now a workhorse primitive across quantum information. Because $P(\text{control}=0)=\tfrac12(1+|\langle\psi|\phi\rangle|^2)$ turns an inner product into a measurable frequency, it is the standard way to estimate state fidelity against a target, to detect entanglement (a controlled-SWAP between two copies of a state estimates the purity $\mathrm{Tr}(\rho^2)$), and to compute kernels in quantum machine learning, where the similarity of two data-encoded states is exactly what a support-vector or clustering algorithm needs. Variational algorithms lean on it for cost-function evaluation, and destructive "Bell-basis" variants trade the controlled-SWAP for local measurements to save the expensive control qubit. On real hardware the gate is costly: compiled as one Toffoli plus two CNOTs it carries a $T$-count of seven, so a SWAP test on $n$-qubit registers needs $n$ controlled-SWAPs and on the order of $7n$ distilled magic states in a surface-code machine — which is why cutting controlled-SWAP $T$-count is an active compilation problem. Direct realizations exist too: in 2016 a Griffith University group implemented a photonic quantum Fredkin gate acting on single-photon polarization without decomposing it into two-qubit gates, and controlled-SWAPs have since run on trapped-ion and superconducting platforms. The conservative-logic thread lives on in reversible-computing research, where the promise Fredkin and Toffoli made — computation approaching Landauer's zero-dissipation limit — remains a target for ultra-low-power logic.

Read the Fredkin gate first as a railroad switch and it is disappointingly tame. Two signal tracks run across the page and a third track, the control, throws the switch: control off, the signals pass straight through on their own rails; control on, the two are cross-connected and swap rails. Nothing is ever lost — a signal is only rerouted — which is the conservation property drawn in metal. Because a swap can only move a $1$ from one wire to another, the gate can never change how many $1$s are present, so it shuffles the eight basis states only within fixed Hamming-weight sectors. The weight-0 state $|000\rangle$, the three weight-1 states, and $|111\rangle$ have nowhere to go, and among the three weight-2 states the only pair the control-on swap can exchange is $|101\rangle$ and $|110\rangle$. The whole gate is that one transposition, and the first figure draws it honestly, the two moved labels flagged in red.

Now hand the same gate a control in superposition and the switch stops choosing. Because $F$ is linear, a control spread across $|0\rangle$ and $|1\rangle$ is not read and resolved — both branches are written at once, and the gate ties whether-the-targets-were-swapped to the control's amplitude pattern. This is the coherent maybe-swap, and it is the whole reason the Fredkin gate matters to quantum information rather than only to reversible-logic theory. Put the control in $|+\rangle$, load the two targets with unknown states $|\psi\rangle$ and $|\phi\rangle$, and the branch that swapped and the branch that did not now carry different target states — unless $|\psi\rangle=|\phi\rangle$. A final Hadamard on the control makes those two branches interfere, and the probability of reading the control as $0$ turns out to measure exactly how alike the two states are. The second figure is that circuit, the SWAP test, with the interference made numerical.

Two facts finish the picture. First, the target labels $a$ and $b$ are interchangeable — the gate is symmetric under swapping which target is which. Second, entanglement is not automatic: feed the gate a control already in a definite basis state, or identical targets $|\psi\rangle|\psi\rangle$ (which SWAP leaves alone), and the output is a plain product state. The gate earns its quantum keep only when the control carries a genuine superposition and the two targets differ, so that the swapped and unswapped branches point somewhere distinguishable.

The most compact definition is a single line of modulo-2 arithmetic on the three bits, the reversible logic that names the gate. Everything below is a consequence of this rule plus linearity.

where: $c$ — control bit, $c\in\{0,1\}$; $a,b$ — the two target bits; $\oplus$ — addition modulo $2$ (XOR); $c(a\oplus b)$ — logical AND of $c$ with $a\oplus b$. The reading: the control passes through untouched, and each target is XORed with the quantity $c(a\oplus b)$, which is nonzero only when the control is on and the targets differ — precisely the condition under which a swap changes anything. Evaluating the two control cases collapses the formula to a conditional swap, which is worth writing on its own because it is how the gate is used in practice.

where: the $c=0$ branch is the identity on the targets ($a\oplus0=a$); the $c=1$ branch exchanges them, since $a\oplus(a\oplus b)=b$ and $b\oplus(a\oplus b)=a$. The reading: $F$ is the controlled-SWAP — off means pass-through, on means exchange. Made concrete as an operator on the eight-dimensional space, in the ordered basis $|cab\rangle=000,001,\dots,111$ with $c$ the most significant bit, the gate is a permutation matrix built from a $6\times6$ identity and one $2\times2$ swap block.

where: the only off-diagonal entries sit at indices $5$ and $6$, exchanging $|101\rangle\leftrightarrow|110\rangle$. The reading: every row and column has a single $1$, so the matrix merely relabels basis states and is automatically unitary; six labels map to themselves and one pair is transposed. Because that matrix is real and symmetric, it is at once Hermitian and unitary, which forces it to be its own inverse — the algebraic face of "swapping the same pair twice does nothing" — and its bit-permuting action makes the conservation law exact.

where: $F^\dagger$ — conjugate transpose (adjoint); $I$ — the $8\times8$ identity; $(\text{in})_i,(\text{out})_i$ — the $i$-th input and output bits. The reading: self-adjointness plus unitarity collapse to $F^2=I$, and the Hamming weight (number of $1$s) is unchanged because a swap moves a $1$ without creating or destroying it. Lifting the conditional swap off the basis states gives the controlled-$U$ form that places the Fredkin gate in the general controlled-gate family, here with $U=\mathrm{SWAP}$.

where: $|0\rangle\langle0|,\,|1\rangle\langle1|$ — orthogonal projectors on the control; $I_4$ — identity on the two-target space; $\mathrm{SWAP}$ — the two-qubit exchange, itself $\mathrm{CNOT}_{a\to b}\,\mathrm{CNOT}_{b\to a}\,\mathrm{CNOT}_{a\to b}$. The reading: the $|0\rangle$ branch applies the identity and the $|1\rangle$ branch applies SWAP, and because the projectors are orthogonal the two branches never interfere — replacing SWAP by any two-qubit $U$ gives a general controlled-$U$. Since hardware exposes only one- and two-qubit gates, the Fredkin gate is compiled down; the standard identity conjugates a Toffoli (controlled-controlled-NOT) by two CNOTs, and is the route by which its non-Clifford cost is counted.

where: $\mathrm{CNOT}_{b\to a}$ — CNOT with control $b$, target $a$; $\mathrm{Toffoli}_{c,a\to b}$ — controlled-controlled-NOT with controls $c,a$ and target $b$. The reading: the two CNOTs are Clifford (cheap), so the gate's fault-tolerant cost is carried entirely by the Toffoli, and Derivation A tracks a basis state through the three layers to prove the identity. Finally, the quantum application that makes the gate famous: on a superposed control the Fredkin gate is a coherent maybe-swap, and inside the SWAP test its interference reads out the overlap of two states.

where: $|\psi\rangle,|\phi\rangle$ — the two states loaded into the targets; the control begins in $|0\rangle$ and is Hadamarded before and after $F$. The reading: orthogonal states give $P=\tfrac12$ (a coin flip), identical states give $P=1$ (never fails), and the value in between estimates $|\langle\psi|\phi\rangle|^2$ — derived in full in Derivation C.

The pinned-input specializations below are where the gate's two faces — reversible logic and coherent comparison — become concrete, and they are the cases worth carrying in your head.

1 · Estimating an overlap with the SWAP test (fully worked)

Two single-qubit registers hold $|\psi\rangle=|0\rangle$ and $|\phi\rangle=|+\rangle=\tfrac1{\sqrt2}(|0\rangle+|1\rangle)$. Run the SWAP test. Find the exact probability of measuring the control in $|0\rangle$, say what a single shot tells you, and estimate how many shots are needed to pin the overlap to $\pm0.01$.

Step 1. Compute the overlap. $\langle\psi|\phi\rangle=\langle0|+\rangle=\tfrac1{\sqrt2}$, so $|\langle\psi|\phi\rangle|^2=\tfrac12=0.5$. The two states are neither identical nor orthogonal — they sit exactly halfway.

Step 2. Apply the readout formula (7): $P_0=\tfrac12(1+0.5)=\mathbf{0.75}$, and correspondingly $P_1=1-P_0=\mathbf{0.25}$. The control comes up $0$ three times in four and $1$ once in four. A single shot is nearly useless — a lone "$0$" is consistent with any overlap from $0$ to $1$ — because the test is a Bernoulli trial and the overlap lives in its bias, not in any one outcome.

Step 3. Invert to get the estimator: $|\langle\psi|\phi\rangle|^2=2P_0-1$. Estimating $P_0$ from $N$ shots has standard error $\sqrt{P_0(1-P_0)/N}=\sqrt{0.75\cdot0.25/N}=\tfrac{0.433}{\sqrt N}$, and the overlap error is twice that, $\tfrac{0.866}{\sqrt N}$. Setting $\tfrac{0.866}{\sqrt N}\le0.01$ gives $N\ge(86.6)^2\approx\mathbf{7500}$ shots. The overlap is knowable to two decimals only after a few thousand repetitions — the price of learning a quantum inner product without ever measuring either state directly.

2 · A reversible AND gate and its garbage (fully worked)

Pin the lower target to the constant $b=0$ and feed the control $c$ and upper target $a$ into a Fredkin gate. Tabulate the four classical inputs, identify the useful output, and account for the conservation law and the leftover "garbage" bits.

Step 1. Specialize equation (1) at $b=0$: $F|c,a,0\rangle=|c,\,a\oplus c\cdot a,\,c\cdot a\rangle=|c,\,a\wedge\bar c,\,a\wedge c\rangle$, since $a\oplus ca=a(1-c)=a\wedge\bar c$. The lower output is $a\wedge c$, a logical AND of the control and the upper target.

Step 2. Tabulate all four inputs $(c,a)$ with $b=0$:

The last column is exactly the AND truth table: it is $1$ only for $c=a=1$.

Step 3. Account for the bookkeeping. In every row the number of input $1$s equals the number of output $1$s — conservation holds line by line (e.g. row $c=1,a=1$: two $1$s in, two out). The AND lands on one wire; the other two outputs ($c$ and $a\wedge\bar c$) are garbage — bits the computation did not want but reversibility forbids discarding. A reversible circuit must carry or uncompute this garbage, which is why reversible arithmetic costs extra ancilla wires that a dissipative classical circuit would simply erase. On a fault-tolerant machine the same gate, compiled via equation (6), costs the non-Clifford budget of one Toffoli — a T-count of 7 magic states — which is what makes Fredkin-heavy reversible subroutines expensive to run.

The Fredkin gate carries the fingerprints of a physicist who was convinced, more literally than almost anyone, that the universe is a computation — and who built a gate that computes without spending energy to prove that logic and thermodynamics are one subject.

Texts. Nielsen and Chuang, Quantum Computation and Quantum Information, §1.4.1 (reversible logic and the Fredkin/Toffoli gates) and §3.2.5 · Preskill, Lecture Notes for Physics 219, Ch. 6 (classical and quantum reversible computation) · Watrous, The Theory of Quantum Information, Ch. 2 · Kitaev, Shen and Vyalyi, Classical and Quantum Computation, §2 · Mermin, Quantum Computer Science, Ch. 2 · Fredkin and Toffoli, "Conservative Logic," Int. J. Theor. Phys. 21, 219 (1982) · Buhrman, Cleve, Watrous and de Wolf, "Quantum Fingerprinting," Phys. Rev. Lett. 87, 167902 (2001) for the SWAP test. Key results to keep in mind: the $8\times8$ permutation matrix follows from the action rule $|c,a,b\rangle\mapsto|c,\,a\oplus c(a\oplus b),\,b\oplus c(a\oplus b)\rangle$, with the single transposition $|101\rangle\leftrightarrow|110\rangle$; the self-inverse and conservation properties $F^\dagger=F$, $F^2=I$; the compilation identity $F=\mathrm{CNOT}_{b\to a}\,\mathrm{Toffoli}_{c,a\to b}\,\mathrm{CNOT}_{b\to a}$ verified by direct basis tracking; the AND/NOT/fan-out specializations of the Boolean action; and the SWAP-test probability $P_0=\tfrac12(1+|\langle\psi|\phi\rangle|^2)$, including the worked value $P_0=0.75$ for $|\psi\rangle=|0\rangle$, $|\phi\rangle=|+\rangle$ (overlap $\tfrac12$). All matrix entries are $0$ or $1$; the $T$-count of $7$ is the standard Toffoli figure.

Prerequisites. SWAP Gate · CNOT Gate · Controlled-U Gates · Quantum Circuit Model. Leads to. Circuit Identities and Equivalences · Controlled-Z Gate · Phase Gates (S and T).

Ask the tutor: ask me to run any three-qubit state through the Fredkin gate, walk the SWAP test end to end for two states you choose, or compile a controlled-SWAP down to Toffoli and CNOTs and count its T gates.