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:2503.04101 · Quantum

Stabilizer Ranks, Barnes Wall Lattices and Magic Monotones

Amolak Ratan Kalra, Pulkit Sinha

Published Jul 29, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.22331/q-2026-07-29-2179

Related papers

Improved bounds on stabilizer extent and Clifford rank

Pulkit Sinha, Benjamin Lovitz

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.

quant-pharXiv:2610.06819•Oct 6, 2026•0 citations

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

New techniques for bounding stabilizer rank

Benjamin Lovitz, Vincent Steffan

In this work, we present number-theoretic and algebraic-geometric techniques for bounding the stabilizer rank of quantum states. First, we refine a number-theoretic theorem of Moulton to exhibit an explicit sequence of product states with exponential stabilizer rank but constant approximate stabilizer rank, and to provide alternate (and simplified) proofs of the best-known asymptotic lower bounds on stabilizer rank and approximate stabilizer rank, up to a log factor. Second, we find the first non-trivial examples of quantum states with multiplicative stabilizer rank under the tensor product. Third, we introduce and study the generic stabilizer rank using algebraic-geometric techniques.

arXiv:2110.07781•Quantum•Apr 20, 2022•6 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

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

Clifford entropy

Gianluca Cuffaro, Matthew B. Weiss

We introduce the Clifford entropy, a measure of how close an arbitrary unitary is to a Clifford unitary, which generalizes the stabilizer entropy for states. We show that this quantity vanishes if and only if a unitary is Clifford, is invariant under composition with Clifford unitaries, and is subadditive under tensor products. Rewriting the Clifford entropy in terms of the stabilizer entropy of the corresponding Choi state allows us to derive an upper bound: that this bound is not tight follows from considering the properties of symmetric informationally complete sets. Nevertheless we are able to numerically estimate the maximum in low dimensions, comparing it to the average over all unitaries, which we derive analytically. Finally, harnessing a concentration of measure result, we show that as the dimension grows large, with probability approaching unity, the ratio between the Clifford entropy of a Haar random unitary and that of a fixed magic gate gives a lower bound on the depth of a doped Clifford circuit which realizes the former in terms of the latter. In fact, numerical evidence suggests that this result holds reliably even in low dimensions. We conclude with several directions for future research.

quant-pharXiv:2512.23050•Dec 30, 2025•0 citations
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.
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 this work, we present number-theoretic and algebraic-geometric techniques for bounding the stabilizer rank of quantum states. First, we refine a number-theoretic theorem of Moulton to exhibit an explicit sequence of product states with exponential stabilizer rank but constant approximate stabilizer rank, and to provide alternate (and simplified) proofs of the best-known asymptotic lower bounds on stabilizer rank and approximate stabilizer rank, up to a log factor. Second, we find the first non-trivial examples of quantum states with multiplicative stabilizer rank under the tensor product. Third, we introduce and study the generic stabilizer rank using algebraic-geometric techniques.
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.
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.
We introduce the Clifford entropy, a measure of how close an arbitrary unitary is to a Clifford unitary, which generalizes the stabilizer entropy for states. We show that this quantity vanishes if and only if a unitary is Clifford, is invariant under composition with Clifford unitaries, and is subadditive under tensor products. Rewriting the Clifford entropy in terms of the stabilizer entropy of the corresponding Choi state allows us to derive an upper bound: that this bound is not tight follows from considering the properties of symmetric informationally complete sets. Nevertheless we are able to numerically estimate the maximum in low dimensions, comparing it to the average over all unitaries, which we derive analytically. Finally, harnessing a concentration of measure result, we show that as the dimension grows large, with probability approaching unity, the ratio between the Clifford entropy of a Haar random unitary and that of a fixed magic gate gives a lower bound on the depth of a doped Clifford circuit which realizes the former in terms of the latter. In fact, numerical evidence suggests that this result holds reliably even in low dimensions. We conclude with several directions for future research.