Representations of a Clifford+T phase polynomial, modulo Clifford operations, form a coset of the punctured Reed-Muller code RM(h-4, h). The optimization literature decodes this coset for weight: the number of odd-coefficient parities is the T-count, and its exact minimization is NP-hard. We decode the same coset for rank: the F2-dimension d of the span of the odd-parity support, minimized over the coset, which we call the interference dimension, because exact path-sum simulation costs poly x 2^d rather than 2^(T-count). We prove that the subspaces supporting some coset element form an intersection-closed family, so a unique minimal core subspace V0 exists with d = dim V0; that the Clifford-equivalence class is computed by a syndrome map into the shortened code RM(3, h); and that d equals the F2-rank of an explicit h x O(h^2) matrix read off the circuit: polynomial time, in sharp contrast with the NP-hardness of the weight objective. For the standard GF(2^k) multiplier benchmarks the invariant is a convolution tensor and d = 4k-1 exactly; combined with the hierarchy log2(t+1) <= d <= t, where t is the optimal T-count, this yields a linear lower bound on multiplier T-count in the coset model, which meets Karatsuba-type upper bounds at t = Theta(k). A counting argument gives families on which the rank price beats the optimal weight price superpolynomially. Every theorem is machine-verified (exhaustive small-case checks; 142/142 agreement with brute-force coset scans), and the method is benchmarked against the feynman suite and the quizx stabilizer decomposer, with both engines agreeing on every exact amplitude. Optimal T-count is NP-hard; the interference dimension, which is what exact simulation actually pays for, is a matrix rank. Code and machine verification of every proof step: https://github.com/0verflowme/rankprice
Representations of a Clifford+T phase polynomial, modulo Clifford operations, form a coset of the punctured Reed-Muller code RM(h-4, h). The optimization literature decodes this coset for weight: the number of odd-coefficient parities is the T-count, and its exact minimization is NP-hard. We decode the same coset for rank: the F2-dimension d of the span of the odd-parity support, minimized over the coset, which we call the interference dimension, because exact path-sum simulation costs poly x 2^d rather than 2^(T-count). We prove that the subspaces supporting some coset element form an intersection-closed family, so a unique minimal core subspace V0 exists with d = dim V0; that the Clifford-equivalence class is computed by a syndrome map into the shortened code RM(3, h); and that d equals the F2-rank of an explicit h x O(h^2) matrix read off the circuit: polynomial time, in sharp contrast with the NP-hardness of the weight objective. For the standard GF(2^k) multiplier benchmarks the invariant is a convolution tensor and d = 4k-1 exactly; combined with the hierarchy log2(t+1) <= d <= t, where t is the optimal T-count, this yields a linear lower bound on multiplier T-count in the coset model, which meets Karatsuba-type upper bounds at t = Theta(k). A counting argument gives families on which the rank price beats the optimal weight price superpolynomially. Every theorem is machine-verified (exhaustive small-case checks; 142/142 agreement with brute-force coset scans), and the method is benchmarked against the feynman suite and the quizx stabilizer decomposer, with both engines agreeing on every exact amplitude. Optimal T-count is NP-hard; the interference dimension, which is what exact simulation actually pays for, is a matrix rank. Code and machine verification of every proof step: https://github.com/0verflowme/rankprice
To predict what a quantum computer will output you have to work out an astronomical sum, and almost every term in it cancels to nothing. This work counts how many actually survive, and shows that number is out of reach of the standard tools: not the Tutte polynomial, not the usual weight counts, not the usual recursions. A binary linear code is a set of bit strings closed under bitwise addition — the object behind error-correcting codes. This paper studies a counting quantity attached to such a code, its survivor count. Where it comes from. Take a quantum circuit built from Clifford gates and T gates and ask for the expected value of its output. That expectation is a signed sum of exponentially many terms — quadratic Gauss sums over the two-element field — indexed by the codewords of a binary linear code. What that sum comes to is a well-studied quantity. This paper asks a different question about the same sum: not what it adds up to, but how many of its terms are really there. The number that survive is the survivor count of the code. What was already known, and what is taken up here. Whether one individual term survives is classical: a quadratic Gauss sum vanishes unless its form is trivial on the radical of its polar form, and is otherwise a power of two carrying the Arf sign. The weight attached to a single support is published as well, as the local isotropic-nullity weight of Bouchet's isotropic systems and of the restricted Tutte–Martin polynomial; the paper treats it as background rather than as a result of its own. What the paper takes up is the whole family at once. The census runs over all 2k codewords of a code, and the questions asked are what determines that total, what exact evaluation costs, which parameters and moduli buy an algorithm, and how far into the planar case each side reaches. What the paper proves. An exact criterion, and a closed form. The class sum at a support vanishes unless a certain half-weight form vanishes on a radical; where it does not vanish, the survivors are counted exactly by a power of two read off the dimensions of the code. One parity obstruction can remove them all. Consequently the survivor count depends only on the code's binary matroid. Separations. It is determined by none of the following: the Tutte polynomial; the cycle and cut weight enumerators taken together on planar graphs; the local marginals. It is not invariant under duality, and it obeys no constant-coefficient deletion–contraction recursion. The standard machinery that classifies graph and matroid invariants therefore does not reach it, and every line drawn below between easy and hard is drawn from the definition instead. A complexity map. Exact evaluation is #P-complete under deterministic polynomial-time Turing reductions, both on explicit generators and on graph cycle codes, and stays hard on four restricted graph families, on linear complementary dual codes, and at each fixed hull dimension. It is polynomial at bounded pathwidth, at bounded treewidth by a proved but unimplemented join step, on several code classes, and modulo 2, 3 and 6. Planar graphs. An exact algorithm running in time 2O(√n log n), conditional on three imported constructors, together with a #P-hardness statement conditional on one named planar Tutte evaluation being #P-hard. A bridge to quantum circuits, in both directions. Every Clifford+T circuit compiles to a single code and a single integer h whose output expectation is exactly (A + B√2)/2h+1, an identity holding exactly in the ring Z[√2], where (A,B) is that code's mod-8 weight census. Separately, a reverse construction makes the sign of such a bias hard for PromiseBQP at an exponentially small threshold, while at inverse-polynomial thresholds the same sign is decided classically with bounded error. Scope, and what is not claimed. Every statement carries exactly the status its proof supports and never a stronger one. Results resting on an unproved hypothesis carry that hypothesis at the head of their own statement, and no hypothesis is discharged anywhere in the paper. Nothing here claims, implies or denies any equality or separation of complexity classes. Where a comparison with the literature was not made, the paper says so at the statement it touches; nothing here asserts priority. Supplementary material. The consolidated record, and the proof files named in the paper's appendix, are deposited separately at doi:10.5281/zenodo.22804078. Abstract, as printed in the paper A Clifford+T circuit's output expectation is a signed sum of quadratic Gauss sums over the codewords of a binary linear code; counted here is how many survive. For C in F_2^m, let K_F be the dual subcode supported in a codeword F and R_F its radical: the survivor count S(C) counts, over all F, the cosets of K_F in the even-weight subspace on F with nonzero Gauss sum. An exact criterion is proved: the class sum at F vanishes unless the half-weight form twisted by the class representative s vanishes on R_F, and survivors at nonzero F number 2^(|F|-1-dim K_F-dim R_F+[F in the dual]), or none under a parity obstruction. So S is a binary-matroid invariant determined by none of the Tutte polynomial, the cycle and cut weight enumerators together on planar graphs, or the local marginals, not duality-invariant, and obeying no constant-coefficient deletion-contraction recursion. Exact evaluation is #P-complete under polynomial-time Turing reductions, and stays hard on four restricted graph families, on linear complementary dual codes and at each fixed hull dimension; it is polynomial at bounded pathwidth, at bounded treewidth by a proved but unimplemented join step, on several code classes and modulo 2, 3, 6. For planar graphs an exact 2^(O(sqrt(n) log n)) algorithm is given, conditional on three imported constructors, with hardness conditional on one named planar Tutte evaluation being #P-hard. Every such circuit compiles to one code and an integer h with output expectation exactly (A+B sqrt 2)/2^(h+1) in Z[sqrt 2], for (A,B) that code's mod-8 weight census; a reverse construction makes that sign PromiseBQP-hard at an exponentially small threshold, while inverse-polynomial ones are decided classically with bounded error. No complexity-class equality or separation is claimed or denied.
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+1T 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.
In this paper, we study the close relationship between Reed-Muller codes and single-qubit phase gates from the perspective of T-count optimization. We prove that minimizing the number of T gates in an n-qubit quantum circuit over CNOT and T, together with the Clifford group powers of T, corresponds to finding a minimum distance decoding of a length 2n- 1 binary vector in the order n - 4 punctured Reed-Muller code. Moreover, we show that the problems are polynomially equivalent in the length of the code. As a consequence, we derive an algorithm for the optimization of T-count in quantum circuits based on Reed-Muller decoders, along with a new upper bound of O(n2) on the number of T gates required to implement an n-qubit unitary over CNOT and T gates. We further generalize this result to show that minimizing small angle rotations corresponds to decoding lower order binary Reed-Muller codes. In particular, we show that minimizing the number of RZ(2π/m) gates for any integer m is equivalent to minimum distance decoding in RM(n - k - 1, n)*, where k is the highest power of 2 dividing m.
The SU(N) matrix-model potential V=−4g2∑I,JTr[XI,XJ]2, the interaction of the BFSS/BMN family, whose thermal large-N states are dual to black holes, is diagonal in the coordinate basis and is compiled in the literature as a phase polynomial with O(d2N4Q4) rotations per Trotter step. That cost is close to optimal for its gate class: we show that for a generic Trotter step the Walsh support mmin lower-bounds both the rotation count and the two-qubit count of every circuit over {CNOT,CZ,CPhase,RZZ,SWAP,X,Rz}, ancillas included, and we build a parity network attaining 1.01--1.10mmin. Improvement therefore requires a gate outside that class, and the exact factorisation of V into a sum of squared commutator entries supplies one in each era. For NISQ, Hadamard: each squared entry is added into a Fourier register and squared there, Θ(d2N3Q3) two-qubit gates. For fault tolerance, T: reversible arithmetic with one phase-gradient injection per squared entry, Θ(d2N3Q2) T gates and no arbitrary-angle rotation. Both are built and verified. With a native RZZ the NISQ circuit uses fewer two-qubit gates than every parity network from Q=6 at SU(2) and Q=2 at SU(5); the oracle beats a precision-matched Hamming-weight-phasing incumbent at every point built except the smallest, by up to 11.9× in T count and, at equal width, 25.5× in surface-code spacetime. An ablation with the same arithmetic but no factorisation costs up to 21× more and loses to that incumbent at 15 of 17 points, so the factorisation, not the arithmetic, produces the win. Both constructions survive the supersymmetric deformation to mini-BMN with fermions, and complete Trotter evolutions on a statevector simulator reproduce the exact product formula to 2×10−12.
In fault-tolerant quantum computing systems, realising (approximately) universal quantum computation is usually described in terms of realising Clifford+T operations, which is to say a circuit of CNOT, Hadamard, and π/2-phase rotations, together with T operations (π/4-phase rotations). For many error correcting codes, fault-tolerant realisations of Clifford operations are significantly less resource-intensive than those of T gates, which motivates finding ways to realise the same transformation involving T-count (the number of T gates involved) which is as low as possible. Investigations into this problem [arXiv:1206.0758, 1303.2042, 1308.4134, 1601.07363, 1606.01904, 1701.00140] has led to observations that this problem is closely related to NP-hard tensor decomposition problems [arXiv:1712.01557] and is tantamount to the difficult problem of decoding exponentially long Reed-Muller codes [arXiv:1601.07363]. This problem then presents itself as one for which must be content in practise with approximate optimisation, in which one develops an array of tactics to be deployed through some pragmatic strategy. In this vein, we describe techniques to reduce the T-count, based on the effective application of spider nest identities: easily recognised products of parity-phase operations which are equivalent to the identity operation. We demonstrate the effectiveness of such techniques by obtaining improvements in the T-counts of a number of circuits, in run-times which are typically less than the time required to make a fresh cup of coffee.
Strongly simulating a quantum circuit, that is, computing an output amplitude, can be done by summing the circuit's Feynman paths: a weighted count over assignments to Boolean path variables. The circuit's gates induce correlations among these variables, forming a graph whose structure controls several exact simulation routes. This sum-of-powers (SOP) viewpoint underlies recent simulators built on binary decision diagrams and weighted model counting.
For a quadratic SOP with n variables, even modulus r, and a rank-decomposition of its variable graph of width k, our dynamic program (DP) computes an amplitude using only O(4kpoly(n)) arithmetic operations. For Clifford+T circuits, the amplitude is given by an SOP with modulus 8.
Rank-width never exceeds linear rank-width, which governs some decision-diagram approaches, and is at most one greater than the Markov--Shi contraction complexity of the circuit tensor network. Moreover, there are non-Clifford families of bounded rank-width where both competing parameters diverge. We also present a stabilizer-rank optimization, exploiting that the DP tables are stabilizer-type Gauss sums. Each subtree runs at the width price of its cut-ranks or at a magic price that discharges the non-Clifford phases below it. The resulting best total cost never exceeds O(4kpoly(n)), yet is polynomial on mixed families where the pure rank-width and pure T-count guarantees are both exponential. Clifford amplitudes take polynomial time on any graph, the exact-amplitude consequence of Gottesman--Knill.
A prototype evaluation on standard circuit benchmarks finds treewidth bucket elimination the strongest baseline, with the new rank-width DP complementary: it wins on structured families where treewidth blows up.