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.
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.
Lower bounds of the form 2^Ω(t) on the strong classical simulation of Clifford+T circuits with t T gates, and exponential lower bounds on efficiently computable stabilizer decompositions of the magic state |T⟩^⊗t, have been derived from the Exponential Time Hypothesis (ETH). Two manuscripts of October 2026 claim deterministic subexponential algorithms for #k-SAT, which would refute ETH. Under one of these claims, Tulsyan showed that the witness circuits of the ETH-based bounds, which use O(t) Clifford gates, are simulated exactly in time 2^O(t/√log t), and recorded 2^Ω(t) hardness with unboundedly many Clifford gates as open. We give an unconditional reduction showing that such hardness follows from the exponential hardness of syndrome decoding of binary linear codes, a standard assumption of code-based cryptography that does not depend on ETH. Syndrome decoding at length N reduces, with N+1 adaptive queries, to deciding whether ⟨0|U|0⟩ ≠ 1 for Clifford+T circuits U with 8N+O(log N) T gates and O(N²) gates. The Clifford gates prepare a coset of the code in superposition, and the T gates pay only for a Hamming-weight test built from relative-phase Toffoli gates. Consequently, a strong simulator running in time 2^(αt)·poly(g) on circuits with g gates yields a decoder running in time 2^(8αN+o(N)). If decoding requires circuits of size 2^(δN) at every length N, then χ(|T⟩^⊗t) ≥ 2^((δ/16)t − O(log t)) for all large t. Together with Tulsyan's conditional bound, this indicates that the density of the Clifford part, not the T-count alone, governs the fine-grained complexity of simulating Clifford+T circuits.
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.
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.
Maximum-likelihood decoding provides an optimal decoding strategy for quantum error correction under stochastic Pauli noise. However, computing logical-class probabilities is challenging, and the leading exact tensor-network contraction requires time exponential in treewidth. In this work, we introduce a new decoding algorithm based on rank-decomposition dynamic programming (Rank DP). We express decoding partition functions with independent local fault factors as quadratic sums of powers and apply Rank DP. The resulting exact evaluator has arithmetic complexity polynomial in the input size and exponential in the Tanner graph's rank-width with respect to the fault partition, including decomposition construction. After Gaussian elimination, it gives polynomial-time decoding for punctured quantum Reed-Muller codes and a Steane-concatenated family with growing distance under independent single-qubit Pauli noise. Standard contraction of the corresponding tensor networks requires superpolynomial time. A nonnegative realization gives relative floating-point error bounds under explicit arithmetic assumptions. Numerical experiments demonstrate runtime advantages over the tested tensor-network implementations on selected code-capacity and circuit-level instances, with full likelihood evaluation for Reed-Muller codes up to 1,023 qubits. We further use these likelihoods to learn circuit noise parameters from syndromes, evaluate rare postselection probabilities, and quantify decoder optimality gaps. Our work opens new avenues for exploiting algebraic structure in quantum decoding and noise characterization.