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.
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.
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
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.
Lower bounds for depth-two threshold circuits are currently proved by Williams' algorithmic method, which needs nontrivial algorithms estimating acceptance probabilities. For circuits C(x)=f(∑i=1qTi(x)) with an arbitrary symmetric top f:{0,…,q}→{0,1} and linear threshold bottom gates Ti on h variables, a natural plan is to estimate a single modular character of the bottom-gate sum and recover f by linearity. We show that this primitive is already as hard as the general problem. Let R be the least power of two larger than q and ω=e2πi/R. In polynomial time we construct M=O(q2) unweighted linear threshold functions U1,…,UM on h+2log2R+1 variables such that Eω∑jUj=R−1Prx[C(x)=1]. Every character coefficient equals one; the compression comes from logarithmically many uniform selector variables, which combine character orthogonality with an exact cancellation of the rejected top values. Conversely, each residue probability of ∑jUj is itself a symmetric-top counting query, so the two primitives are polynomially interreducible when R and M are polynomially bounded. Consequently, an algorithm for unweighted single-character estimation of MODR∘LTF expectations would give the same algorithm for arbitrary SYM∘LTF counting, up to polynomial blow-up and a factor R<2(q+1) in the additive error. The result is a representation theorem. It gives no new algorithm or circuit lower bound, and makes no claim about characters with a fixed modulus. Archival copy of version 1 of this paper, published on rStation on 25 October 2026 (rStation computer_science paper 1, v1). paper.md is the manuscript exactly as published there; the PDF is typeset from it with the published title and abstract; supplement.zip is the supplement as published there. Files: paper.md — SHA-256 d389bd9a616e7181afae0db0df606e2f39bd35b070e741aa47b372d082315726 a-single-modular-character-is-complete-for-sym-ltf-counting.pdf — SHA-256 de1bf8e6fa9b34bdd4a1bdd19887a7f6a3911d186b1cff4ed4db5213de8ed004 supplement.zip — SHA-256 d98cfb3bd1dbfc93908bd6bdef686add5096131d211650950fc8faefb3f77528
This note is a stripped down version of a published paper on the Potts partition function, where we concentrate solely on the linear coding aspect of our approach. It is meant as a resource for people interested in coding theory but who do not know much of the mathematics involved and how quantum computation may provide a speed up in the computation of a very important quantity in coding theory. We provide a theorem on the quantum computation of the Weight Enumerator polynomial for a restricted family of cyclic codes. The complexity of obtaining an exact evaluation is O(k2s(logq)2), where s is a parameter which determines the class of cyclic codes in question, q is the characteristic of the finite field over which the code is defined, and k is the dimension of the code. We also provide an overview of cyclotomic cosets and discuss applications including how they can be used to speed up the computation of the weight enumerator polynomial (which is related to the Potts partition function). We also give an algorithm which returns the coset leaders and the size of each coset from the list {0,1,2,...,N−1}, whose time complexity is soft-O(N). This algorithm uses standard techniques but we include it as a resource for students. Note that cyclotomic cosets do not improve the asymptotic complexity of the computation of weight enumerators.
The fourth-order coefficient that controls the relative-entropy disturbance of a reduced quantum state under Gaussian coherent noise is identified here as one half of the quadratic form of the chi-squared divergence, evaluated not on a state but on the second-order mean drift of that state. The coefficient had appeared in an existing series of papers as a computed number attached to each noise family separately, with no statement of what kind of object it is. Naming it as a divergence norm on the drift is what makes the three results below possible, and each of them is a statement the series could not have reached while the coefficient remained a number. The first result is an identification, not a new computation. Five symbols are used for that coefficient across the series, carrying three different normalisations; they are shown to denote one quantity, and the conversion between them is recorded in a table. The normalisation that each symbol carries is stated explicitly, because the three differ by factors of the monitored dimension and of the total dimension, and a reader comparing two of the papers without that table would conclude that they disagree. The second result is a deformation. When the generating function of the expansion is replaced by the one-parameter family whose member at unit parameter is the logarithm, the coefficient becomes the quadratic form of the corresponding divergence of that family. The reason is local and explicit: the confluent value of the deformed kernel is the second derivative of the generator, so the kernel that the expansion produces is the Hessian of the generating function and nothing else. Closed forms follow for both noise families already studied, expressed in the power sums of the deformed theory. For unitarily invariant noise the coefficient is a single quadratic combination of three power sums. For Pauli-string noise on a stabilizer code only one power sum moves. The third result follows from the second. Because the only dependence on the deformation parameter sits in the diagonal of the kernel, whose sum over the spectrum is that single power sum, the counting law for stabilizer codes is invariant in form under the entire deformation, with the power sum read at the working parameter. The law is therefore not a feature of the relative entropy in particular; it is a feature of the whole family, and the choice of generating function changes one scalar in it and nothing of its structure. A structural correction to the series is also recorded, and it is the result with the clearest consequence for error correction. Protection at fourth order requires two independent conditions: the vanishing of every first-order amplitude, and the vanishing of the drift. The Knill-Laflamme condition supplies only the first. A code satisfying it may therefore carry a fourth-order error, and the residual is exactly the coefficient above together with the connected channel. That residual is thus the obstruction to full protection at this order, and a protection statement elsewhere in the series, which asserts the two conditions to be equivalent, is strictly weaker than it claims. A code and a noise family exhibiting the gap are given, and the residual is measured on them. The manuscript is self-contained. Three appendices derive, from the definitions, every ingredient that the results use: the two expansion coefficients and the quadratic form through the divided-difference Frechet derivative, the drift of each noise family from the completeness identities of the mode algebra, and the two vanishing arguments. No statement in the paper depends on work that is not yet published, and one appendix reproduces, from a convention-free law for the drift, the published coefficient of an earlier paper of the series, including the factor that the geometry of four tensor factors contributes to it. Every identity is certified numerically against the integral definitions of the deformed theory rather than against the closed forms used to derive it: the power sums are computed by quadrature in the substitution t = exp(u), with the interval split at the logarithm of every eigenvalue, at ninety working digits, and only then compared. Every statement of the appendices is checked separately on explicit matrices built from the definitions, with the perturbation applied by exact matrix exponentiation. Each check reports the discrepancy it attains rather than a verdict, so that the resolution of the test is visible; where a finite difference sets that resolution, the tolerance of the row is the resolution attained and not a wish. Three rational values reported as exactly verified in an earlier paper of the series are reproduced here from a single spectrum by a route not used when they were obtained. The archive deposited with this record carries the four self-contained checks, a README describing what each one measures, and the licence. Four further guards belong to the manuscript and are not in the archive, because none of them can run without files that are not part of it; they check the documents and the deposit rather than the mathematics, and all four are named in the README. The limitations of the work are stated in the manuscript as six paragraphs, among them the restriction of the drift to the diagonal case, the factor outside the weight hypothesis, and the extent of the prior-art search behind the disclaimer of novelty, which was two queries and the reading of two abstracts: the verdict recorded for the new statements is therefore "not found", which is weaker than "new". The use of an AI tool in the research and in the preparation of the manuscript is disclosed in the Acknowledgements, with the model and its version named, and described in the section on numerical certification.