Toffoli Gate

The Toffoli gate is the hinge on which the theory of reversible logic turns, and it wears two identities at once. Classically it is the reversible AND: Tommaso Toffoli introduced it in 1980 to answer a foundational worry — that ordinary gates like AND and OR erase information and therefore, by Landauer's principle, must dissipate energy. No one- or two-bit gate is universal for reversible classical computation, but this single three-bit gate is, mapping $(a,b,c)\mapsto(a,b,c\oplus ab)$ while remaining its own inverse. Quantum-mechanically it is the doubly-controlled-NOT: the target undergoes a Pauli $X$ exactly when both controls are $|1\rangle$ . Because it only permutes basis states it is a real permutation matrix — a classical gate promoted, unchanged, into the quantum circuit model, which is why it bridges both worlds. Two universality facts make it central. First, the Toffoli plus constant ancillas simulates any Boolean circuit, since it yields NAND, NOT, and FANOUT by fixing its inputs. Second, and more surprising, the Toffoli together with the Hadamard gate is universal for quantum computation even though every one of its matrix entries is real — a result of Shi and of Aharonov. Practically it is the workhorse of quantum arithmetic: ripple-carry adders, modular exponentiation in Shor's algorithm, Grover oracles, and syndrome extraction are all counted in Toffolis. Because hardware offers only one- and two-qubit gates, the recurring theme is compiling the Toffoli cheaply — six CNOTs by Barenco et al., or seven $T$ gates in the fault-tolerant setting where that count sets the bill.

Key takeaways

The Toffoli gate (controlled-controlled-NOT, CCNOT) is a three-qubit gate that flips a target qubit if and only if both controls are $|1\rangle$ , acting as $|a,b,c\rangle\mapsto|a,b,c\oplus ab\rangle$ and leaving the other seven basis states fixed.
It is universal for reversible classical computation: fixing its inputs yields NAND, NOT, and FANOUT, so any Boolean function is expressible in Toffolis plus ancillas.
Its $8\times8$ matrix is the identity except that it swaps $|110\rangle\leftrightarrow|111\rangle$ ; it is Hermitian, self-inverse ( $\mathrm{TOF}^2=I$ ), and has determinant $-1$ .
Combined with Hadamard it is universal for quantum computation, and conjugating its target by $H$ turns it into the controlled-controlled- $Z$ gate that phase oracles need.
Compiling it costs six CNOTs plus single-qubit gates with no ancilla (Barenco); fault-tolerantly it costs seven non-Clifford $T$ gates, which is why Toffoli count is the headline resource metric.
Key idea: the Toffoli gate flips its target iff both controls are $|1\rangle$ , $|a,b,c\rangle\mapsto|a,b,c\oplus ab\rangle$ — self-inverse, universal for reversible classical logic, quantum-universal once paired with Hadamard, and the elementary building block of all quantum arithmetic.

The core insight

The Toffoli gate flips its target iff both controls are $|1\rangle$ , $|a,b,c\rangle\mapsto|a,b,c\oplus ab\rangle$ ; it is self-inverse, universal for reversible classical computation, and — together with Hadamard — universal for quantum computation, while being the elementary building block of all quantum arithmetic.

Where this lives today

The Toffoli is no longer only a theorist's gate — it is a benchmark and a budget line. It has been demonstrated on hardware: Monz and collaborators realized a three-qubit Toffoli in a trapped-ion register in 2009, and superconducting processors implement it by compilation or via engineered higher-level transitions. In the fault-tolerant era it is the unit of account: because Clifford operations are cheap under the surface code but each $T$ gate demands a distilled magic state, algorithm cost is quoted in Toffolis or $T$ gates. Gidney and Ekerå's 2021 estimate for factoring a 2048-bit RSA key — famously "8 hours on 20 million noisy qubits" — is dominated by roughly $3\times10^{9}$ Toffoli gates in the modular-exponentiation core. The same accounting drives active research into cheaper Toffolis: measurement-assisted "temporary AND" constructions spending only four $T$ gates, catalytic schemes, and layout-aware synthesis under lattice surgery. Every improvement to the humble CCNOT flows straight into the runtime of Shor's algorithm, Grover search, and quantum chemistry — which is why "reduce the Toffoli count" is one of the most consequential optimization targets in the field.

The physical picture

