HomeQuantum PhysicsLessonsToffoli Gate (CCX)

CCX

Toffoli Gate (CCX)

Multi-qubit3-qubitAND

Flips the target qubit only when both control qubits are $∣1 ⟩$ .

Intuition

The Toffoli gate is a three-qubit gate with two controls and one target. The target flips only when both controls are $∣1 ⟩$ . On definite classical inputs, this computes a reversible AND: the target ends up holding the AND of the two controls. On quantum inputs, it acts on all eight three-qubit basis states simultaneously in superposition. Toffoli alone is universal for classical reversible computing. Combined with Hadamard, it becomes universal for quantum computing.

Matrix representation

I_{8} with ∣110 ⟩ \leftrightarrow ∣111 ⟩

Action on states

∣ ab, c ⟩ \to ∣ ab, c \oplus (a \land b)⟩

Circuit

Open in simulator →

▶ Try it in the simulator

Full technical statement

Toffoli (CCX) is a three-qubit gate. Its action is |ab, c⟩ → |ab, c XOR (a AND b)⟩. Here XOR (exclusive or) flips a bit when the other bit is 1, and AND is 1 only when both inputs are 1. So the target bit c flips if and only if both controls a and b are 1. The gate is its own inverse (applying it twice restores the original state) and unitary (it preserves total probability). It can simulate any classical logic circuit reversibly. On quantum states, it applies the controlled-controlled-NOT operation coherently (preserving all quantum phases and amplitudes) across all branches of a superposition, without collapsing any of them.

What changes in measurements

The target qubit’s measurement outcome changes according to the AND of the two control qubits’ values.

What stays hidden until later

When controls are in superposition, Toffoli preserves all phases and amplitudes across all branches. The result is a quantum superposition, not a classical mixture.

Bloch sphere

Applies a conditional X rotation to the target qubit when both controls are $∣1 ⟩$ . The individual Bloch vectors depend on the full three-qubit state.

Truth table

|000⟩→|000⟩

|010⟩→|010⟩

|100⟩→|100⟩

|110⟩→|111⟩

|111⟩→|110⟩

Step-by-step example

Reversible AND computation

1Start with $∣110 ⟩$ . Both controls are $∣1 ⟩$ and the target is $∣0 ⟩$ .
2Apply Toffoli. Both controls are 1, so the target flips. The state becomes $∣111 ⟩$ .
3Start fresh with $∣100 ⟩$ . Only one control is $∣1 ⟩$ .
4Apply Toffoli. Both controls are not 1, so the target stays unchanged. The state remains $∣100 ⟩$ .
5In both cases, the target qubit now holds the AND of the two controls.

Where this gate appears

Implementing reversible classical logic inside quantum circuits
Quantum arithmetic circuits such as adders and multipliers
Constructing oracles for Grover’s search algorithm
Quantum error correction circuits
Universal classical computation: any Boolean function can be built from Toffoli gates

Connected gates

Toffoli = doubly-controlled X (CCX), extending CNOT by adding a second control
If one control is fixed to |1⟩, Toffoli reduces to an ordinary CNOT
Toffoli + H = a universal quantum gate set, sufficient to build any quantum circuit
Toffoli can be decomposed into 6 CNOTs and several single-qubit gates

Tempting but wrong

It is tempting to think Toffoli is a purely classical gate because its truth table matches AND. That sounds right because AND is a classical operation. What actually happens is that when the controls are in superposition, Toffoli produces a quantum superposition (with phases preserved) rather than a probabilistic classical mixture. The quantum version processes all input combinations simultaneously through amplitudes.

Why this gate matters for what comes next

Toffoli proves that quantum computing includes all of classical computing. Any classical algorithm can be embedded as a reversible quantum circuit using Toffoli gates. From there, quantum features like superposition and interference can be layered on top to achieve speedups.

Test your understanding

What classical logic gate does Toffoli implement reversibly?

▶ Try it in the simulator Quick reference →↗ Nielsen and Chuang, Quantum Computation and Quantum Information

← Back to all lessons