arXiv:2610.01024
Exact -counts of CCZ layers from an isotropy bound
Arul Rhik Mazumder
Abstract
The $T$-count is a dominant cost of fault-tolerant Clifford$+T$ computation. We prove that every Hadamard-free Clifford$+T$ circuit with clean ancillas for a layer of $m$ disjoint CCZ gates, the diagonal core of a parallel Toffoli layer, uses at least $6m+1$ $T$ gates. Campbell and Howard gave a circuit with $6m+1$, and to our knowledge this is the first proof that it is optimal for general $m$. The proof combines Campbell and Howard's self-orthogonality of the columns of the parity matrix with a rank (flattening) bound, sharpened by one. More generally, the argument gives a lower bound on the $T$-count of every diagonal gate in the third level of the Clifford hierarchy, the isotropy floor, computable by Gaussian elimination. It is never below the stabilizer nullity $ν$ and reaches $2ν+1$ on non-Clifford gates whose phase is purely cubic. No bound that also holds for circuits with measurement and feedforward can do this, since such circuits implement CCZ ($ν=3$) with four $T$ gates and the layer with $4m$, where the floor gives seven and $6m+1$. The floor 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 once repeated parities are merged (at the best of five optimizer seeds), against $113$ for nullity, including $37$ of the $72$ blocks too large for exhaustive search.
AI Summary
The paper studies lower bounds on the exact $T$-count of diagonal third-level Clifford-hierarchy gates in the Hadamard-free Clifford+$T$ model, including clean ancillas. Its main result is that $m$ disjoint CCZ gates require exactly $6m+1$ $T$ gates, matching the existing Campbell–Howard construction for every $m$. The proof records the odd phase-polynomial parities as rows of a binary matrix $Y$. For gates with vanishing first- and second-order moments (“pure-cubic” gates), its columns span a self-orthogonal space, giving $t\ge2\operatorname{rank}Y$. A tensor-flattening argument bounds this rank using the radical of the cubic moment form; an all-ones-vector argument supplies an additional unit. More generally, the resulting “isotropy floor” is $\delta(U)\ge2(n-d^*)-r$, where $d^*$ is the full moment tensor’s radical dimension and $r$ is the quadratic moment matrix’s rank. The paper identifies stabilizer nullity as $\nu=n-d^*$, so the floor always dominates nullity and becomes $2\nu+1$ for non-Clifford pure-cubic gates. These quantities are computable by Gaussian elimination. The bound is also exact for specified forest-overlap CCZ layers and recovers the fan-out count $4m+3$. On PyZX TODD-optimized outputs, it certifies $193/311$ phase blocks optimal, versus $113$ using nullity. These certificates hold only for the chosen block partition and Hadamard placement. The floor need not be tight, does not generally cover internal Hadamards, and does not apply to adaptive measurement-based implementations, which realize the disjoint layer with $4m$ $T$ gates.
Generative artificial intelligence tools (Claude Opus 4.5, Claude Opus 5.5 and Claude Fable) assisted with the secondary results, including those of the supplementary notes, with the verification code and the benchmark experiments, and with drafting the text.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 35 pages, 5 figures, 5 tables; supplementary notes (35 pages) as an ancillary file. v3: condensed to the core results, with the remaining material moved to the supplementary notes; field-multiplication slice-rank bounds deferred to a separate paper