Think of the Toffoli as an AND gate rebuilt so that nothing is thrown away. A classical AND takes two bits to one and loses information; the Toffoli keeps the two inputs as controls and writes their AND into a fresh third wire prepared in $c=0$ , giving $(a,b,0)\mapsto(a,b,ab)$ . Because both inputs survive, the map is a bijection — run the gate again and it undoes itself. On the eight basis states it does nothing unless both controls are set: seven states are fixed, and only the pair $|110\rangle$ and $|111\rangle$ are exchanged, so the $8\times8$ unitary is the identity with a single Pauli- $X$ block in the corner. The first figure draws the gate and makes that exchange the whole story.

Figure

The Toffoli gate as a reversible circuit — two solid control dots and one target ⊕. The target flips only when both controls read 1, so among the eight basis states only the pair 110 and 111 is exchanged, realizing the action a,b,c → a,b,c⊕ab with the gate its own inverse

Universality arrives in two flavours. Classically, by choosing the inputs you turn the one gate into a whole logic family: both controls 1 gives NOT; $c=0$ gives AND; one control 1 copies the other (FANOUT); and $c=1$ gives NAND, the single gate from which all Boolean logic is built. Quantum-mechanically the same permutation, sandwiched between Hadamards on the target, converts the conditional bit-flip into a conditional phase — linking the Toffoli to the controlled-controlled- $Z$ and the phase oracles of Grover search. The one thing it cannot do alone is create a superposition, since its matrix is real; that is Hadamard's job. The second figure is what an engineer reaches for: the compiled circuit and the gate count that governs its cost.

Figure

Compiling the Toffoli into hardware-native gates (the Nielsen–Chuang circuit) — the exact ancilla-free construction uses 6 CNOTs plus 7 gates from the set T and T† and 2 Hadamards. The T-count of 7 is the number that makes the Toffoli expensive on a fault-tolerant machine, since every T gate must be supplied by magic-state distillation

The core equations

The gate is defined by its action on a basis state: it adds the AND of the two controls, modulo 2, onto the target and leaves the controls untouched.

\mathrm{TOF}\,|a,b,c\rangle = |a,\,b,\,c\oplus ab\rangle \qquad (1)

where: $a,b$ — control bit values, $a,b\in\{0,1\}$ ; $c$ — target bit value; $\oplus$ — addition modulo 2 (XOR); $ab$ — logical AND of the controls (ordinary product of bits). Reading: the target flips ( $c\to c\oplus1$ ) precisely when $ab=1$ , i.e. when both controls are set, and is otherwise left alone. Ordering the basis by the binary index $4a+2b+c$ from $|000\rangle$ (0) to $|111\rangle$ (7), equation (1) becomes an explicit permutation matrix — the identity everywhere except a Pauli- $X$ block on the last two states.

\mathrm{TOF} = \begin{pmatrix} 1&0&0&0&0&0&0&0\\ 0&1&0&0&0&0&0&0\\ 0&0&1&0&0&0&0&0\\ 0&0&0&1&0&0&0&0\\ 0&0&0&0&1&0&0&0\\ 0&0&0&0&0&1&0&0\\ 0&0&0&0&0&0&0&1\\ 0&0&0&0&0&0&1&0 \end{pmatrix} \qquad (2)

where: $\mathrm{TOF}$ — the $8\times8$ Toffoli unitary. Reading: rows 0–5 carry a diagonal $1$ because there $ab=0$ ; the lower-right block swaps index 6 ( $|110\rangle$ ) with index 7 ( $|111\rangle$ ). The same operator, written with projectors, exposes the "controlled-controlled" logic directly: apply $X$ to the target only in the sector where both controls project onto $|1\rangle$ .

\mathrm{TOF} = |0\rangle\langle0|\otimes I\otimes I \;+\; |1\rangle\langle1|\otimes\Big(|0\rangle\langle0|\otimes I + |1\rangle\langle1|\otimes X\Big) \qquad (3)

where: $|0\rangle\langle0|,\,|1\rangle\langle1|$ — projectors onto the control states; $I$ — $2\times2$ identity; $X$ — Pauli $X$ on the target. Reading: the nested structure reads "if control 1 is set, then if control 2 is set, flip the target" — the definition of a doubly-controlled gate. Three algebraic facts follow immediately and are worth memorizing — the sanity checks a compiler applies to any candidate Toffoli.

