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

• 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

• 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

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

• 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

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