CS Paper Radar

Exact $T$-counts of CCZ layers from an isotropy bound

Arul Rhik Mazumder

cs.CC quant-ph ·submitted 2026-10-01 04:11 UTC · v3
theory

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.

Comment
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

Closest papers

Nearest neighbours by meaning across the whole index.

Shallow Clifford circuits on square lattices

cs.ET quant-ph ·2026-11-14 ·Dmitri Maslov
theory similarity 0.65
Abstract · Preliminary version. Comments are welcome

We study the depth of CZ circuits, Clifford state preparation, and Clifford unitary synthesis over the two-dimensional square lattice. A programmable circuit on a $2{\times}k$ ladder ($n{=}2k$) implements an arbitrary CZ computation in depth at most $\frac{3n}{2}{+}3$ up to reversal of both rails. This improves the best-known LNN (Linear Nearest-Neighbor)-compliant depth-$(2n{+}2)$ construction by about 25\%. For state preparation, we consider a Phase gate programmable -H-{CNOT+P}-LC- circuit and derive matching obstructions to attaining the CZ-span counting lower bound of $2\lceil\frac{n}{2}\rceil{-}1$ for depth by the entangling gates. For cycle connectivity $C_n$, we prove that the minimum depth is exactly $2\lceil\frac{n}{2}\rceil{-}1$ when $n$ is not a multiple of four and $2\lceil\frac{n}{2}\rceil$ when $n\,{=}\,4k$. We construct a hole-free minimum-perimeter square-lattice patch with a Hamiltonian cycle for every even size, giving optimal-depth programmable circuits to implement Clifford states for all $n\,{=}\,4k{+}2$. Exhaustive and heuristic searches address the remaining cases for $n$ up to 256, and selected values up to 1,024 qubits. The improvement against comparable state-of-the-art, an LNN-compliant depth-$(2n{+}2)$ solution, is about 50\%. Finally, combining state synthesis circuits developed in this work with a known four-diagonal-stage decomposition gives rise to a depth $4n{-}4$ for $n\,{=}\,4k{+}2$ and depth $4n$ for $n\,{=}\,4k$ implementation of arbitrary Clifford unitaries. This improves the most relevant state-of-the-art, an LNN-compliant depth $7n{-}4$ construction, by about 43\%.

0.17

Ancilla-free randomized Toffoli gates and the T-count of Boolean oracles

cs.CC quant-ph ·2026-10-28 ·Arul Rhik Mazumder
code/data similarity 0.62
Abstract · 27 pages, 4 figures, 1 table. Verification scripts: https://github.com/arulrhikm/randomized-oracle-checks

In fault-tolerant Clifford+T circuits, a Boolean oracle costs T gates and extra qubits, and on four or more qubits every exact Toffoli gate needs an extra qubit. Gosset, Kothari and Zhang showed that sampling a fresh random circuit for each call makes the T-count of the Toffoli gate independent of its size, but a direct implementation of their sampler uses about one extra qubit per bit of precision. We show that computing the sampled parities in place, on the gate's own controls, removes every extra qubit once the gate is large enough: each random circuit then uses about 8 T gates per bit of precision and borrows only the gate's own idle inputs. This is one T gate more per circuit than the best measurement-free variant that keeps one clean ancilla. The same holds for exclusive-ors of indicators of affine subspaces, such as equality tests and checks of linear equations. For randomized circuits that do not measure, this is within a factor of eight of optimal up to an additive constant, even with extra qubits, and when each random circuit computes a Boolean function exactly, closing the factor asymptotically is equivalent to determining the leading constant in the T-count of exact multi-controlled Toffoli gates. Finally, the oracle of the indicator of a random set of fixed density needs exponentially many T gates at constant error, while that of an affine subspace of the same density needs a constant number, and extra qubits reduce the exponential cost only quadratically.

0.35

Improved Transversal Non-Clifford Gates from Cup Products

cs.IT quant-ph ·2026-08-17 ·Louis Golowich, Itzhak Tamo, Guanyu Zhu
published similarity 0.61
Abstract

It is a major challenge in quantum fault-tolerance to obtain low-overhead protocols for performing non-Clifford gates. In this vein, we construct quantum codes with low-weight stabilizers that support transversal (i.e. low-depth) implementations of the non-Clifford $C^{r-1}Z$ gate, for every constant $r\geq 3$. In particular, we obtain length-$n$ quantum LDPC codes (with constant-weight stabilizers) of polynomial distance $d\geq n^{(1-ε)/r}$ supporting transversal $C^{r-1}Z$ gates on a close-to-linear number $k\geq n^{1-ε}$ of disjoint tuples of logical qubits, for arbitrarily small $ε>0$. Our construction is the first with constant-weight stabilizers that obtains $dk\gg n$, and as a consequence achieves arbitrarily small magic state overhead exponent $γ=\log(n/k)/\log(d)>0$. Comparable prior constructions instead required at least polylogarithmic stabilizer weight. We also show how to obtain linearly many $k=Ω(n)$ logical $C^{r-1}Z$ gates, though with stabilizer weight and physical circuit depth $n^ε$. We show that our transversal gates also support addressing (i.e. targeting) of specific logical qubits. To obtain our codes, we develop a general transformation based on cup products that maps classical codes satisfying a multiplication property to quantum codes with transversal $C^{r-1}Z$. We apply this transformation to a new family of classical Tanner codes that we construct from punctured tensor products of algebraic codes.