\mathrm{TOF}^2 = I,\qquad \mathrm{TOF}^\dagger = \mathrm{TOF},\qquad \det(\mathrm{TOF}) = -1 \qquad (4)

where: $\mathrm{TOF}^2$ — the gate composed with itself; $\dagger$ — Hermitian conjugate; $\det$ — determinant. Reading: $c\oplus ab\oplus ab=c$ makes the gate its own inverse; being a real symmetric permutation it is Hermitian; and swapping exactly one pair of states is a single transposition, whose sign is $-1$ . Conjugating the target — and only the target — by Hadamard gates converts the conditional bit-flip into a conditional sign, turning the Toffoli into the controlled-controlled- $Z$ that phase oracles use.

(I\otimes I\otimes H)\,\mathrm{TOF}\,(I\otimes I\otimes H) = \mathrm{CCZ} = \mathrm{diag}(1,1,1,1,1,1,1,-1) \qquad (5)

where: $H$ — Hadamard on the target; $\mathrm{CCZ}$ — controlled-controlled- $Z$ , which multiplies $|111\rangle$ by $-1$ . Reading: it uses only $HXH=Z$ ; because CCZ is diagonal and symmetric in its three qubits, "control" and "target" become interchangeable here. Finally, since hardware supplies only one- and two-qubit gates, the Toffoli must be compiled — the standard exact cost being the Barenco construction.

\Lambda_2(X) \;=\; \underbrace{6\ \text{CNOTs}}_{\text{two-qubit}} \;+\; \underbrace{\{H,\,T,\,T^\dagger\}}_{\text{single-qubit}},\qquad T=\mathrm{diag}\!\left(1,e^{i\pi/4}\right) \qquad (6)

where: $\Lambda_2(X)$ — the doubly-controlled $X$ , i.e. the Toffoli; $T,\,T^\dagger$ — the $\pi/8$ phase gate and its inverse; $H$ — Hadamard. Reading: six CNOTs is optimal for an exact ancilla-free Toffoli, and the seven $T$ / $T^\dagger$ gates are the fault-tolerantly expensive non-Clifford part.

Derivation AToffoli is universal for reversible classical computation

The goal is to prove that this one three-bit gate, with ancilla wires held at fixed constants, can compute any Boolean function whatsoever — the statement that makes it the classical analogue of NAND. A set of reversible gates is classically universal if, allowing ancillas initialized to constants and uncomputing garbage at the end, it realizes every function on bit strings. Since NAND is already functionally complete, it is enough to show the Toffoli produces NAND plus a way to copy bits, then to restore reversibility by uncomputation.

Step 1. Set the target constant to $c=1$ . Then $\mathrm{TOF}|a,b,1\rangle=|a,b,\overline{ab}\rangle$ , and $\overline{ab}$ is exactly $a\,\mathrm{NAND}\,b$ . Why: NAND is functionally complete on its own, so getting it from a fixed input choice already guarantees every Boolean function is reachable.

Step 2. Set both controls to $1$ : $\mathrm{TOF}|1,1,c\rangle=|1,1,\bar c\rangle$ , the NOT gate on the target. Why: reversible logic must be able to negate a wire, and here it costs nothing but a choice of ancilla values.

Step 3. Set one control to $1$ and the target to $0$ : $\mathrm{TOF}|1,b,0\rangle=|1,b,b\rangle$ , copying $b$ onto a second wire. Why: reversible circuits have no free one-bit FANOUT, so this controlled copy is what lets a signal branch to two later gates.

Step 4. Assemble any Boolean circuit from these NAND and FANOUT primitives, tracking the "garbage" bits reversibility forces you to keep; then run a mirror-image copy to uncompute the garbage back to constants, keeping only the answer — Bennett's trick. Why: without uncomputation the accumulated garbage would block ancilla reuse; Bennett's construction shows the reversibility overhead is only a constant factor.

Go deeper · Derivation B · 1 minThe Hadamard sandwich and the controlled-controlled-Z gate

Derivation BThe Hadamard sandwich and the controlled-controlled-Z gate

The goal is to show that conjugating the Toffoli's target wire by Hadamard gates produces the controlled-controlled- $Z$ gate, the identity behind every phase oracle in Grover search and amplitude amplification. Phase oracles mark an answer not by flipping a bit but by attaching a $-1$ sign, so oracle construction computes a predicate into an ancilla, converts that bit into a sign, and uncomputes. The bit-to-sign conversion is just the single-qubit identity $HXH=Z$ promoted to the controlled setting, which this derivation makes explicit.

