⚛️ quantum physics

Improved bounds on stabilizer extent and Clifford rank

This paper establishes improved bounds on stabilizer extent and Clifford rank, resolving a quantitative conjecture, generalizing lower bounds for approximate stabilizer rank to arbitrary non-stabilizer states, and deriving stronger results for function representation, pseudorandomness, and tomography algorithms.

Original authors: Pulkit Sinha, Benjamin Lovitz

Published 2026-10-06

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Pulkit Sinha, Benjamin Lovitz

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of quantum computing, there is a special class of calculations that classical computers can handle with ease. These are operations built from a specific set of rules and starting points, known as stabilizer states and Clifford gates. Think of these as the basic building blocks of a quantum system that behave predictably, allowing a standard computer to track their evolution without getting overwhelmed. However, to perform truly powerful quantum tasks, scientists must introduce a special ingredient that breaks these simple rules. This ingredient, often called a magic state, adds the necessary complexity to solve problems that are otherwise impossible. The central challenge for researchers is to understand exactly how much of this "magic" is required. If a quantum state is built from a certain number of these magic ingredients, how difficult is it to describe or simulate using only the simple, predictable building blocks?

A team of researchers has now answered this question with a new mathematical proof that tightens the limits on how efficiently these complex states can be described. They focused on a measure called stabilizer rank, which counts the minimum number of simple building blocks needed to construct a specific quantum state. For years, scientists knew that states with a low rank were easier to simulate, but they lacked a precise understanding of how the complexity of the description grew as the number of building blocks increased. The authors proved that the complexity of describing such a state grows much more slowly than previously thought. Specifically, they showed that if a state is made from a certain number of simple components, the total "weight" or size of the mathematical description needed to represent it is bounded by a formula that involves the square root of that number, rather than the number itself. This finding resolves a long-standing conjecture about the relationship between the count of ingredients and the size of the description.

The implications of this discovery ripple through several areas of quantum science. First, it establishes a firm lower limit on how many simple components are needed to approximate the repeated copies of a magic state. The researchers proved that for any non-simple quantum state, the number of simple components required to approximate it grows nearly quadratically with the number of copies. This means that as you stack more and more of these complex states together, the cost to simulate them on a classical computer explodes much faster than earlier estimates suggested. This result generalizes previous findings that were limited to specific types of magic states, showing that the difficulty is a universal feature of all non-simple quantum states.

Beyond simulation, the work provides new tools for distinguishing between random quantum noise and carefully crafted quantum states. The researchers demonstrated that if a collection of quantum states is truly random, it is extremely unlikely to contain any state that can be described using a small number of simple components. This creates a reliable test: if a state can be described simply, it is almost certainly not random. This insight helps define the boundaries of what is possible in quantum cryptography and the creation of pseudorandom sequences, which are vital for secure communication. The proof also rules out the existence of certain types of random quantum systems that were previously thought to be possible, sharpening our understanding of the landscape of quantum information.

The paper also offers a practical benefit for scientists trying to learn the properties of unknown quantum states. By proving that states with a low number of components have a manageable mathematical description, the authors derived a new, faster method for quantum tomography. This is the process of figuring out what a quantum state is by measuring it many times. Their method allows researchers to reconstruct the state of a system using significantly fewer measurements and less computing time than before, provided the system is not too complex. This improvement is substantial, reducing the computational effort required to the point where it becomes feasible to analyze larger systems than was previously possible.

The researchers arrived at these conclusions by developing a clever strategy involving random projections. Instead of trying to analyze the entire complex state at once, they showed how to break the problem down by projecting the state onto smaller, simpler spaces. They proved that by randomly choosing these spaces, they could eliminate large groups of the simple components at once while preserving the structure of the rest. This process allowed them to group the components into clusters and show that the total complexity could not exceed a specific bound. The method relies on the fact that these simple quantum states have a rigid internal structure that prevents them from canceling each other out in ways that would hide their true complexity.

