arXiv preprint ·
Exact $T$-counts of CCZ layers from an isotropy bound
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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 $\mathbb{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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Quantum Physics
Beyond IP = PSPACE and QIP = PSPACE: Interactive Proofs in Arbitrary Physical Theories
Hamiltonian locality testing and certification do not achieve the Heisenberg limit
No Size-Preserving Amplification with Quantum Advice
Coloring 3-colorable graphs with $O(n^{4/23})$ colors via a Gaussian-cover recursion
The Plan Language of a Curriculum: A Formal Model and the Complexity of Degree Planning
Get the few papers worth your time in Quantum Physics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.