Step 1. Write the Toffoli in projector form, $\mathrm{TOF}=P_0\otimes I + P_1\otimes(P_0'\otimes I + P_1'\otimes X)$ , with $P_0=|0\rangle\langle0|$ , $P_1=|1\rangle\langle1|$ on the two controls, so that the target sees $X$ only in the $|11\rangle$ control sector. Why: isolating the target factor is what lets us conjugate it without disturbing the control structure.

Step 2. Sandwich the target by $H$ . Where the Toffoli applied $I$ , $HIH=I$ leaves it unchanged; where it applied $X$ , we get $HXH$ . Why: conjugation acts factor-by-factor on a tensor product, so only the target operator is transformed and the control projectors are untouched.

Step 3. Substitute the fundamental identity

HXH = Z

so the $|11\rangle$ sector now applies $Z$ to the target instead of $X$ . Why: this is the exact point at which a conditional bit-flip becomes a conditional phase — the mechanism a phase oracle exploits.

Step 4. Collect: the operator applies $Z$ only when both controls are $|1\rangle$ , i.e. it multiplies $|111\rangle$ by $-1$ and fixes the other seven states — exactly $\mathrm{CCZ}=\mathrm{diag}(1,1,1,1,1,1,1,-1)$ . Why: CCZ is diagonal and totally symmetric in its three qubits, so the "control" versus "target" distinction dissolves and it serves as a symmetric three-qubit phase. *The result is confirmed by direct computation: $(I\otimes I\otimes H)\,\mathrm{TOF}\,(I\otimes I\otimes H)$ has diagonal $(1,1,1,1,1,1,1,-1)$ and no off-diagonal entries.*

Go deeper · Derivation C · 1 minCounting the Barenco decomposition with a controlled square-root of NOT

Derivation CCounting the Barenco decomposition with a controlled square-root of NOT

The goal is to show why an exact ancilla-free Toffoli reduces to two-qubit gates with a count of six CNOTs, using the controlled- $V$ trick at the heart of the Barenco et al. synthesis. Real hardware executes only one- and two-qubit operations, so a three-qubit gate must be compiled, and the elegant route uses the fact that the Pauli $X$ has a unitary square root $V=\sqrt{X}=\tfrac12\!\begin{pmatrix}1+i&1-i\\1-i&1+i\end{pmatrix}$ , with $V^2=X$ and $V^\dagger V=I$ . The construction interleaves controlled- $V$ , controlled- $V^\dagger$ , and CNOTs so the net target operation is $X$ exactly when both controls are set and the identity otherwise.

Step 1. Assemble the standard sequence

\mathrm{TOF}=(C_1V)\,(\mathrm{CNOT}_{12})\,(C_2V^\dagger)\,(\mathrm{CNOT}_{12})\,(C_2V),

where $C_1V$ applies $V$ to the target controlled on qubit 1, and $C_2V$ controlled on qubit 2. Why: this five-piece pattern is the minimal controlled-root arrangement distinguishing "both controls set" from every other case.

Step 2. Take both controls set, $a=b=1$ . The two CNOTs leave the control parity so the surviving target factors compose to $V\cdot V=X$ — the desired flip. Why: $V^2=X$ is exactly "two half-flips make a full flip", which is why a square root of $X$ is the right building block.

Step 3. Take either control unset. Then a $V$ and a $V^\dagger$ always meet on the target and cancel, $VV^\dagger=I$ , leaving it untouched. Why: the unitarity of $V$ guarantees the cancellation, so the gate does nothing unless both controls are set.

Step 4. Count. Each controlled- $V$ or controlled- $V^\dagger$ expands into two CNOTs plus single-qubit rotations; simplifying yields the Barenco circuit of six CNOTs, which in the fault-tolerant $T$ -basis is the seven- $T$ circuit of the second figure. Without ancillas, six CNOTs is optimal. Why: the count is what gets billed on hardware, and its $T$ -part is what a fault-tolerant estimate pays for. *The two key identities $V^2=X$ and $VV^\dagger=I$ can be confirmed by direct matrix multiplication.*

Limiting cases

The Toffoli collapses to a gallery of simpler gates the moment you pin down one input — which is precisely why it is universal.

