Toffoli (CCX) gate

Definition

The Toffoli gate acts on the computational basis as

$$\mathrm{CCX}|c_1,c_2,t\rangle = |c_1,c_2,\, t \oplus (c_1 \wedge c_2)\rangle$$

flipping the target bit exactly when both controls are $1$. As an $8\times 8$ permutation matrix it is the identity everywhere except the $|110\rangle \leftrightarrow |111\rangle$ swap.

Reversible classical logic

$\mathrm{CCX}$ is the quantum realization of a reversible AND gate: with the target ancilla initialized to $|0\rangle$, $\mathrm{CCX}|c_1,c_2,0\rangle = |c_1,c_2,\,c_1\wedge c_2\rangle$ computes the logical AND while remaining unitary and reversible, unlike a classical AND gate which discards information. Nielsen and Chuang show this makes $\{\mathrm{CCX}\}$ alone universal for reversible classical computation, and $\{\mathrm{CCX}, H\}$ (or $\{\mathrm{CCX}\}$ plus any basis-changing single-qubit gate) universal for quantum computation.

Decomposition

$\mathrm{CCX}$ has no native two-qubit hardware analogue and is not itself Clifford. The standard circuit (Barenco et al. 1995; also Nielsen & Chuang Fig. 4.9) decomposes it into

$$6\ \text{CNOT gates} \;+\; 2\ H \;+\; 4\ T \;+\; 3\ T^\dagger$$

for a total $T$-count of 7 — the standard resource figure quoted when estimating the fault-tolerant cost of a circuit that uses Toffolis, since $T$ gates (not Clifford gates) dominate magic-state distillation cost.

Key identities

• $\mathrm{CCX}$ is Hermitian and self-inverse: $\mathrm{CCX}^2 = I$.
• $\mathrm{CCX}$ is symmetric in its two control qubits but not in the target: swapping the two controls leaves the gate unchanged, swapping a control with the target does not.
• Multi-controlled-$X$ gates on more qubits ($C^nX$) are built recursively from Toffolis and ancilla qubits, making $\mathrm{CCX}$ the base case for the whole family used in Grover diffusion operators and reversible arithmetic circuits.