Fredkin (CSWAP) gate

Definition

$$\mathrm{CSWAP}|c,a,b\rangle = |c,\, (1-c)a + cb,\, (1-c)b + ca\rangle = \begin{cases} |c,a,b\rangle & c=0 \\ |c,b,a\rangle & c=1 \end{cases}$$

As an $8\times 8$ permutation matrix, $\mathrm{CSWAP}$ is the identity on the four $c=0$ basis states and the identity except for exchanging $|101\rangle\leftrightarrow|110\rangle$ on the $c=1$ block (the $|100\rangle$ and $|111\rangle$ states, having $a=b$, are unaffected by the swap).

Action and conservation law

Unlike Toffoli, which computes a genuinely new bit (the AND), $\mathrm{CSWAP}$ only ever permutes its two target bits. This makes it conservative: the Hamming weight of the two target qubits is invariant under $\mathrm{CSWAP}$, a structural property Fredkin and Toffoli's original 1982 paper on conservative reversible logic used to model computation with a fixed particle count.

Decomposition

The naive decomposition is a CNOT–Toffoli–CNOT sandwich (target $b$ CNOT-copied onto $a$'s role, a Toffoli implementing the conditional exchange, then the CNOT undone) — 2 CNOTs plus 1 Toffoli, which itself costs 6 more CNOTs. Smolin and DiVincenzo (1996) improved on this with an explicit five-two-qubit-gate construction, showing the naive count is not optimal and giving numerical evidence that five is minimal.

Key identities

• $\mathrm{CSWAP}^2 = I$: applying the same controlled-swap twice restores the input.
• $\mathrm{CSWAP}$ is the core primitive of the SWAP test: preparing a control qubit in $|+\rangle$, applying $\mathrm{CSWAP}$ between two unknown states, then measuring the control in the $X$ basis estimates $|\langle\psi|\phi\rangle|^2$ without ever measuring $|\psi\rangle$ or $|\phi\rangle$ directly.
• Like Toffoli, $\mathrm{CSWAP}$ has no native two-qubit hardware realization and must be compiled from the elementary gate set for execution.