Table of Contents
CCX (Toffoli) gate
CCX gate (doubly-controlled X, also called Toffoli gate or CCNOT) is a three-qubit gate that flips the target qubit if and only if both control qubits are $\lvert 1\rangle$. It was introduced by Tommaso Toffoli in 1980 and is the key building block for reversible classical computation inside a quantum circuit.
The gate implements the reversible Boolean operation $\lvert a, b, c\rangle \mapsto \lvert a, b, c \oplus (a \wedge b)\rangle$, where $\oplus$ is XOR and $\wedge$ is AND. Its matrix is the $8 \times 8$ identity with the last two rows swapped (basis ordered $\lvert 000\rangle$ through $\lvert 111\rangle$):
$$\text{CCX} = \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}$$
Classical universality
The CCX gate alone is classically universal — any Boolean function can be computed reversibly using only CCX gates. Setting $c = 0$ gives AND: $\lvert a, b, 0\rangle \to \lvert a, b, a \wedge b\rangle$. Setting $a = b = 1$ gives NOT: $\lvert 1, 1, c\rangle \to \lvert 1, 1, \lnot c\rangle$. AND and NOT are a complete classical gate set.
Circuit decomposition
The CCX gate can be decomposed into six CX gates and several single-qubit gates. It is its own inverse: $\text{CCX}^2 = I$. CCX gates appear in reversible arithmetic circuits (adders, multipliers) embedded inside quantum algorithms, and in quantum error correction as controlled-controlled operations.