# Toffoli Gate (CCX)

**Toffoli** (Controlled-Controlled-X or CCX) is a three-qubit gate: flips the target qubit if both control qubits are $|1\rangle$. The quantum AND gate and is universal for reversible classical computation.

Action: $|c_1 c_2 t\rangle \to |c_1 c_2 (t \oplus c_1 c_2)\rangle$ where $c_1, c_2$ are controls and $t$ is target. Flips target only if both controls are 1.

$$\text{Toffoli} = \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 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{pmatrix}$$

Basis state mapping: $|abc\rangle \to |ab(c \oplus (a \wedge b))\rangle$. Swaps $|110\rangle \leftrightarrow |111\rangle$.

## Properties

- **Self-inverse**: $\text{Toffoli}^2 = I$
- **Universal**: Toffoli alone is universal for reversible classical computation (can build AND, NAND, etc.)
- **Quantum universal** (with Hadamard): Toffoli + single-qubit gates form universal quantum gate set
- **Reversible**: implements reversible classical logic

## Uses

- **Quantum arithmetic**: addition, subtraction, multiplication in quantum algorithms
- **Classical simulation**: Deutsch-Jozsa and related algorithms
- **Reversible computing**: designing reversible classical circuits
- **Error correction**: appears in quantum error correction codes

## Decomposition

- **Gate cost**: ~6 CNOT gates + ~10 single-qubit gates
- **Complexity**: expensive operation; avoid when possible
- **Note**: complex multi-gate sequence (standard decomposition lengthy)

## Implementation

- **Superconducting qubits**: via gate decomposition; ~30–50 ns for single Toffoli or longer for full decomposition
- **Trapped ions**: scalable decomposition via laser interactions
- **Photonic**: probabilistic schemes or post-selection
- **Development**: some platforms creating native Toffoli implementations

## Dual Gate

- **Fredkin (CSWAP)**: swaps two qubits if third is $|1\rangle$; also universal for reversible classical computation