Case	Result	Meaning
Both controls set	$\vert 1,1,c\rangle \mapsto \vert 1,1,c\oplus 1\rangle$	With $a=b=1$ the target undergoes a NOT; fixing both controls to $\vert 1\rangle$ realizes a single-qubit $X$ .
Target initialized to zero	$\vert a,b,0\rangle \mapsto \vert a,b,ab\rangle$	With $c=0$ the gate writes the logical AND of the controls into the target — the reversible AND.
One control set	$\vert 1,b,c\rangle \mapsto \vert 1,b,c\oplus b\rangle$	Fixing $a=1$ reduces the Toffoli to a CNOT between the remaining control $b$ and the target.
Either control zero	$\vert 0,b,c\rangle \mapsto \vert 0,b,c\rangle$	If at least one control is $\vert 0\rangle$ the gate is the identity on all three qubits.
Target set to one	$\vert a,b,1\rangle \mapsto \vert a,b,\overline{ab}\rangle$	With $c=1$ the target carries $a\,\mathrm{NAND}\,b$ — the functionally complete classical gate.

Common trapThe Toffoli decomposes into a few two-qubit gates "for free", and the 3-CNOT version is just a cheaper Toffoli

Both halves are wrong. With no ancilla you need at least five two-qubit gates, and the standard exact construction spends six CNOTs plus single-qubit gates — no free lunch compiles a genuine Toffoli into two or three CNOTs. The famous three-CNOT "Margolus" gate is not the Toffoli: it reproduces the correct bit-flip pattern but stamps an extra $-1$ phase on one basis state (e.g. $|101\rangle$ ), so it is a relative-phase Toffoli, safe only when that stray phase is guaranteed to cancel later — typically because the ancilla is computed and then uncomputed, so the phase appears twice and squares to $+1$ . Drop a Margolus gate into a circuit that keeps its output and you have silently changed the unitary.

Worked examples

1 · The Toffoli generates entanglement (fully worked)

|\psi_{\text{in}}\rangle=\tfrac12\big(|000\rangle+|010\rangle+|100\rangle+|110\rangle\big).

Step 2. Act with the Toffoli term by term. Only $|110\rangle$ has both controls set, so only it changes, mapping to $|111\rangle$ ; the other three are fixed:

|\psi_{\text{out}}\rangle=\tfrac12\big(|000\rangle+|010\rangle+|100\rangle+|111\rangle\big).

Step 3. Normalization check: four terms of amplitude $\tfrac12$ give $4\times(\tfrac12)^2=1$ , so each basis outcome has probability $(\tfrac12)^2=\tfrac14$ and P(111) = 1/4.

Step 4. Note that $|\psi_{\text{out}}\rangle$ does not factor into three single-qubit states — the target is now correlated with "both controls are 1", which no product state can reproduce. From an unentangled input, the Toffoli has produced a genuinely entangled three-qubit state. This is the crux of quantum universality: Hadamards make the $|+\rangle$ superpositions and the Toffoli entangles them, so "Hadamard + Toffoli" reaches beyond classical reversible logic.

2 · The T-count of an 8-bit adder (fully worked resource estimate)

A ripple-carry (Cuccaro-style) adder for two $n$ -bit integers computes each carry bit as an AND with a Toffoli and then uncomputes it, using about $2n$ Toffolis plus a linear number of CNOTs. Estimate the fault-tolerant $T$ -count of adding two 8-bit numbers.

Step 1. Count Toffolis. With $n=8$ , the adder computes $n$ carry bits and later uncomputes them, using about $2n=\mathbf{16}$ Toffoli gates. The accompanying CNOTs and NOTs are Clifford and essentially free in the fault-tolerant cost model.

Step 2. Convert each Toffoli to its non-Clifford cost. The exact Toffoli of equation (6) uses 7 $T$ / $T^\dagger$ gates, and every $T$ gate must be supplied by magic-state distillation — the dominant expense of a surface-code machine.

Step 3. Multiply. The $T$ -count is $16\times7=\mathbf{112}$ $T$ gates — 112 distilled magic states for one 8-bit addition. The 4- $T$ "temporary AND" trick would cut this to about $16\times4=64$ .

Step 4. Interpret. This is why serious resource estimates — from Grover oracles to Shor's factoring — are quoted as a Toffoli count or $T$ -count rather than a raw gate count: the Cliffords are cheap and the Toffolis are the bill. 16 Toffolis → 112 T gates for one 8-bit add; the Toffoli count is the number to minimize.

