# Fredkin Gate (CSWAP)

**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$.

## Properties

- **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)

## Relation to Toffoli

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

## Uses

- **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)

## Decomposition

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

## Implementation

- **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

## Comparison to SWAP

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