0.60

Good Stabilizer Codes from Shallow Clifford Circuits with Random Matchings

cs.CC quant-phcond-mat.str-elcs.IT ·2026-08-19 ·Emile Anand, Elia Gorokhovsky, Jennifer Hritz, Jingtong Sun
theory similarity 0.59
Abstract · 33 pages, 2 figures, 1 table

Encoding quantum information with low circuit overhead is a fundamental challenge in fault-tolerant quantum computation. Random circuits provide a natural mechanism for rapidly spreading logical information through simple gates applied in parallel. Brown and Fawzi showed that random Clifford circuits on two-qubit Clifford gates provide such encoders that achieve the quantum Gilbert-Varshamov rate-distance tradeoff with depth $O(\log^3 n)$. We show that the same asymptotic tradeoff is attained in optimal $O(\log n)$ depth under a gate distribution with a more restricted support. For every fixed $δ>0$ and sufficiently large $n$, if $\frac kn < 1 - H(\frac{d}{n}) - \frac{d}{n}\log_2 3 - δ$, we can construct random circuits of depth $O(\log n)$ which define, with high probability, an $[n,k]$ stabilizer code of distance at least $d+1$, which matches the $Ω(\log n)$ light-cone lower bound for linear distance encoders. Our ensemble employs a random matching circuit architecture consisting of $T$ independent permutation-invariant layers. In each layer, the qubits are paired up by a uniformly random perfect matching, and a random independent two-qubit Clifford gate is applied to each pair. The gate distribution need not be uniform over, or even have full support on, the two-qubit Clifford group; rather, we allow for very general distributions on Clifford gates satisfying three regularity conditions. In particular, the construction can be implemented using $n/2$ CNOT gates on randomly matched pairs in each layer, with parallel one-qubit Clifford twirls. These regularity conditions allow us to reduce the second-moment dynamics of our random circuits to a reversible Markov chain on binary support strings. We establish logarithmic hitting-time bounds for this Markov chain and comparisons of its stationary distribution to prove the coding properties of the circuits.

0.38

Improved Quantum Codes with Transversal T Gates

cs.IT quant-ph ·2026-08-25 ·Adam Wills
theoryhighly cited similarity 0.57
Abstract

In this work, we study quantum CSS codes with transversal $T$ gates. Here, $T$ gate transversality is meant in the strongest sense; the application of physical $T$ to every physical qubit yields logical $T$ on every logical qubit, without Clifford corrections. Despite the importance of the $T$ gate in fault-tolerant quantum computation, the parameters of asymptotic families of such codes have not been improved since the work of Hastings and Haah in 2017, and Haah in 2018. In this work, we significantly broaden the achievable parameters of quantum code families with transversal $T$ gates, both expanding the regime of achievable polynomial rate and distance, and constructing such codes with constant rate and growing distance; this is the first time the latter has been achieved, even when allowing Clifford corrections after the transversal $T$ gate. These are also the first codes achieving $γ\to 0$ for a code with a transversal $T$ gate, where $γ$ is the overhead exponent of magic state distillation. To do this, we develop a framework of divisible decreasing monomial codes, punctured at a downward-closed set on the Boolean hypercube to create logical qubits. We prove a closed-form expression for the distance of such a code punctured at such a set, which may be of independent interest. We first instantiate this with an explicit construction based on weighted Reed-Muller codes, puncturing at low Hamming-weight points, and then with a randomised construction, where a small random set of points is protected from the puncturing to save quantum code distance, achieving improved parameters.

0.28

Improved Quantum Query Bounds for Boolean Matrix Product Verification

cs.DS quant-ph ·2026-09-30 ·Amin Shiraz Gilani, François Le Gall, Xingyu Zhou
theory similarity 0.56
Abstract · 38 pages

