Toffoli Gate

The Toffoli gate is a three-qubit gate with two control qubits and one target qubit. It flips the target if and only if both controls are in the $|1\rangle$ state. Named after Tommaso Toffoli, who introduced it in 1980, this gate is universal for classical reversible computation: any Boolean function can be built from Toffoli gates alone. In quantum computing, it appears wherever classical logic must be embedded in a quantum circuit, most notably in the modular arithmetic subroutines of Shor’s algorithm.

The details

The Toffoli gate acts on the eight three-qubit basis states, leaving all unchanged except $|110\rangle \leftrightarrow |111\rangle$. Its action can be written compactly as:

$|a, b, c\rangle \to |a, b, c \oplus (a \cdot b)\rangle$

The $8 \times 8$ unitary matrix is the identity with the last two rows and columns swapped, corresponding to the Pauli-X acting on the target subspace conditioned on both controls being $|1\rangle$.

The circuit symbol places filled dots on the two control wires and an $\oplus$ on the target:

control₁ ──●──
            │
control₂ ──●──
            │
target   ──⊕──

Classical universality. The AND function is irreversible (two input bits produce one output bit, losing information). The Toffoli gate computes AND reversibly by storing the result in the target qubit while preserving both inputs. Combined with NOT (a special case of Toffoli with both controls fixed to $|1\rangle$), this is sufficient to implement any classical circuit. The CNOT gate is itself a special case of the Toffoli with one control fixed to $|1\rangle$.

Decomposition into native gates. The Toffoli is not a native gate on most quantum hardware. The standard decomposition uses 6 CNOT gates and several single-qubit gates (including T and $T^\dagger$ gates). This makes the Toffoli relatively expensive: each CNOT already has non-trivial error rates, so six of them compound quickly. Optimized decompositions using relative phase Toffoli variants can reduce cost when the gate’s global phase is unimportant.

Arithmetic circuits. The Toffoli gate is the core component of quantum half-adders and full-adders. A half-adder on qubits $|a, b, 0\rangle$ uses a Toffoli to compute the carry bit ($a \cdot b$) and a CNOT to compute the sum ($a \oplus b$). These adder circuits compose into the modular exponentiation needed for Shor’s algorithm.

In Qiskit:

from qiskit import QuantumCircuit

qc = QuantumCircuit(3)
qc.ccx(0, 1, 2)  # Toffoli: controls on qubits 0 and 1, target on qubit 2
print(qc.draw())

Fault-tolerant cost. In a fault-tolerant setting, the T gates in the Toffoli decomposition each require magic state distillation. Since the decomposition contains multiple T gates, and each distilled T-state may require thousands of physical qubits, the Toffoli is one of the most expensive standard operations in fault-tolerant computation. Reducing Toffoli count is a major optimization target for practical quantum algorithms.

Why it matters for learners

The Toffoli gate bridges classical and quantum computation. Understanding it clarifies why quantum computers can do everything classical computers can (classical reversible universality) and why embedding classical logic into quantum algorithms is expensive (the decomposition overhead). When you encounter resource estimates for fault-tolerant algorithms, the Toffoli count is often a headline metric alongside T-count.

Common misconceptions

Misconception 1: The Toffoli gate by itself is universal for quantum computation. It is universal for classical reversible computation, not for arbitrary quantum computation. You need to add the Hadamard gate (or another gate that creates superposition) to achieve quantum universality.

Misconception 2: The Toffoli gate is a Clifford gate. It is not. The Toffoli gate is outside the Clifford group, which means circuits using Toffoli gates are not efficiently simulable by the Gottesman-Knill theorem. Its decomposition requires non-Clifford T gates.

Misconception 3: Toffoli gates are only useful for reversible classical logic. While that is their origin, Toffoli gates appear throughout quantum algorithms. They are essential in Grover oracles (computing Boolean conditions), quantum arithmetic (adders, multipliers, modular exponentiation), and multi-controlled unitary constructions. Any algorithm that needs to evaluate a classical function coherently will rely heavily on Toffoli gates.

See also

• CNOT Gate
• T Gate
• Clifford Group
• Magic State Distillation
• Shor’s Algorithm