Exact T-counts of CCZ layers from an isotropy bound
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
- A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
- An algorithm for the T-count
- Optimising quantum circuits is generally hard
- T-count and T-depth of any multi-qubit unitary
- Application of a resource theory for magic states to fault-tolerant quantum computing
- Quantifying magic for multi-qubit operations
- Simulation of quantum circuits by low-rank stabilizer decompositions
- Stabilizer R'enyi entropy
- Amortized Stabilizer R'enyi Entropy of Quantum Dynamics
- A unified framework for magic state distillation and multi-qubit gate-synthesis with reduced resource cost
- Characterization of permutation gates in the third level of the Clifford hierarchy
- Quantum Circuit Optimization with AlphaTensor
- An Efficient Quantum Compiler that reduces $T$ count
- PyZX: Large Scale Automated Diagrammatic Reasoning
- Reducing T-count with the ZX-calculus
- Halving the cost of quantum addition
- Semi-Clifford operations, structure of $\mathcal{C}_k$ hierarchy, and gate complexity for fault-tolerant quantum computation
- C3, Semi-Clifford and Generalized Semi-Clifford Operations
- A new quantum ripple-carry addition circuit
- Halving the cost of QROM
Related papers
- Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
- Encrypted clones can leak: Classification of informative subsets in Quantum Encrypted Cloning
- Polynomial-time classical and quantum simulation of quantum impurity models
- A quasiparticle-protected superconducting qubit
- Theory of quantum-enhanced interferometry with general Markovian light sources
- A convergent hierarchy of spectral gap certificates for qubit Hamiltonians