We prove the first non-trivial upper bound for the quantum query complexity of Boolean Matrix Product Verification ($\mathsf{BMPV}$), answering a longstanding open question in quantum query complexity. For $n\times n$ matrices, our upper bound is $\widetilde O(n^{17/12})$, improving on the standard $O(n^{3/2})$ bound obtained using Grover search by Buhrman and Špalek [SODA 2006]. We complement this result by showing an $Ω(n^{5/4})$ lower bound, which improves over the previous best known lower bound of $\widetildeΩ(n^{19/18})$ by Childs, Kimmel, and Kothari [ESA 2012]. Our approach centers on a connection with Orthogonal Vectors ($\mathsf{OV}$), which asks whether an indexed list of $n$ Boolean vectors of dimension $n$ contains two vectors with disjoint supports. In particular, we prove equivalences between $\mathsf{OV}$ and $\mathsf{BMPV}$ and establish the above bounds for $\mathsf{OV}$. We also prove a tight $\widetilde Θ(n^{3/2})$ bound for a variant of $\mathsf{BMPV}$ that asks whether the product contains a given row vector. Together, these results imply a polynomial separation between the quantum query complexities of deciding whether a graph has radius at most two and whether it has diameter at most two.

0.25

Short Point Lists for CNFs and Stronger Constant-Depth Circuit Hardness

cs.CC math.CO ·2026-10-19 ·Xin Li, Yan Zhong
publishedtheory similarity 0.55
Abstract

We give a short-description decomposition of bounded-width CNFs. For every fixed $\varepsilon>0$, every width-$b$ CNF on $m$ variables is an exact disjoint union of at most $2^{\varepsilon m}$ width-$b$ CNFs, each determined by $2^{O_\varepsilon(b)}\log(m+1)$ satisfying assignments. For every fixed $d\ge3$, we prove a worst-case size lower bound of $2^{Ω_d((n\log n)^{1/(d-1)})}$ against depth-at-most-$d$ unbounded-fan-in AND/OR circuits with input negations for three polynomial-time Boolean families: inverse trace over binary fields, the Goldreich--Tal trilinear function, and OpenAI's polynomial evaluator with its original parameters. All parameter bits count as inputs. For inverse trace, every such circuit of size at most $S$, where $n\le S\le2^{c_dn^{1/(d-1)}}$, has uniform sign correlation at most $2^{-η_dn\log\log S/(\log S)^{d-1}}$. Here $c_d,η_d>0$ depend only on $d$. This improves on the classical parity correlation bound. The lower bounds combine the decomposition with restriction arguments; the correlation bound additionally uses common partial decision trees. We also construct exact nonuniform AND/OR circuits for inverse trace of size $2^{O(n^{2/3})}$ at depth eight and $2^{O(\sqrt n\log n)}$ at depth nine. For every fixed integer $h\ge2$, the construction gives depth-$(4h+1)$ circuits of size $2^{O_h(n^{1/h}\log n)}$. The upper bounds implement finite-field evaluation and interpolation using circuits that enumerate intermediate states.

0.52

A Memory-Magic Exchange Law in Streaming Clifford+T Compilation

cs.IT quant-phmath.NT ·2026-09-29 ·Jinze Yang, Yangyang Li, Xiu-Hao Deng
code/data similarity 0.55
Abstract · 39 pages, 2 figures. v2: unconditional rate improved from 17/7 to every alpha < 5/2 (Theorem 8, Appendices G-H, exact SMT check). Code, data…

A phase that reaches a fault-tolerant processor in additive pieces can be remembered until the last piece arrives, or executed on arrival: the first option costs classical memory carried across rounds, the second costs magic states committed before the phase is known. We determine the exchange rate $α$, committed $T$ gates per bit of memory forgone, for ancilla-free coordinatewise Clifford+$T$ compilation. The Ramanujan bound gives $α\ge2$ with explicit constants, the square-root barrier of the spectral method. An elementary determinant method, using that quaternion numerators lie on spheres in both real embeddings of $\mathbb{Q}(\sqrt2)$, counts words near any rotation coset below that barrier. With a height dichotomy for the sphere sections it produces and a fibration over rational projections, it gives every $α<5/2$ unconditionally and uniformly over frames, by an exact SMT check of its continuum case analysis; $5/2$ is where this method stops. At Clifford-framed cosets the volume law holds up to subexponential factors: all but a vanishing fraction of $z$-rotations need $T$-count $(3-o(1))\log_2(1/\varepsilon)$, and processes whose committed pieces are near Clifford-framed $z$-rotations, including per-rotation pipelines, have $α\ge3-o(1)$, which a fractional-passthrough family attains under the Ross-Selinger typical-cost hypothesis. Under an equidistribution conjecture supported by exhaustive enumeration to $T$-count 22, $α=3$ in general and memory should be shed in whole rotations. The bounds hold even when the phases cancel to the identity; side information enters through a conditional entropy; probabilistic mixing halves the costs but not the rate. With clean ancillas and a phase-gradient catalyst, table lookups batched over coordinates drive the rate to $O(1/\log\log(1/\varepsilon))$, so the constant-rate law is specific to coordinatewise synthesis.

0.46