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.
We consider the problem of classical strong (amplitude-wise) simulation of n-qubit quantum circuits, and identify a subclass of simulators we call monotone. This subclass encompasses almost all prominent simulation techniques. We prove an unconditional (i.e. without relying on any complexity-theoretic assumptions) and explicit (n - 2)(2n-3- 1) lower bound on the running time of simulators within this subclass. Assuming the Strong Exponential Time Hypothesis (SETH), we further remark that a universal simulator computing any amplitude to precision 2-n/2 must take at least 2n-o(n)time. We then compare strong simulators to existing SAT solvers, and identify the time-complexity below which a strong simulator would improve on state-of-the-art general SAT solving. Finally, we investigate Clifford+T quantum circuits with t T-gates. Using the sparsification lemma, we identify a time complexity lower bound of 22.2451×10-8tbelow which a strong simulator would improve on state-of-the-art 3-SAT solving. This also yields a conditional exponential lower bound on the growth of the stabilizer rank of magic states.
In this work we improve the runtime of recent classical algorithms for strong simulation of quantum circuits composed of Clifford and T gates. The improvement is obtained by establishing a new upper bound on the stabilizer rank of m copies of the magic state | T ⟩ = 2 − 1 ( | 0 ⟩ + e i π / 4 | 1 ⟩ ) in the limit of large m . In particular, we show that | T ⟩ ⊗ m can be exactly expressed as a superposition of at most O ( 2 α m ) stabilizer states, where α ≤ 0.3963 , improving on the best previously known bound α ≤ 0.463 . This furnishes, via known techniques, a classical algorithm which approximates output probabilities of an n -qubit Clifford + T circuit U with m uses of the T gate to within a given inverse polynomial relative error using a runtime p o l y ( n , m ) 2 α m . We also provide improved upper bounds on the stabilizer rank of symmetric product states | ψ ⟩ ⊗ m more generally; as a consequence we obtain a strong simulation algorithm for circuits consisting of Clifford gates and m instances of any (fixed) single-qubit Z -rotation gate with runtime poly ( n , m ) 2 m / 2 . We suggest a method to further improve the upper bounds by constructing linear codes with certain properties.
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
Identifying the boundary between classical and quantum computation is a central challenge in quantum information. In multi-qubit systems, entanglement and magic are the key resources underlying genuinely quantum behaviour. While entanglement is well understood, magic - essential for universal quantum computation - remains relatively poorly characterised. Here we show that determining membership in the stabilizer polytope, which defines the free states of magic-state resource theory, requires super-exponential time $\class{exp} ( n^2)$ in the number of qubits
n, even approximately. We reduce the problem to solving a
3-\class{SAT} instance on
n2 variables and, by invoking the exponential time hypothesis, the result follows. As a consequence, both quantifying and certifying magic are fundamentally intractable: any magic monotone for general states must be super-exponentially hard to compute, and deciding whether an operator is a valid magic witness is equally difficult. As a corollary, we establish the robustness of magic as computationally optimal among monotones. This barrier extends even to classically simulable regimes: deciding whether a state lies in the convex hull of states generated by a logarithmic number of non-Clifford gates is also super-exponentially hard. Together, these results reveal intrinsic computational limits on assessing classical simulability, distilling pathological magic states, and ultimately probing and exploiting magic as a quantum resource.
The approximate stabilizer rank of a quantum state is the minimum number of terms in any approximate decomposition of that state into stabilizer states. Bravyi and Gosset showed that the approximate stabilizer rank of a so-called “magic” state like |T⟩⊗ n, up to polynomial factors, is an upper bound on the number of classical operations required to simulate an arbitrary quantum circuit with Clifford gates and n number of T gates. As a result, an exponential lower bound on this quantity seems inevitable. Despite this intuition, several attempts using various techniques could not lead to a better than a linear lower bound on the “exact” rank of |T⟩⊗ n, meaning the minimal size of a decomposition that exactly produces the state. For the “approximate” rank, which is more realistically related to the cost of simulating quantum circuits, no lower bound better than Ω(√n) has been known. In this paper, we improve the lower bound on the approximate rank to Ω(n2) for a wide range of the approximation parameters. An immediate corollary of our result is the existence of polynomial time computable functions which require a super-linear number of terms in any decomposition into exponentials of quadratic forms over F2, resolving a question by Williams. Our approach is based on a strong lower bound on the approximate rank of a quantum state sampled from the Haar measure, a step-by-step analysis of the approximate rank of a magic-state teleportation protocol to sample from the Haar measure, and a result about trading Clifford operations with T gates.
One of the state of the art techniques for classically simulating quantum circuits relies on approximating the output state of the circuit by a superposition of stabilizer states. \nIf the number of non-Clifford gates in the circuit is small, such simulations can be very effective. \nThis thesis provides various improvements in this framework. First, we describe an improved method of computing approximate stabilizer decompositions, which reduces the time cost of computing a single term in the decomposition from
O(elln2) to
O(mn2), where
ell is the total number of gates in the circuit, and
m is the number of non-Clifford gates. \nSince this subroutine has to be repeated exponentially many times, this improvement can be significant in practice whenever
ellggm. \nOur method uses a certain re-writing of the circuit, which in some cases allows for a significant amelioration of the exponential scaling of the required classical resources. \n \nFurthermore, we describe a method of constructing exact, low-rank stabilizer decompositions of
ketpsiotimesm, where
ketpsi is either a magic state or an equatorial state. \nFor any single qubit magic state
ketpsi, we find stabilizer decompositions of
ketpsiotimesm with
2mlog2(3)/4 terms. This improves on the best known bound of
2mlog2(7)/6. \nSimilarly, for any single qubit equatorial state
ketpsi, we give a stabilizer decomposition of
ketpsiotimesm with
2m/2 terms. \nTo our knowledge no such decompositions were previously known. \nThese results translate to milder exponential scaling of the classical resources required for estimating probabilities of quantum circuits up to a polynomially small multiplicative error, as well as allowing more types of circuits to be simulated in this way. \n \nWe also consider certain obstructions to classical simulations. \nIt has been argued in various contexts that contextuality and non-locality hamper classical simulations of quantum circuits. \nLinear constraint systems (LCSs) are a generalization of the well-known Peres-Mermin magic square, which has been recently used to prove a separation between the power of constant depth classical and quantum circuits. \n \nWhile binary LCSs have been studied in detail,
d-ary LCSs are less well-understood. In this thesis we consider linear constraint systems modulo
d>2. We give a simple proof, of the previously known fact, that any linear constraint system which admits a quantum solution consisting of generalized Pauli observables in odd dimension must be classically satisfiable. We further prove that, for odd
d, if a Pauli-like commutation relation between two variables in the LCS arises, then it has no quantum solutions in any dimensions, in stark contrast to the even
d case. We apply this result to various examples, for instance showing that many generalizations of the Peres-Mermin magic square do not give rise to a quantum vs. classical satisfiability gap.