3 · Building a Fredkin (controlled-SWAP) from one Toffoli

The controlled-SWAP gate exchanges qubits 2 and 3 when qubit 1 is $|1\rangle$ . Verify the identity $\mathrm{CSWAP}=\mathrm{CNOT}_{32}\,\mathrm{TOF}_{123}\,\mathrm{CNOT}_{32}$ on the input $|1,0,1\rangle$ , where $\mathrm{CNOT}_{32}$ has control qubit 3 and target qubit 2.

Step 1. First $\mathrm{CNOT}_{32}$ : qubit 3 is $1$ , so qubit 2 flips: $|1,0,1\rangle\to|1,1,1\rangle$ .

Step 2. $\mathrm{TOF}_{123}$ (controls 1,2, target 3): both controls are $1$ , so qubit 3 flips: $|1,1,1\rangle\to|1,1,0\rangle$ .

Step 3. Second $\mathrm{CNOT}_{32}$ : qubit 3 is now $0$ , so qubit 2 is unchanged, $|1,1,0\rangle\to|1,1,0\rangle$ . The net $|1,0,1\rangle\to|1,1,0\rangle$ has swapped qubits 2 and 3, as control $=1$ demands.

Step 4. Control-off check $|0,0,1\rangle$ : the outer CNOTs flip and unflip qubit 2 while the Toffoli does nothing (control 1 is $0$ ), returning $|0,0,1\rangle$ — no swap. CNOT–Toffoli–CNOT is a Fredkin.

Physics of the portrait

The Toffoli sits where thermodynamics meets computation: it was invented not to build a faster computer but to ask whether computing must cost energy at all.

Origins · 1 minTommaso Toffoli and how this was discovered

Tommaso Toffoli

born 1943, Italian-American physicist and computer scientist · reversible computation and the physics of information

Tommaso Toffoli was born in Montecatini Terme, Italy, in 1943, and earned his PhD at the University of Michigan in 1976. At the MIT Laboratory for Computer Science he worked closely with Edward Fredkin on the then-radical program of reversible and conservative computing — the idea that computation, done carefully, need not erase information and so need not pay Landauer's thermodynamic tax. His 1980 report "Reversible Computing" introduced the three-bit controlled-controlled-NOT gate that now bears his name and proved it universal for reversible classical logic; the companion Fredkin gate came from the same collaboration and its billiard-ball model of computation. His later work ranged over cellular automata and lattice-gas models of physics, always pressing the theme that physical law and computation are two views of one thing. When quantum computing arrived his gate was waiting: the CCNOT became the indispensable non-Clifford workhorse of quantum arithmetic and — with Hadamard — a universal set for quantum computation. A concept devised to save energy in classical circuits became a cornerstone of the quantum ones.

History

1961

— Landauer argues that erasing a bit must dissipate at least kT ln 2 of energy

1973

— Bennett shows any computation can be rearranged into a logically reversible one

1980

— Toffoli introduces the reversible controlled-controlled-NOT gate and proves it universal

1995

— Barenco and collaborators give the elementary-gate decomposition of the Toffoli

2003

— Shi proves that Hadamard plus Toffoli is universal for quantum computation

Going further

Texts. Nielsen & Chuang, Quantum Computation and Quantum Information, §1.4.1 (reversible logic) and §4.3 (universal gates, Barenco construction, Fig. 4.9) · Barenco et al., "Elementary gates for quantum computation", Phys. Rev. A 52, 3457 (1995) · Toffoli, "Reversible Computing", MIT/LCS/TM-151 (1980); ICALP 1980 · Preskill, Lecture Notes for Physics 219, Ch. 6 · Kitaev, Shen & Vyalyi, Classical and Quantum Computation, §8 · Shi, "Both Toffoli and Controlled-NOT need little help to do universal quantum computation", QIC 3, 84 (2003). Every matrix entry follows from evaluating $c\oplus ab$ on the eight basis states, from which one can confirm $\mathrm{TOF}^2=I$ , $\mathrm{TOF}^\dagger=\mathrm{TOF}$ , $\det=-1$ , and $(I\otimes I\otimes H)\,\mathrm{TOF}\,(I\otimes I\otimes H)=\mathrm{CCZ}$ . The resource counts — 7 $T$ gates per Toffoli and $\approx 2n$ Toffolis for an $n$ -bit adder — are standard fault-tolerant figures; the 2048-bit factoring estimate is from Gidney & Ekerå (2021).

