In short: The Toffoli gate (CCNOT) is a three-qubit controlled-controlled-NOT that flips its target only when both controls are 1 — it is reversible and universal for classical logic, which is why every irreversible Boolean function (AND, OR, full adders) can be embedded losslessly inside a quantum circuit.
Why reversibility matters at all
A classical AND gate is a one-way street. Given the output 0 you cannot say whether the inputs were 00, 01, or 10 — information has been erased. Landauer's principle ties that erasure to a thermodynamic floor of kT·ln2 joules per bit (about 2.75 zJ at room temperature). Quantum mechanics is stricter still: unitary evolution is bijective, so every gate must be invertible. You simply cannot build a native, standalone AND gate on a quantum computer. To run classical logic — a modular adder inside Shor's algorithm, a comparator inside Grover's oracle — you must first rewrite it in reversible form. The Toffoli gate is the workhorse that makes that possible.
⚛️ Every reversible gate has exactly as many output lines as input lines, and its truth table is a permutation of the input rows. A 3-bit gate permutes the 8 possible states among themselves.
What the Toffoli gate actually does
CCNOT takes three bits: two controls a, b and one target c. It computes c' = c ⊕ (a·b) while leaving a and b untouched. In plain terms: flip the target iff both controls are 1. Because XOR is its own inverse, applying Toffoli twice returns you to the start — the gate is its own inverse, a property shared with CNOT and NOT.
| a | b | c | a' | b' | c' |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 0 |
Universality: AND, NAND, and fan-out for free
Set the target to a fresh ancilla initialised to 0. Then c' = 0 ⊕ (a·b) = a AND b. You have just computed a reversible AND. Because {AND, NOT} is a universal classical set, and Toffoli gives you NOT (set both controls to 1) plus AND, the Toffoli gate alone is classically universal. NAND falls out by initialising the target to 1. You can even copy a classical bit — forbidden for arbitrary quantum states by the no-cloning theorem, but perfectly legal for basis states — using a CNOT with a 0 ancilla.
? One Toffoli + ancillas reproduces any Boolean circuit. The cost is "garbage" bits that must be uncomputed (Bennett's trick) so the ancillas can be reused without leaking entanglement into the result.
Watch a bit flip: an animated CCNOT
The hardware reality: Toffoli is expensive
On real hardware you rarely have a native three-qubit gate. The standard decomposition of one Toffoli uses 6 CNOTs plus several single-qubit T and H gates. In fault-tolerant, surface-code machines the T gates dominate the cost: each logical T needs a distilled magic state, and a single Toffoli consumes roughly 7 T-gates (or 4 in optimised Toffoli-direct schemes). That is why "T-count" and "Toffoli-count" are the headline metrics in quantum resource estimation. When architects estimate the qubit-hours to break RSA-2048, it is the Toffoli count of the modular-exponentiation circuit — on the order of billions — that sets the bill.
The same reversible-logic discipline shows up in classical EDA too. Reversible and adiabatic logic styles are an active research topic for ultra-low-power design, and the synthesis-and-verification tooling from vendors such as Synopsys, Cadence, and Siemens EDA is routinely used to validate the classical control fabric that sits beside a quantum processor. If you are moving from front-end RTL into these flows, our partner's VLSI and physical-design training pairs well with the quantum track here.
Where it connects in the gate zoo
CCNOT generalises the two-qubit CNOT gate: add one more control line and you climb from controlled-NOT to controlled-controlled-NOT. Its cousin the Fredkin gate (CSWAP) is also reversible and universal but conserves the number of 1s, which matters for billiard-ball and conservative-logic models. For the full picture of how these fit together with H, T, and the Clifford+T set, see our walkthrough of building a universal quantum gate set. All three — NOT, CNOT, Toffoli — form a ladder of ever-more-controlled flips.
Want to simulate Toffoli circuits, build reversible adders, and estimate T-counts hands-on? The CourseTron Quantum Computing track takes you from single-qubit gates to fault-tolerant resource estimation with runnable notebooks.
Frequently asked questions
Is the Toffoli gate the same as a classical AND gate?
No. An AND gate has one output; Toffoli has three outputs and preserves its two control inputs. It computes AND into an ancilla, making the operation reversible, which a bare AND gate is not.
Why can't a quantum computer just use ordinary logic gates?
Quantum evolution must be unitary and therefore invertible. Irreversible gates like AND and OR destroy information and have no unitary representation, so classical functions must be re-expressed with reversible gates such as Toffoli before they run on a QC.
How many simpler gates does one Toffoli cost?
A common decomposition is 6 CNOTs plus H and T single-qubit gates. In fault-tolerant terms a Toffoli costs roughly 4–7 T-gates, which is why T-count and Toffoli-count are the main yardsticks in quantum resource estimation.
Is Toffoli universal for quantum computing?
It is universal for classical reversible computation. For full quantum universality you additionally need a gate that creates superposition, such as the Hadamard; Toffoli + Hadamard is a known universal quantum set.