The work also extends to the study of Boolean functions, which are the logic operations at the heart of classical computing. The researchers applied their findings to show that expressing a specific logic function, known as the AND function, using a particular type of mathematical wave requires a nearly quadratic number of terms. This improves upon the best previous estimate, which suggested only a linear growth. This result connects the abstract world of quantum states to concrete problems in computer science, showing that the limitations of quantum simulation have direct consequences for how efficiently we can represent classical logic.

In the end, this research provides a clearer map of the terrain between simple and complex quantum systems. It confirms that the gap between the two is wider than previously believed, making it harder to simulate complex quantum systems with simple tools. The findings are not just theoretical; they offer concrete algorithms for learning and distinguishing quantum states, and they set new standards for what is possible in quantum simulation. The authors have shown that while quantum systems can be incredibly complex, their complexity follows strict mathematical rules that can be understood and quantified. This clarity allows scientists to better predict the behavior of quantum computers and to design more efficient ways to work with them.

Technical Summary: Improved Bounds on Stabilizer Extent and Clifford Rank

Problem Statement
The paper addresses the quantitative relationship between the stabilizer rank of a quantum state (or operator) and its stabilizer extent (or Clifford coefficient norm). The stabilizer rank, $\chi(|\psi\rangle)$ , measures the minimum number of stabilizer states required to exactly decompose a state $|\psi\rangle$ . The stabilizer extent, $\xi(|\psi\rangle)$ , measures the minimum squared sum of coefficients in such a decomposition.

While the Gottesman-Knill theorem establishes that Clifford circuits on stabilizer states are classically simulable, general quantum computations require "magic" resources. Simulation algorithms often rely on decomposing non-stabilizer states into stabilizer states. The efficiency of these algorithms depends on the stabilizer extent, as small coefficients allow for efficient sampling (sparsification). However, a state with a small stabilizer rank might theoretically have a large extent if large coefficients cancel out in the decomposition.

The central problem is to determine how strongly a bound on stabilizer rank constrains the stabilizer extent. Specifically, the paper investigates the quantitative conjecture by Mehraban–Tahmasbi [MT25], which posited that states of stabilizer rank $k$ must have a stabilizer fidelity (overlap with the nearest stabilizer state) bounded below by $2^{-k/C}$ for some constant $C$ . Previous work by Kalra–Sinha [KS26] established an upper bound on the extent of $\xi(|\psi\rangle) \le 2^{O(k \log k)}$ for rank- $k$ states. The authors aim to improve this bound and resolve the conjecture regarding the scaling of fidelity with rank.

Methodology
The authors employ a novel approach combining randomized projections onto stabilizer codespaces with a clustering argument based on code overlap.

Clustering via Code Merging: The authors start with a decomposition of a state $|\psi\rangle$ into $k$ stabilizer states. They define a "cluster" as a subset of these states contained within a common stabilizer codespace. Using Lemma 3.2, they show that if two codespaces have a large overlap (measured by the operator norm of their projectors), they can be merged into a larger codespace with a dimension controlled by the overlap.
Dichotomy: The clustering process leads to a dichotomy (Lemma 3.3): either a low-dimensional codespace contains a significant number of the original stabilizer terms, or the terms split into clusters that are nearly orthogonal.
- Case 1 (Low-dimensional containment): If a codespace of dimension $d$ contains $r$ terms, the authors use the fact that any state in a $d$ -dimensional stabilizer code has a decomposition with coefficient sum bounded by $\sqrt{d}$ .
- Case 2 (Near orthogonality): If the clusters are nearly orthogonal, cancellation between them is limited. The authors can bound the extent by summing the contributions of each cluster.
Block Elimination via Randomized Projections: To handle the terms within a cluster, the authors utilize randomized Pauli projections. By projecting onto the eigenspace of a random Pauli operator satisfying the code constraints, they can eliminate a block of $r$ stabilizer terms while preserving the stabilizer nature of the remaining terms (up to a scalar). This allows for an inductive reduction of the problem size.
Extension to Clifford Operators: For operators, the authors adapt this framework using the normalized Choi map. They introduce the concept of entanglement deficit (the number of ebits missing from maximal entanglement). They track how Pauli projections affect this deficit (increasing it by at most one) to control the cost of decomposing intermediate states into maximally entangled stabilizer states, which correspond to Clifford unitaries.

