⚛️ quantum physics

Adaptivity is all you need: Optimal stabilizer learning using just single-copy measurements

This paper demonstrates that adaptivity completely eliminates the sample complexity gap between single-copy and multi-copy measurements for learning stabilizer states, enabling an optimal $\Theta(n)$ -copy algorithm using only single-copy Clifford measurements while also extending to tolerant testing and states with bounded stabilizer nullity.

Original authors: L. Bittel, J. Eisert, W. Gong, A. A. Mele, L. Schatzki

Published 2026-10-02

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: L. Bittel, J. Eisert, W. Gong, A. A. Mele, L. Schatzki

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 quest to build powerful quantum computers, scientists rely on a special class of quantum states known as stabilizer states. These states are the backbone of error correction, the method used to protect fragile quantum information from noise, and they serve as a benchmark for testing how well a quantum machine is working. Because they can be described efficiently by classical computers, they also act as a bridge between the quantum and classical worlds. For years, researchers have faced a puzzling dilemma when trying to identify an unknown stabilizer state. If they could measure two copies of the state simultaneously, they could learn everything about it using a number of copies that grows linearly with the size of the system. However, if they were forced to measure only one copy at a time, without keeping any quantum memory between measurements, the old rules suggested they would need a number of copies that grew with the square of the system size. This gap implied that measuring one by one was fundamentally inefficient, requiring vastly more resources to achieve the same result.

A team of researchers has now shown that this inefficiency is not a fundamental law of nature, but a limitation of how the measurements were previously chosen. They have developed a new method that allows scientists to learn any stabilizer state using only single copies of the state, while still achieving the most efficient possible rate. The key to their success is adaptivity. Instead of measuring every copy in the same fixed way, the new approach uses the result of one measurement to decide how to measure the next. By adjusting the measurement strategy in real time based on what has already been learned, the researchers can close the gap between the single-copy and two-copy methods. Their algorithm learns the state in polynomial time, meaning the time required grows reasonably with the size of the system, and it does so using the same number of copies as the most efficient two-copy methods, without ever needing to hold two copies of the state at once.

The core of this discovery lies in a clever iterative process. Imagine trying to identify a hidden pattern by asking a series of yes-or-no questions. In the past, scientists asked the same type of question for every copy of the state, which was slow and inefficient. The new method asks a question, looks at the answer, and then immediately changes the next question to be more revealing. Specifically, the algorithm measures two copies of the state separately and compares the results. If the results differ, that difference reveals a specific piece of information about the state's structure. The researchers then use a mathematical operation, known as a Clifford gate, to rotate the state so that this newly found piece of information becomes easier to see in the next round. This process is repeated, with each step peeling away a layer of complexity and revealing more of the state's underlying structure, until the entire state is fully mapped out. Crucially, this rotation is chosen carefully so that it does not destroy the information already gathered in previous steps.

This breakthrough has immediate implications for how we test and verify quantum devices. The researchers demonstrated that their adaptive method can also distinguish between a perfect stabilizer state and a state that is merely close to one, a task known as tolerant testing. They proved that this can be done with the optimal number of copies, even when the input state is mixed or imperfect. Furthermore, they explored what happens when a quantum computer is allowed to store a small number of qubits in memory between measurements. They found a precise tradeoff: the more memory available, the fewer copies of the state are needed to perform the test. This relationship holds true even when the state is not perfectly pure, providing a complete map of the resources required for verification under different hardware constraints.

The utility of this approach extends beyond perfect stabilizer states. The researchers showed that the same adaptive mechanism works for states that are slightly more complex, specifically those that are close to stabilizer states but contain a limited number of non-standard operations. These states are important because they represent the kind of errors or deviations that might occur in real-world quantum circuits. The team proved that even for these more complex states, the adaptive single-copy method remains effective, requiring a number of copies that scales reasonably with the complexity of the deviation. This suggests that the ability to learn and test quantum states efficiently is not limited to idealized scenarios but can be applied to the messy reality of experimental physics.

The significance of this work lies in its demonstration that classical feedback can replace the need for coherent quantum memory in certain learning tasks. For a long time, it was believed that the quadratic gap in efficiency between single-copy and two-copy measurements was an unavoidable cost of not having access to multiple copies at once. This paper proves that by using the information gained from one measurement to guide the next, a single-copy protocol can achieve the same efficiency as a two-copy protocol. This finding reshapes our understanding of quantum learning, showing that adaptivity is a powerful tool that can overcome limitations previously thought to be fundamental. It opens the door to more efficient verification protocols for quantum computers, potentially reducing the experimental overhead required to certify that a quantum device is working correctly.

