Three-qubit gates are $8 \times 8$ unitary matrices acting on a three-qubit system. They appear in fault-tolerant quantum computation and quantum arithmetic circuits. Any three-qubit gate decomposes into two-qubit and single-qubit gates, though the decompositions can be deep.

The Toffoli gate (doubly-controlled NOT, CCX) is the canonical three-qubit gate. It flips the target qubit if and only if both control qubits are $\lvert 1\rangle$:

$$\text{CCX}\lvert c_1 c_2 t\rangle = \lvert c_1 c_2\rangle \otimes \lvert t \oplus (c_1 \wedge c_2)\rangle$$

The Toffoli gate is classically universal: it can simulate any classical Boolean circuit reversibly, since it implements NAND when the target is initialized to $\lvert 1\rangle$. In quantum settings it appears in quantum arithmetic, stabilizer-code error correction circuits, and as a resource in magic state distillation for fault-tolerant $T$ gate implementations.

An ancilla-free Toffoli decomposes into 6 CX gates and several $T$, $T^\dagger$, $H$, and $S$ gates. The $T$ gate count matters for fault tolerance: logical $T$ gates are expensive to implement in error-correcting codes (they require distillation), so minimizing $T$-count in three-qubit gate decompositions is an active area of compilation research.

• CCX (Toffoli) gate — doubly controlled NOT (CCX)