Prerequisites. CNOT Gate · Controlled-U Gates · Pauli Gates (X, Y, Z) · Phase Gates (S and T) · Quantum Circuit Model. Leads to. Circuit Identities and Equivalences · Controlled-Z Gate · SWAP Gate.

Ask the tutor: Ask me to walk through the seven- $T$ Toffoli circuit gate by gate, or to show how a Grover oracle computes a predicate into an ancilla with Toffolis and converts it to a phase.

Why can no one- or two-bit gate be universal for reversible classical computation, but a three-bit gate can?

The obstruction is a conservation law. Every reversible one- or two-bit gate is linear (affine) over the two-element field, and composing linear gates only ever gives linear functions — so you can never build a nonlinear function like AND, essential to general computation. The Toffoli's output bit $c\oplus ab$ contains the product $ab$ , a genuinely nonlinear term, and three bits is the minimum width at which a reversible gate can carry that nonlinearity while staying a bijection. That single nonlinear term is why one gate suffices.

What is the difference between the Toffoli and the Fredkin gate?

Both are three-bit reversible gates from the same MIT program, but do different jobs. The Toffoli (CCNOT) uses two controls to decide whether to flip a target; the Fredkin (CSWAP) uses one control to decide whether to swap two bits. The Fredkin is "conservative" — it never changes the number of 1s — which the Toffoli is not. Each builds from the other with a couple of CNOTs (Worked Example 3 makes a Fredkin from one Toffoli), and both are universal for reversible classical computation. In quantum computing the Toffoli is the more common primitive, since so much of quantum arithmetic is controlled bit-flips.

What does it mean that the Toffoli is a "non-Clifford" gate, and why does that matter so much?

The Clifford group (generated by $H$ , $S$ , and CNOT) maps Pauli operators to Pauli operators; by the Gottesman–Knill theorem a circuit of only Clifford gates is efficiently simulable classically, so Cliffords alone give no quantum advantage. The Toffoli lies outside this group, which is exactly what lets Clifford + Toffoli circuits do what classical machines cannot. The catch is cost: fault-tolerantly, Clifford gates are cheap but non-Clifford gates like $T$ and Toffoli must be injected through magic-state distillation. So "non-Clifford" is at once the source of the Toffoli's power and the reason it dominates the resource budget.

Does a Toffoli really need seven T gates, or can I do better?

Seven is the count for the standard exact, ancilla-free Toffoli (Nielsen–Chuang, Fig. 4.9). You can do better by relaxing constraints. With one clean ancilla and a measurement, the "temporary AND" construction realizes a Toffoli for only four $T$ gates when it will later be uncomputed — common in arithmetic, where carries are computed and cleaned up. Catalytic techniques and magic-state cultivation push the amortized cost lower still. But for a genuine standalone Toffoli whose output you keep, with no ancilla, seven $T$ gates is the reference figure — and minimizing the number of Toffolis usually matters more than shaving the $T$ -cost of each.

When is it safe to use the cheaper three-CNOT Margolus gate?

The Margolus (relative-phase) Toffoli reproduces the correct bit-flip truth table but attaches an extra $-1$ phase to one basis state, so it is not the Toffoli as a unitary. It is safe precisely when that phase is guaranteed to cancel. The classic pattern is compute-then-uncompute: compute a value into an ancilla with a Margolus gate, do some Clifford work, then erase it with the inverse — the stray phase appears twice and squares to $+1$ . Keep the Margolus output as a lasting part of the register, though, and the extra phase corrupts the computation.

Why the specific pairing "Hadamard plus Toffoli" for quantum universality?

Each gate contributes what the other lacks. The Toffoli is a real permutation — it entangles and computes nonlinear Boolean functions but can never build a superposition. The Hadamard builds superpositions and lets the real-amplitude dynamics encode the missing structure. Shi (2003) and Aharonov (2003) proved this set is computationally universal: it simulates any quantum circuit to arbitrary accuracy even though every reachable state has real amplitudes (the imaginary parts ride an extra encoding qubit). It is one of the smallest and most surprising universal sets, dramatizing that quantum speedup needs no explicit complex numbers — only the interference that Hadamard's superpositions and Toffoli's entanglement together provide.