Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.06819

Improved bounds on stabilizer extent and Clifford rank

Pulkit Sinha, Benjamin Lovitz

quant-phSubmitted Oct 5, 2026• Announced Oct 6, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

Comments
31 pages

Related papers

Stabilizer rank bounds for magic-state orbits

Farrokh Labib, Vincent Russo

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 \le \log_3(2)/2 \approx 0.316$ for the Strange state, and $γ_{H_3}, γ_N \le \log_3(4)/3 \approx 0.421$ for the Hadamard-eigenstate and Norrell orbits, all strictly below the prior $γ_{T_3} \le 1/2$ baseline. We also prove the first nontrivial $Ω(m / \log m)$ 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 \le \log_2(3)/4 \approx 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.

quant-pharXiv:2605.28586•May 28, 2026•0 citations

Stabilizer Ranks, Barnes Wall Lattices and Magic Monotones

Amolak Ratan Kalra, Pulkit Sinha

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.

arXiv:2503.04101•Quantum•Jul 29, 2026•0 citations

A note on tomography of states with low stabilizer rank

Arkopal Dutt

In this note, we consider tomography of $n$-qubit quantum states $|ψ\rangle$ that are promised to have stabilizer rank $k$ i.e., admit a stabilizer decomposition of $|ψ\rangle = \sum_{i=1}^k c_i |φ_i\rangle$ where each $|φ_i\rangle$ is a stabilizer state. We give a tomography protocol for such states up to trace distance $\varepsilon > 0$ running in $\textsf{poly}(n,2^k,1/\varepsilon)$ time and thus can handle $k=O(\log n)$ efficiently. This follows from first showing that the stabilizer extent $ξ(|ψ\rangle)$, which is the minimal $\ell_1$ norm over the coefficients $\{c_i\}$ of any stabilizer decomposition of $|ψ\rangle$, can be bounded as $ξ(|ψ\rangle) \leq 2^{O(k)}$ and improving upon the previous best bound of $k^{O(k)}$. The protocol is then obtained by utilizing a tomography protocol for states with bounded stabilizer extent.

quant-pharXiv:2610.03658•Oct 5, 2026•0 citations

Lower Bounds on Stabilizer Rank

Shir Peleg, Amir Shpilka, Ben Lee Volk

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/log⁡n) . 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.

arXiv:2106.03214•Quantum•Feb 15, 2022•10 citations

Quadratic Lower Bounds on the Approximate Stabilizer Rank: A Probabilistic Approach

Saeed Adel Mehraban, Mehrdad Tahmasbi

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.

arXiv:2305.10277•ACM Symposium on Theory of Computing (STOC)•Jun 10, 2024•2 citations

Exponential lower bounds on the fermionic Gaussian rank of magic states and the bosonic coherent state rank of Fock states

Oliver Reardon-Smith

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 $\lvert M\rangle^{\otimes k}$ consists of $Ω(1.4^k)$ terms. Here $\lvert M\rangle$ 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 $m_j$ bosons in mode $j$ is exactly $\prod_{j}(1+m_j)$, 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.

quant-pharXiv:2610.03699•Oct 5, 2026•0 citations
We prove that every pure state of stabilizer rank at most kkk has stabilizer extent at most 2O(klog⁡(k+1))2^{O(\sqrt{k\log(k+1)})}2O(klog(k+1)​), and establish the analogous bound for the squared Clifford coefficient norm of Clifford-rank-kkk operators. This implies stabilizer fidelity at least 2−O(klog⁡(k+1))2^{-O(\sqrt{k\log(k+1)})}2−O(klog(k+1)​), resolving the quantitative conjecture of (Mehraban-Tamasbi, STOC, 2025), and proves an Ω(n2/log⁡n)Ω(n^2/\log n)Ω(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 TTT-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/log⁡n)Ω(n^2/\log n)Ω(n2/logn) lower bound for exact representations of nnn-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)O((\log n)^2/\log\log n)O((logn)2/loglogn), respectively, a log⁡n\log nlogn improvement over prior work (Kalra-Sinha, Quantum, 2026). We also obtain tomography algorithms for states of stabilizer rank at most kkk, with poly(n)2O(klog⁡(k+1))poly(n)2^{O(\sqrt{k\log(k+1)})}poly(n)2O(klog(k+1)​) time and copy complexity, a nearly square-root improvement in the exponent over the best-known algorithm.
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≤log⁡3(2)/2≈0.316γ_S \le \log_3(2)/2 \approx 0.316γS​≤log3​(2)/2≈0.316 for the Strange state, and γH3,γN≤log⁡3(4)/3≈0.421γ_{H_3}, γ_N \le \log_3(4)/3 \approx 0.421γH3​​,γN​≤log3​(4)/3≈0.421 for the Hadamard-eigenstate and Norrell orbits, all strictly below the prior γT3≤1/2γ_{T_3} \le 1/2γT3​​≤1/2 baseline. We also prove the first nontrivial Ω(m/log⁡m)Ω(m / \log m)Ω(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≤log⁡2(3)/4≈0.396γ_T \le \log_2(3)/4 \approx 0.396γ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 nnn-qubit quantum states ∣ψ⟩|ψ\rangle∣ψ⟩ that are promised to have stabilizer rank kkk i.e., admit a stabilizer decomposition of ∣ψ⟩=∑i=1kci∣φi⟩|ψ\rangle = \sum_{i=1}^k c_i |φ_i\rangle∣ψ⟩=∑i=1k​ci​∣φi​⟩ where each ∣φi⟩|φ_i\rangle∣φi​⟩ is a stabilizer state. We give a tomography protocol for such states up to trace distance ε>0\varepsilon > 0ε>0 running in poly(n,2k,1/ε)\textsf{poly}(n,2^k,1/\varepsilon)poly(n,2k,1/ε) time and thus can handle k=O(log⁡n)k=O(\log n)k=O(logn) efficiently. This follows from first showing that the stabilizer extent ξ(∣ψ⟩)ξ(|ψ\rangle)ξ(∣ψ⟩), which is the minimal ℓ1\ell_1ℓ1​ norm over the coefficients {ci}\{c_i\}{ci​} of any stabilizer decomposition of ∣ψ⟩|ψ\rangle∣ψ⟩, can be bounded as ξ(∣ψ⟩)≤2O(k)ξ(|ψ\rangle) \leq 2^{O(k)}ξ(∣ψ⟩)≤2O(k) and improving upon the previous best bound of kO(k)k^{O(k)}kO(k). The protocol is then obtained by utilizing a tomography protocol for states with bounded stabilizer extent.
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/log⁡n) . 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.
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\lvert M\rangle^{\otimes k}∣M⟩⊗k consists of Ω(1.4k)Ω(1.4^k)Ω(1.4k) terms. Here ∣M⟩\lvert M\rangle∣M⟩ is the most standard magic state for fermionic linear optics: the 444 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−δ21-δ^21−δ2. Our results on exact fermionic Gaussian rank apply directly to any product of kkk 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 nnn-mode bosonic Fock state with mjm_jmj​ bosons in mode jjj is exactly ∏j(1+mj)\prod_{j}(1+m_j)∏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.