The researchers also addressed the limits of their method. They showed that while adaptivity closes the gap for stabilizer states, the efficiency gains depend on the specific structure of the state being learned. For states that are far from being stabilizer states, the benefits of adaptivity are less clear, and the method requires more copies to achieve the same accuracy. However, for the broad class of states that are central to quantum error correction and simulation, the new method provides a definitive solution. The work also highlights the importance of the specific mathematical structure of stabilizer states, which allows the adaptive updates to preserve the information already gathered. This structural insight is what makes the method work, and it suggests that similar adaptive strategies might be developed for other structured families of quantum states in the future.

In summary, this research resolves a long-standing question in quantum information science by showing that adaptivity is all that is needed to learn stabilizer states efficiently using single copies. The method is fast, requires no quantum memory between measurements, and works for both exact and approximate states. By turning the measurement process into a dynamic, learning loop, the researchers have removed a major barrier to efficient quantum state identification. This achievement not only advances our theoretical understanding of quantum learning but also provides a practical toolkit for the ongoing development and verification of quantum technologies. The results suggest that the path to scalable quantum computing may be less resource-intensive than previously thought, provided we can harness the power of adaptive measurement strategies.

Technical Summary: Adaptivity is All You Need: Optimal Stabilizer Learning Using Just Single-Copy Measurements

1. Problem Statement

Stabilizer states are fundamental to quantum error correction, fault-tolerant computation, and efficient classical simulation. A central operational question is how efficiently an unknown $n$ -qubit stabilizer state can be identified from experimental data.

Prior work established a significant gap in sample complexity depending on the measurement strategy:

Two-copy Bell sampling: Montanaro [9] showed that $\Theta(n)$ copies suffice to learn a stabilizer state using joint Bell measurements on pairs of copies. This is information-theoretically optimal.
Non-adaptive single-copy measurements: Ref. [10] demonstrated that if measurements are restricted to single copies and must be chosen non-adaptively (independent of previous outcomes), the sample complexity jumps to $\Omega(n^2)$ .

The open question addressed in this work is whether adaptive single-copy measurements (where the choice of measurement basis for the current copy depends on previous outcomes) can close this quadratic gap, achieving the optimal $\Theta(n)$ scaling without requiring coherent access to multiple copies simultaneously.

2. Methodology

Core Algorithm: Adaptive Stabilizer Learning

The authors propose a polynomial-time algorithm (Algorithm 1) that learns an arbitrary $n$ -qubit stabilizer state using only $\Theta(n)$ single-copy adaptive measurements. The algorithm relies on classical feedback to progressively transform the unknown state into a computational-basis state.

Key Mechanism:

Initialization: Start with the identity Clifford circuit $C = I$ . The goal is to find a Clifford $C$ such that $C|\psi\rangle = |z\rangle$ , where $|z\rangle$ is a computational-basis state.
Iterative Rounds: In each round, the algorithm measures two independent copies of the current transformed state $C|\psi\rangle$ in the computational basis, obtaining outcomes $x$ and $y$ .
Difference Sampling: The bitwise difference $u = x + y$ is computed. For a stabilizer state, if $u \neq 0$ , this vector identifies the $X$ -part of a stabilizer generator that is not diagonal in the computational basis.
Adaptive Update:
- The algorithm identifies a pivot index $i$ where $u_i = 1$ .
- It applies a CNOT-based Clifford operation $F_u$ that maps the identified stabilizer to a form $(e_i, v')$ .
- Crucially, $F_u$ preserves all previously found diagonal ( $Z$ -type) stabilizers because the pivot qubit $i$ is chosen such that existing $Z$ -stabilizers act trivially on it.
- A random local correction ( $H_i$ or $H_i S_i$ ) is applied to convert the new stabilizer into a $Z$ -type stabilizer.
Termination: The process repeats, monotonically increasing the dimension of the known diagonal stabilizer subspace. Once the dimension reaches $n$ , the state is a computational-basis state, which is fully determined by a final measurement. The original state is recovered as $|\psi\rangle = C^\dagger |z\rangle$ .

Extensions

The paper extends this adaptive mechanism to three additional scenarios:

Tolerant Learning: Learning the closest stabilizer state to a mixed or non-stabilizer input $\rho$ with fidelity $F_{\text{stab}}(\rho) > \sqrt{2/3}$ . The algorithm generates a list of candidates and uses classical shadows to estimate fidelities.
Tolerant Testing: Distinguishing between states with fidelity $\ge 1-\epsilon_1$ and $\le 1-\epsilon_2$ to the set of stabilizer states.
Memory-Assisted Testing: Testing with $k$ qubits of coherent quantum memory, interpolating between single-copy ( $k=0$ ) and two-copy ( $k=n$ ) regimes.
Low Stabilizer Nullity: Learning pure states with stabilizer nullity $r$ (states with a stabilizer subspace of dimension $n-r$ ), which includes states prepared by Clifford circuits with a bounded number of non-Clifford gates.

3. Key Contributions and Results

A. Optimal Single-Copy Learning

The primary result is a proof that adaptivity completely closes the gap between single-copy and two-copy learning.

Theorem II.1: An unknown $n$ -qubit stabilizer state can be learned with probability $1-\delta$ using $N = O(n + \log(1/\delta))$ copies and only adaptive single-copy measurements.
Complexity: The algorithm runs in polynomial time $O(n T^2)$ , where $T = O(n + \sqrt{n \log(1/\delta)} + \log(1/\delta))$ is the number of rounds.
Optimality: This matches the $\Theta(n)$ lower bound known for collective measurements, proving that coherent access to multiple copies is not necessary for optimal sample complexity in this setting.

B. Tolerant Learning and Testing

Tolerant Learning (Theorem III.1): For an input $\rho$ with $F_{\text{stab}}(\rho) \ge f_0 > \sqrt{2/3}$ , the algorithm outputs a stabilizer state with fidelity within $\xi$ of the optimum using $O(n + \xi^{-2}\log(1/\delta))$ copies.
Tolerant Testing (Theorem IV.1): The authors provide a polynomial-time tester distinguishing $F_{\text{stab}}(\rho) \ge 1-\epsilon_1$ from $F_{\text{stab}}(\rho) \le 1-\epsilon_2$ with sample complexity $O(n + \frac{\epsilon_2}{(\epsilon_2-\epsilon_1)^2} \log(1/\delta))$ . This resolves an open question regarding the feasibility of efficient tolerant testing with single-copy measurements.
Lower Bounds: The paper establishes that for pure inputs, $\Omega(n + \frac{\epsilon_2}{(\epsilon_2-\epsilon_1)^2})$ copies are necessary, confirming the optimality of the proposed tester.

C. Memory-Sample Tradeoff

Theorem V.1: For stabilizer testing with $k$ qubits of quantum memory, the optimal sample complexity is $\Theta(n - k + 1/\epsilon)$ .
Implication: To achieve sub-linear sample complexity (better than $\Theta(n)$ ), one must store nearly the entire state ( $k \approx n$ ). If $k=0$ , the complexity is $\Theta(n)$ ; if $k=n$ , it drops to $\Theta(1)$ .

D. Learning Low Nullity States

Theorem VI.1: States with stabilizer nullity $r$ (including $t$ -doped states with $t$ T-gates) can be learned using $O(2^r(n + \log(1/\delta)) + 2^r \epsilon^{-2}(r + \log(1/\delta)))$ copies.
Mechanism: The adaptive compression slows down by a factor of $2^r$ because only a $2^{-O(r)}$ fraction of difference samples reveal a valid stabilizer direction. However, "harmless" samples do not destroy the existing diagonal structure.

4. Significance and Claims

The paper claims that classical adaptivity alone suffices for sample-optimal stabilizer learning, eliminating the need for coherent multi-copy access. This is a significant finding because:

Closing the Gap: It demonstrates that the quadratic separation between non-adaptive single-copy learning ( $\Omega(n^2)$ ) and two-copy Bell sampling ( $\Theta(n)$ ) is an artifact of the non-adaptive restriction, not a fundamental limitation of single-copy measurements.
Experimental Feasibility: Since the algorithm requires only Clifford operations followed by computational-basis measurements on single copies, it is highly compatible with current experimental constraints where coherent multi-copy storage is difficult.
Structural Insight: The work highlights that stabilizer learning is a "natural structured setting" where adaptivity makes a fundamental difference. The measurement outcomes serve a dual purpose: providing data and identifying transformations that simplify the state while preserving previously discovered structure.
Broader Context: The authors note that while adaptivity helps in specific structured tasks (like bosonic Gaussian tomography or stabilizer learning), it does not offer asymptotic advantages for general mixed-state tomography in trace distance. This work helps delineate the boundaries of when adaptivity is beneficial in quantum learning.

The paper concludes by identifying open questions, such as whether the multiplicative dependence on $2^r$ for low-nullity states can be made additive, and whether the leading constant in the sample complexity can be reduced to match collective measurement bounds.