We prove that every pure state of stabilizer rank at most $k$ has stabilizer extent at most $2^{O(\sqrt{k\log(k+1)})}$, and establish the analogous bound for the squared Clifford coefficient norm of Clifford-rank-$k$ operators. This implies stabilizer fidelity at least $2^{-O(\sqrt{k\log(k+1)})}$, resolving the quantitative conjecture of (Mehraban-Tamasbi, STOC, 2025), and proves an $Ω(n^2/\log n)$ lower bound for the approximate stabilizer rank of tensor powers of any non-stabilizer qubit state. The latter result generalizes the best-known lower bound for tensor powers of $T$-states (Mehraban-Tamasbi, STOC, 2024) to arbitrary non-stabilizer qubit states, including magic states.
As a consequence of the Clifford rank--norm inequality, we obtain an $Ω(n^2/\log n)$ lower bound for exact representations of $n$-bit AND function by quadratic phases, improving the previous best-known linear bound. Further consequences rule out pseudorandom state and unitary ensembles with approximate stabilizer and Clifford rank $O((\log n)^2/\log\log n)$, respectively, a $\log n$ improvement over prior work (Kalra-Sinha, Quantum, 2026). We also obtain tomography algorithms for states of stabilizer rank at most $k$, with $poly(n)2^{O(\sqrt{k\log(k+1)})}$ time and copy complexity, a nearly square-root improvement in the exponent over the best-known algorithm.
AI Summary
The paper asks how strongly a short stabilizer decomposition constrains coefficient size despite cancellation between nonorthogonal terms. It proves that every vector of stabilizer rank at most $k$ satisfies $\xi(v)\le 2^{O(\sqrt{k\log(k+1)})}\|v\|^2$. For operators of Clifford rank at most $k$, it establishes the analogous bound $L_C(A)^2\le 2^{O(\sqrt{k\log(k+1)})}2^{-n}\|A\|_F^2$. These bounds optimize over new decompositions rather than controlling coefficients in a supplied decomposition.
The state bound implies stabilizer fidelity at least $2^{-O(\sqrt{k\log(k+1)})}$, resolving the stated quantitative rank–fidelity conjecture. Consequences include an $\Omega(n^2/\log n)$ approximate stabilizer-rank lower bound for tensor powers of every fixed non-stabilizer qubit pure state, at any fixed Euclidean error below one; an $\Omega(n^2/\log n)$ lower bound for exact quadratic-phase representations of AND; and exclusion of approximate rank $O((\log n)^2/\log\log n)$ from pseudorandom state and unitary ensembles. Substitution into existing learning algorithms gives low-rank state tomography with sample and quantum-time complexity $\operatorname{poly}(n,1/\epsilon,\log(1/\beta))2^{O(\sqrt{k\log(k+1)})}$.
The proof clusters stabilizer terms into codespaces using projector overlaps, then averages Pauli projections to eliminate entire clusters. The operator extension tracks entanglement deficit in Choi states. The logarithmic loss arises from code-merging costs; removing it, or obtaining polynomial rank–extent bounds, remains open. The AND result concerns exact representation, not constant absolute approximation error. Learning guarantees use existing algorithms and need not return decompositions of the promised rank.
Almost certainly largely AI-generatedAI use disclosed
GPT-6 Astra and GPT 5.6-Sol were used extensively in this work, including to generate mathematical arguments, and to draft and revise the manuscript.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
We prove that every pure state of stabilizer rank at most k has stabilizer extent at most 2O(klog(k+1)), and establish the analogous bound for the squared Clifford coefficient norm of Clifford-rank-k operators. This implies stabilizer fidelity at least 2−O(klog(k+1)), resolving the quantitative conjecture of (Mehraban-Tamasbi, STOC, 2025), and proves an Ω(n2/logn) lower bound for the approximate stabilizer rank of tensor powers of any non-stabilizer qubit state. The latter result generalizes the best-known lower bound for tensor powers of T-states (Mehraban-Tamasbi, STOC, 2024) to arbitrary non-stabilizer qubit states, including magic states.
As a consequence of the Clifford rank--norm inequality, we obtain an Ω(n2/logn) lower bound for exact representations of n-bit AND function by quadratic phases, improving the previous best-known linear bound. Further consequences rule out pseudorandom state and unitary ensembles with approximate stabilizer and Clifford rank O((logn)2/loglogn), respectively, a logn improvement over prior work (Kalra-Sinha, Quantum, 2026). We also obtain tomography algorithms for states of stabilizer rank at most k, with poly(n)2O(klog(k+1)) time and copy complexity, a nearly square-root improvement in the exponent over the best-known algorithm.
The paper asks how strongly a short stabilizer decomposition constrains coefficient size despite cancellation between nonorthogonal terms. It proves that every vector of stabilizer rank at most k satisfies ξ(v)≤2O(klog(k+1))∥v∥2. For operators of Clifford rank at most k, it establishes the analogous bound LC(A)2≤2O(klog(k+1))2−n∥A∥F2. These bounds optimize over new decompositions rather than controlling coefficients in a supplied decomposition.
The state bound implies stabilizer fidelity at least 2−O(klog(k+1)), resolving the stated quantitative rank–fidelity conjecture. Consequences include an Ω(n2/logn) approximate stabilizer-rank lower bound for tensor powers of every fixed non-stabilizer qubit pure state, at any fixed Euclidean error below one; an Ω(n2/logn) lower bound for exact quadratic-phase representations of AND; and exclusion of approximate rank O((logn)2/loglogn) from pseudorandom state and unitary ensembles. Substitution into existing learning algorithms gives low-rank state tomography with sample and quantum-time complexity poly(n,1/ϵ,log(1/β))2O(klog(k+1)).
The proof clusters stabilizer terms into codespaces using projector overlaps, then averages Pauli projections to eliminate entire clusters. The operator extension tracks entanglement deficit in Choi states. The logarithmic loss arises from code-merging costs; removing it, or obtaining polynomial rank–extent bounds, remains open. The AND result concerns exact representation, not constant absolute approximation error. Learning guarantees use existing algorithms and need not return decompositions of the promised rank.
The stabilizer rank of a quantum state ψ is the minimal r such that |ψ⟩=∑j=1rcj|φj⟩ for cj∈C and stabilizer states φj . The running time of several classical simulation methods for quantum circuits is determined by the stabilizer rank of the n -th tensor power of single-qubit magic states.We prove a lower bound of Ω(n) on the stabilizer rank of such states, improving a previous lower bound of Ω(n) of Bravyi, Smith and Smolin \cite{BSS16}. Further, we prove that for a sufficiently small constant δ , the stabilizer rank of any state which is δ -close to those states is Ω(n/logn) . This is the first non-trivial lower bound for approximate stabilizer rank.Our techniques rely on the representation of stabilizer states as quadratic functions over affine subspaces of F2n , and we use tools from analysis of boolean functions and complexity theory. The proof of the first result involves a careful analysis of directional derivatives of quadratic polynomials, whereas the proof of the second result uses Razborov-Smolensky low degree polynomial approximations and correlation bounds against the majority function.
Distinct Clifford orbits of magic states can exhibit different stabilizer ranks at small tensor powers. We establish this for qutrits, where the single-qutrit Clifford group has four inequivalent orbits of magic states: Strange, Norrell, Hadamard-eigenstate, and the qutrit T-state, but a nontrivial upper bound on the asymptotic exponent had been pinned down for only the qutrit T-state. For the other three orbits we give explicit stabilizer decompositions, yielding upper bounds on the per-copy asymptotic stabilizer-rank exponent: γS≤log3(2)/2≈0.316 for the Strange state, and γH3,γN≤log3(4)/3≈0.421 for the Hadamard-eigenstate and Norrell orbits, all strictly below the prior γT3≤1/2 baseline. We also prove the first nontrivial Ω(m/logm) asymptotic lower bounds for the Hadamard-eigenstate and Norrell orbits, and exhibit two-qutrit Clifford circuits that convert two copies of these states into an injectable phase state with constant success probability, enabling constant-overhead injection of one non-Clifford diagonal gate per orbit. In the case of qubits, we give a closed-form decomposition of the qubit T-type orbit at four copies matching the existing γT≤log2(3)/4≈0.396 exponent via a direct algebraic identity rather than an entangled cat-state construction. An open-source library stabrank accompanies the paper, with Lean 4 proof formalizations of all the decompositions.
In 2024, Kliuchnikov and Schönnenbeck showed a connection between the Barnes Wall lattices, stabilizer states and Clifford operations. In this work, we study their results and relate them to the problem of lower bounding stabilizer ranks. We show the first quantitative lower bound on stabilizer fidelity as a function of stabilizer ranks, which reproduces the linear-by-log lower bound for χ δ ( | H ⟩ ⊗ n ) , i.e, on the approximate stabilizer rank of | H ⟩ ⊗ n . In fact, we show that the lower bound holds even when the fidelity between the approximation and | H ⟩ ⊗ n is exponentially small, which is currently the best lower bound in this regime.Next, we define a new magic monotone for pure states, the Barnes Wall norm, and its corresponding approximate variant. We upper bound these monotones by the C S -count of state preparation, and also by the stabilizer ranks. In particular, the upper bound given by the C S -count is tight, in the sense that we exhibit states that achieve the bound.Apart from these results, we give a Fidelity Amplification algorithm, which provides a trade-off between approximation error and the stabilizer rank. As a corollary, it gives us a way to compose approximate stabilizer decompositions into approximate decompositions of their tensor products.Finally, we provide an alternate, elementary proof of the existence and density of product states with maximal stabilizer ranks, which was first proven by Lovitz and Steffan (2022), where they used results from algebraic geometry.
In this note, we consider tomography of n-qubit quantum states ∣ψ⟩ that are promised to have stabilizer rank k i.e., admit a stabilizer decomposition of ∣ψ⟩=∑i=1kci∣φi⟩ where each ∣φi⟩ is a stabilizer state. We give a tomography protocol for such states up to trace distance ε>0 running in poly(n,2k,1/ε) time and thus can handle k=O(logn) efficiently. This follows from first showing that the stabilizer extent ξ(∣ψ⟩), which is the minimal ℓ1 norm over the coefficients {ci} of any stabilizer decomposition of ∣ψ⟩, can be bounded as ξ(∣ψ⟩)≤2O(k) and improving upon the previous best bound of kO(k). The protocol is then obtained by utilizing a tomography protocol for states with bounded stabilizer extent.
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.
Recent algorithms for classical simulation of quantum mechanics have runtime whose superpolynomial component is given by a linear dependence on the number of terms required to write large tensor products of certain "magic" states as superpositions of "free" states (which may be stabilizer states, fermionic Gaussian states or others). Surprisingly little is known about the number of terms in such decompositions, called ranks (e.g. the stabilizer rank, fermionic-Gaussian rank etc.). For complexity theoretic reasons they are expected to grow exponentially in the number of tensor factors but, while exponential upper bounds are known for both the stabilizer and fermionic-Gaussian rank of magic states; the best known lower bounds on the stabiliser rank are quadratic, and no bounds on the fermionic-Gaussian rank are known beyond fixed constants. In this work we prove that any fermionic Gaussian decomposition of ∣M⟩⊗k consists of Ω(1.4k) terms. Here ∣M⟩ is the most standard magic state for fermionic linear optics: the 4 qubit state that may be consumed to implement a swap gate. We also prove essentially matching bounds on the δ-approximate rank of the same state, lower bounding it by the same quantity that bounds the exact rank, multiplied by a factor of 1−δ2. Our results on exact fermionic Gaussian rank apply directly to any product of k fixed parity non-Gaussian states, although the same is not true of the approximate rank. Finally, we prove that the coherent state border rank of an n-mode bosonic Fock state with mj bosons in mode j is exactly ∏j(1+mj), answering a conjecture of Ref. [1] and obtain lower bounds on the approximate coherent state rank given by the same quantity multiplied by a function of the fidelity of the approximation, emphasizing the broad applicability of the method we employ.