Quantum Cookbook

Part V · Chapter 24

The Toffoli Gate

Read ~16 min Prerequisites Ch. 3, Ch. 23 Tools interactive CCX widget, code cell Live
Basic

Building a quantum oracle for some classical function f often means implementing ordinary logic gates — AND, OR, NOT — inside a quantum circuit. The catch: every quantum gate has to be reversible (Ch. 4: unitary), and a plain classical AND gate genuinely isn't — given the output, you can't recover the two inputs. The Toffoli gate is the fix: a reversible version of AND, and the single gate this entire problem reduces to.

The definition

Toffoli, also written CCX (controlled-controlled-X), acts on 3 bits: two controls a, b and a target c. It flips c if and only if both a and b are 1, and leaves a and b completely untouched:

CCX: (a, b, c) ↦ (a, b, c ⊕ (a AND b))

Fig. 24.1 — the standard circuit symboltwo filled dots, one ⊕
a b c
Identical visual grammar to Ch. 18's graph-state diagrams (filled dot = control) plus the familiar ⊕ target symbol from Ch. 3's CNOT — Toffoli is "CNOT with one extra control."
Intermediate
Fig. 24.2 — click a,b,c to toggle, watch the target fliplive truth table

Set both a and b to 1 — c flips. Set either to 0 — c is untouched, no matter what it is. This is reversible AND: knowing the output row, you can always read off the exact input row, which a plain classical AND gate never lets you do.

Why reversibility matters here specifically

Ch. 4 established that every quantum gate must be unitary, and unitary matrices are always invertible — quantum circuits can never destroy information the way a classical AND gate does (two 1-bit inputs collapsing to one bit of output, with no way back). Toffoli sidesteps this by keeping a and b around unchanged and only ever flipping c, which makes the whole operation its own perfect inverse: applying CCX twice returns exactly the original state.

Advanced

Universality: Toffoli alone can build anything reversible

The deeper reason this chapter exists at all: the Toffoli gate, together with simple bit preparation and discarding, is universal for classical reversible computation — any classical reversible circuit, of any size, can be built entirely out of Toffoli gates. Set c=0 as an ancilla and CCX literally computes ordinary AND; wire a NOT gate in front of an input and you get NAND, which is itself classically universal. This is exactly why oracle circuits for upcoming algorithms (Grover's, Ch. 28, in particular) get built from Toffoli gates: any classical function f can be compiled into Toffoli-based reversible logic, then wrapped with Ch. 23's phase-kickback trick to become a proper quantum phase oracle.

Fig. 24.3 — code, runs in your browser
The assertion would throw immediately if Toffoli weren't its own perfect inverse — it never does, for any of the 8 possible input rows.
Check your understanding

What does the Toffoli gate do to its three input bits?

Leaves the two control bits a,b unchanged; flips the target bit c if and only if both a and b are 1.

Check your understanding

Why can't a plain classical AND gate be used directly as a quantum gate?

Because it's not reversible — given the single output bit, you can't recover which of the (0,0), (0,1), (1,0) inputs produced it. Quantum gates must be unitary, and unitary operations are always invertible.

Check your understanding

How do you compute ordinary AND using a Toffoli gate?

Set the target bit c to 0 (an ancilla) before applying CCX. The output target bit is then exactly a AND b, while a and b themselves remain available unchanged.

Check your understanding

What does it mean for Toffoli to be "its own inverse," and why does that matter?

Applying CCX twice in a row returns the exact original state. This is what makes it reversible by construction — no information is ever discarded, unlike a plain AND gate.

Check your understanding

Why does Toffoli's universality matter for building quantum oracles?

Any classical function can be compiled into a reversible circuit built entirely from Toffoli gates, which can then be wrapped with phase kickback (Ch. 23) to become a genuine quantum phase oracle — this is the standard route from "I have a classical function" to "I have a usable quantum oracle."

Review queue

Scroll back to a chapter's quiz cards to review them once they're due — a full cross-chapter queue view is a planned upgrade.