Exact T-counts of CCZ layers from an isotropy bound

arXiv:2610.01024 · quant-ph, cs.CC · Submitted 2026-10-01 · Read on arXiv

quant-ph, cs.CC

Submitted: 2026-10-01

Updated: 2026-10-04

Comments: 77 pages, 8 figures, 13 tables. v2: retitled; appendices reorganized (A-L merged into A-F); prior-art discussion of Campbell-Howard expanded; benchmark certificates added

Code: https://github.com/khoruzhii/bcf10

License: http://creativecommons.org/licenses/by/4.0/

The gist: The T-count is a dominant cost of fault-tolerant Clifford +T computation.

Terminology

Abstract

The T-count is a dominant cost of fault-tolerant Clifford +T computation. We prove that a layer of m disjoint CCZ gates, the diagonal core of a parallel Toffoli layer, needs exactly 6m+1 T gates in every Hadamard-free Clifford +T circuit with clean ancillas. Campbell and Howard gave the matching construction, and to our knowledge this is the first proof that it is optimal for general m. The proof rests on a novel isotropy bound. When a gate's phase polynomial has only cubic terms, the vectors recording which T gates touch each qubit span a self-orthogonal subspace over F 2, and this forces the T-count to be at least twice its dimension. This argument gives a lower bound, computable by Gaussian elimination, on the T-count of every diagonal gate in the third level of the Clifford hierarchy. It is never below the stabilizer nullity ν and reaches 2ν+1 on non-Clifford cubic gates. No bound that also holds for circuits with measurement and feedforward can do this, since such circuits implement CCZ (ν=3) with four T gates, while the floor gives seven. It also recovers Campbell and Howard's count 4m+3 for a fan-out of Toffolis. On the output of PyZX's TODD-based optimizer, relative to its Hadamard placement, it certifies 193 of 311 phase-polynomial blocks T-optimal, against 113 for nullity, including 37 of the 72 blocks too large for exhaustive search.

Sources

Related papers