Fredkin (Controlled-SWAP or CSWAP) swaps two qubits if a third control qubit is $|1\rangle$. The quantum analog of a multiplexer and is universal for reversible classical computation.

Action: $|c ab\rangle \to |c (a' b')\rangle$ where $a' = c \cdot b + \bar{c} \cdot a$ and $b' = c \cdot a + \bar{c} \cdot b$ (conditional swap). If control is 0, qubits unchanged; if control is 1, qubits swap.

$$\text{Fredkin} = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix}$$

Basis action: swaps qubits 2 and 3 when qubit 1 is $|1\rangle$. Mapping: $|101\rangle \to |110\rangle$ and $|110\rangle \to |101\rangle$.

• Self-inverse: $\text{Fredkin}^2 = I$
• Universal: Fredkin alone is universal for reversible classical computation
• Symmetric: the two swapped qubits are treated identically
• Conservative: preserves Hamming weight (number of 1s in bitstring)

Both Toffoli and Fredkin are universal for classical reversible computation. They are dual in a sense: Toffoli flips, Fredkin swaps.

• Multiplexing: classical multiplexer logic implemented reversibly
• Quantum FFT: appears in some Fourier transform implementations
• Reversible circuits: designing reversible algorithms
• Conservation laws: Fredkin preserves Hamming weight (useful for systems with conservation laws)

• Gate cost: ~6+ CNOT gates + single-qubit gates (expensive like Toffoli)
• Structure: multiple CNOT layers and single-qubit rotations

• Superconducting qubits: CNOT and single-qubit gate decomposition; gate time similar to Toffoli (expensive)
• Trapped ions: multi-step laser pulse sequence
• Photonic: post-selection or nonlinear schemes
• Availability: native Fredkin rare; decomposition typical

• Conditional vs unconditional: Fredkin conditional on control qubit (unlike SWAP)
• Cost trade-off: Fredkin more expensive than SWAP but enables reversible classical logic