Key Contributions and Results

Improved Stabilizer Rank–Extent Bound (Theorem 1.1):
The authors prove that for any $n$ -qubit vector $|v\rangle$ with stabilizer rank $\chi(|v\rangle) \le k$ , the stabilizer extent is bounded by:
$\xi(|v\rangle) \le 2^{O(\sqrt{k} \log(k+1))} \|v\|^2$
This improves upon the previous $2^{O(k \log k)}$ bound by Kalra–Sinha [KS26] by a square-root factor in the exponent.
Resolution of the Quantitative Conjecture:
The new bound implies a stabilizer fidelity lower bound of $FS(|\psi\rangle) \ge 2^{-O(\sqrt{k} \log(k+1))}$ . This resolves the quantitative conjecture of [MT25] (which suggested $2^{-k/C}$ ) and improves the scaling by a square-root factor in the exponent.
Clifford Rank–Coefficient Norm Bound (Theorem 1.2):
An analogous bound is established for operators. For an operator $A$ with Clifford rank $\chi_C(A) \le k$ , the squared Clifford coefficient norm satisfies:
$\Lambda_C(A)^2 \le 2^{O(\sqrt{k} \log(k+1))} 2^{-n} \|A\|_F^2$
Lower Bounds for Approximate Stabilizer Rank:
Applying these bounds to tensor powers of non-stabilizer states yields a lower bound on the approximate stabilizer rank. For any fixed non-stabilizer qubit state $|\phi\rangle$ , the approximate stabilizer rank of $|\phi\rangle^{\otimes n}$ is:
$\chi_\delta(|\phi\rangle^{\otimes n}) = \Omega_\phi(n^2 / \log n)$
This generalizes the best-known lower bound for $T$ -states [MT24] to arbitrary non-stabilizer qubit states.
Classical Representation of Boolean Functions:
The Clifford rank bound implies a lower bound for the exact representation of the $n$ -bit AND function using quadratic phases. The number of quadratic phases required, $Q(n)$ , satisfies:
$Q(n) = \Omega(n^2 / \log n)$
This improves upon the previous linear lower bound.
Pseudorandomness and Learning:
- Pseudorandomness: The results rule out the existence of pseudorandom state and unitary ensembles with approximate stabilizer/Clifford rank $O((\log n)^2 / \log \log n)$ , improving the threshold from $O(\log n / \log \log n)$ in [KS26].
- Tomography: The authors derive tomography algorithms for states of stabilizer rank at most $k$ with time and copy complexity of $\text{poly}(n) 2^{O(\sqrt{k} \log k)}$ . This represents a nearly square-root improvement in the exponent over the best-known algorithm based on [KS26].

Significance and Claims
The paper claims that the derived bounds provide a stronger connection between the structural complexity (rank) of quantum states/operators and their coefficient norms (extent). By tightening the bound on extent, the authors demonstrate that states with low stabilizer rank cannot have arbitrarily small overlap with stabilizer states, thereby limiting the "cancellation" effects that could otherwise hide complexity.

The significance lies in:

Theoretical Resolution: Settling the quantitative conjecture of [MT25] with a tighter bound.
Generalization: Extending lower bounds for magic-state tensor powers from specific states (like $|T\rangle$ ) to all non-stabilizer qubit states.
Algorithmic Improvement: Providing a nearly square-root improvement in the exponent for the complexity of learning and tomography of low-rank states and unitaries.
Classical Complexity: Establishing a nearly quadratic lower bound for the quadratic-phase rank of the AND function, improving the state-of-the-art in classical representation theory.

The authors note that while their bound $2^{O(\sqrt{k} \log k)}$ is stronger than the concurrent work [Dut26] (which achieves $2^{O(k)}$ ), it is not yet known if the exponent can be reduced to $O(\sqrt{k})$ or if the extent is polynomially bounded in rank. They suggest that the logarithmic loss in their current bounds stems from the dimension cost of merging codespaces, and a stronger clustering bound could potentially remove this factor.

More like this