Counting T-Gates and Qubits

In the near-term noisy regime you count every gate equally, because every gate adds error. In the fault-tolerant regime the cost model changes shape entirely: Clifford gates become almost free, and the bottleneck becomes the number of $T$ gates. Counting $T$ gates and qubits is the single most important resource estimate for any algorithm aimed at an error-corrected machine.

Why $T$ gates dominate

The Clifford group — generated by $H$ , $S$ , and CNOT — is special. By the Gottesman–Knill theorem, a circuit built only from Clifford gates and computational-basis measurement can be simulated efficiently on a classical computer, so Cliffords alone are not universal and carry no quantum advantage. Adding a single non-Clifford gate, conventionally the $T$ gate

T = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi/4} \end{pmatrix},

makes the set Clifford+T, which is universal: any unitary can be approximated to arbitrary precision.

The catch is cost. In the leading error-correction scheme, Clifford gates are implemented transversally and are cheap, but a $T$ gate requires consuming a magic state that must be produced by magic-state distillation — a process that dominates the qubit count and runtime of a fault-tolerant computation. Hence the rule of thumb: the $T$ -count is the cost, and minimising it is a whole research area (the citation by Amy et al. gives depth-optimal synthesis methods).

The $T$ -count of a Toffoli

The single most reused building block is the Toffoli gate. Its standard Clifford+T decomposition — the one in Nielsen & Chuang — uses

\text{T-count}(\text{Toffoli}) = 7,

together with several $H$ and CNOT gates that are free in the cost model. (Cleverer constructions trade $T$ -count for ancillas or measurement, but 7 is the canonical textbook figure.) Because so many oracles, adders, and comparators are built from Toffolis, you can often estimate a circuit's $T$ -count just by counting its Toffolis and multiplying by 7, then adding any standalone $T$ or $T^\dagger$ gates.

Counting qubits

The width estimate has two parts. Logical data qubits carry the algorithm's state — $n$ qubits to hold an $n$ -bit register. Ancilla qubits are scratch space: Toffoli decompositions, multi-controlled gates, and reversible arithmetic all borrow ancillas that must be allocated, used, and ideally uncomputed back to $|0\rangle$ so they can be reused. A tight qubit estimate tracks the peak number of simultaneously-live ancillas, not the total ever allocated, because uncomputation lets the same physical qubit serve many roles in sequence.

Putting it together

A concrete count for a sub-circuit is therefore three numbers — width (peak qubits), $T$ -count, and Clifford count — reported against a stated gate set. The $T$ -count drives fault-tolerant cost, the width drives how big a chip you need, and the Clifford count matters mainly for near-term depth. Keeping the three separate, rather than collapsing to one "gate count", is what makes an estimate actionable.

Try it

Compute the total $T$ -count of a small reversible circuit built from 12 Toffoli gates (7 $T$ each) plus 4 standalone $T$ gates. Return the integer total. The grader checks the value and that it is a whole number.

Run your code to see the quantum state.