T-Count and T-Depth

In a Clifford+$T$ circuit the Clifford gates are nearly free — transversal and classically trackable — while each $T$ gate must be supplied by costly magic-state distillation. So the right cost metrics are not total gate count or ordinary depth, but $T$-count and $T$-depth.

Definitions

• $T$-count: the total number of $T$ (and $T^\dagger$) gates in the circuit. It tracks the number of magic states consumed, hence the total distillation work and qubit-hours.
• $T$-depth: the number of layers in the circuit that contain at least one $T$ gate, where $T$ gates acting on disjoint qubits in the same layer count as a single layer. It tracks the sequential time spent on $T$ gates, which matters because distilled magic states may need to be produced in series.

A circuit can have high $T$-count but low $T$-depth if many $T$ gates run in parallel, or vice versa. Both metrics are reported in resource estimates for fault-tolerant algorithms.

Why Cliffords are not counted

Recall the two reasons from earlier lessons. First, Cliffords are typically transversal, so their physical cost is a constant factor over the logical operation. Second, by Gottesman–Knill, Clifford layers can be commuted and merged classically during compilation. The asymptotic and practical cost of a fault-tolerant algorithm is therefore dominated by its non-Clifford content — the $T$ gates.

The Toffoli as a $T$-count yardstick

The Toffoli (CCX) gate is the canonical example. It is not Clifford, so it requires $T$ gates. The standard fault-tolerant decomposition expresses one Toffoli with

using seven $T$/$T^\dagger$ gates interleaved with Hadamards and CNOTs. Since reversible classical logic (adders, comparators, modular arithmetic in Shor's algorithm) is built largely from Toffolis, the Toffoli $T$-count is a key building block for whole-algorithm estimates.

Estimating a circuit's $T$-count

To estimate the $T$-count of a larger circuit:

1. Replace each non-Clifford gate with its Clifford+$T$ decomposition (e.g. every Toffoli $\to 7$ T, every arbitrary rotation $\to \approx 3\log_2(1/\varepsilon)$ T from the previous lesson).
2. Sum the $T$ gates across all of them.
3. Optionally optimize: cancel adjacent $T$ and $T^\dagger$, merge rotations on the same qubit, and use $T$-count-reduction passes (e.g. the meet-in-the-middle synthesis of Amy et al.).

For example, a reversible adder built from $k$ Toffolis has a leading $T$-count of $7k$ (before optimization), which immediately tells you how many magic states the adder will consume.

Try it

Return the $T$-count of a single Toffoli gate in its standard Clifford+$T$ decomposition. The grader checks the returned number.

Sign in on the full site to ask questions and join the discussion.