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

arXiv:2610.02031 · quant-ph · Submitted 2026-10-01 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: Today's paper: "Adaptivity is all you need".

Mira: Stabilizer states are central to quantum computing and error correction, but their learnability exhibits a gap where non-adaptive single-copy measurements require an exponential number of copies,

Kai: First, who's behind it and why it matters.

Title and authors: Mira: So, shifting from the specific mechanism of the paper to the context, Kai, let's look at what they are calling "Adaptivity is all you need: Optimal stabilizer learning using just single-copy measurements." The title itself really frames this as a fundamental shift in how we think about state characterization.

Kai: I agree; it suggests that adaptivity isn't just a nice feature, but the essential ingredient needed to bridge the gap between two-copy measurements and single-copy measurements for learning stabilizer states. It’s not just about finding a clever trick, it seems like the central argument.

Lev: From my perspective in error correction, what does that title imply about the necessary resource trade-offs? Does it suggest that for certain tasks, we can afford to sacrifice multi-copy access if we use adaptive classical feedback instead?

Mira: Precisely; they are arguing that for stabilizer learning, the cost of coherence across multiple copies can be effectively traded for a polynomial number of single-copy measurements guided by adaptivity. They're showing that the structure revealed through sequential measurement outcomes is enough to guide the necessary operations.

Kai: It seems like they are proposing a more resource-efficient pathway for quantum state characterization, moving us away from demanding high fidelity copies just to get a full picture of the stabilizer structure.

Lev: If we can achieve this scaling, it changes how we estimate error syndromes on hardware; instead of needing many copies to build an ideal measurement apparatus, we rely on real-time adaptation based on what we measure.

Mira: That's the big picture—the idea that the computational power of classical adaptivity is leveraged to overcome a limitation imposed by physical resource constraints in quantum measurements. It’s a statement about how information flows in these systems.

Kai: It frames it as a fundamental problem: how to extract full structural information from limited single-copy data efficiently, and this paper provides the answer via adaptation.

Lev: So the immediate implication is that if we can build hardware where real-time classical feedback is fast enough, we don't need to dedicate resources just for preparing massive entanglement before measurement.

Mira: That’s a very practical consideration; it connects the abstract mathematical structure of stabilizers to the constraints of experimental reality. It moves the discussion from pure theory into something that could actually be tested on a chip.

Kai: Exactly, so we're setting the stage for looking at how this translates into concrete experimental setups in our lab.

The paper's summary: Mira: Now, let's look at what the actual core of "Adaptivity is all you need: Optimal stabilizer learning using just single-copy measurements" actually says about the methodology they developed. It’s about how they construct that polynomial-time adaptive algorithm.

Kai: The paper summarizes it by explaining that the main idea is to convert non-diagonal stabilizers into Z-type ones without destroying the ones already found, and this is done by measuring two copies separately in the computational basis and looking at their bitwise difference.

Lev: That bitwise difference is what allows them to pinpoint exactly which X-part of a stabilizer isn't diagonal, right? It sounds like a very precise diagnostic tool for identifying the necessary correction.

Mira: It is; and based on that information, they adaptively choose a Clifford operation C from F u C to turn that stabilizer into its Z-type counterpart while keeping the previously identified ones intact. This sequential conversion is what drives the learning process forward.

Kai: So, each round feeds the results of the measurement back into a circuit update, progressively increasing our set of known diagonal stabilizers until we hit a computational basis state where everything is determined.

Lev: That sounds like a very systematic way to systematically resolve the stabilizer space one element at a time, rather than trying to solve the whole system at once. It’s methodical problem-solving.

Mira: Exactly, and they are showing that this method is polynomial-time, which means it scales reasonably well with the number of qubits n, which is a key requirement for any useful algorithm.

Kai: So, instead of needing a massive initial state preparation to get an answer, we just need the iterative measurement and feedback loop to drive the transformation toward that known state.

Lev: If this holds up under real hardware conditions, it’s promising because it means we don't need exponential resources upfront for initialization.

Mira: The paper also extends this concept to tolerant learning where they introduce a mechanism where they save one stabilizer candidate in every round to estimate its fidelity on fresh copies to return the best one. That shows they are thinking about robustness right from the start.

Kai: That tolerance part, using fresh copies for estimation, sounds like a necessary safety net when dealing with imperfect states, ensuring we don't get stuck on a poor state just because of measurement noise.

The paper's improvements: Mira: Now we move into the specific enhancements they propose and what that means for practical application, especially concerning tolerant learning and testing. They go beyond just exact learning to address how to handle states that are close to a stabilizer.

Kai: One key improvement is their tolerant learning protocol, which uses adaptive Clifford updates and saves one stabilizer candidate in every round to estimate fidelities on fresh copies of the state to return the best one. This yields an algorithm using O(R mu(n, delta) + xi-two (R mu/delta)) copies for a fidelity above p two/three.

Lev: That scaling is what I need to know; it’s polynomial dependence on the fidelity parameter delta, which is much better than exponential scaling we usually see when dealing with noise. How does that compare to what you see in other papers?

Mira: It's significantly better because it shows that adaptivity maintains a polynomial scaling with respect to the desired accuracy, which is what we want when dealing with noisy experimental data. This contrasts sharply with non-adaptive single-copy methods which require exponential copies for fidelity above p two/three <ref:2610.02031#pg0>.

Kai: And then there's the testing aspect; they propose a three-step process: candidate generation from the tolerant learner, classical shadow estimation to filter states, and final validation on fresh copies. This leads to an optimal sample complexity of (n + epsilon two/(epsilon squared - epsilon one)) copies for distinguishing fidelity gaps F stab(rho) one - epsilon one from F stab(rho) one - epsilon two <ref:2610.02031#pg0>.

Lev: That final testing complexity seems very efficient, especially the term involving epsilon two/(epsilon squared - epsilon one), which suggests that the overhead for verification scales reasonably with our desired precision <ref:2610.02031#pg0>. How does this compare to what we're seeing in other papers?

Mira: It’s better than what non-adaptive methods require, which are exponential, and it achieves optimality when compared to Bell sampling without multi-copy measurements. This confirms their claim that adaptivity closes the gap in terms of optimal sample complexity scaling for verification tasks.

Kai: So the implication is that we can perform robust state estimation and verification using only single-copy measurements with a polynomial number of copies, which is a significant step forward for experimental quantum information science.

Conclusion: Mira: To wrap up this discussion on "Adaptivity is all you need: Optimal stabilizer learning using just single-copy measurements," the authors really argue that classical adaptivity closes the gap between two-copy Bell sampling and non-adaptive single-copy measurements for learning and testing.

Kai: They show that a polynomial-time adaptive algorithm can learn an arbitrary n-qubit stabilizer state from only (n) single-copy Clifford measurements. This is the central achievement here.

Lev: I think the key is realizing that we're using the sequential nature of measurement outcomes to guide a transformation toward a known computational basis state, which is really elegant in its resource management.

Mira: It’s not just elegant mathematics; it’s about practical resource efficiency, showing that classical feedback can be just as powerful as multi-copy access for this specific type of problem. It changes the way we approach fundamental quantum information problems.

Kai: We're looking at a future where state characterization doesn't necessarily require massive multi-copy resources, but rather smart, adaptive measurement sequences instead.

Lev: I just want to say that while the theoretical scaling is promising, we need to be very careful about how this translates into actual hardware protocols that can handle the required sequential operations without introducing too much noise.

Mira: That’s a fair caution; the paper lays out exactly what it does not do—it doesn't guarantee perfect resilience against all forms of decoherence in the physical implementation.

Kai: So, in conclusion, "Adaptivity is all you need: Optimal stabilizer learning using just single-copy measurements" provides a clear roadmap for resource-efficient state characterization using only single-copy measurements guided by adaptivity.

Lennart Bittel, *Jens Eisert, Weiyuan Gong, Antonio Anna Mele, Louis Schatzki

Dahlem Center for Complex Quantum Systems · Helmholtz-Zentrum Berlin f¨ur Materialien und Energie · John A. Paulson School of Engineering and Applied Sciences, Harvard University

quant-ph

Submitted: 2026-10-01

Updated: 2026-10-01

Comments: 17 pages

Code: https://github.com/AntMele/single-copy-stabilizer-learning-lean

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 92/100

The gist: Stabilizer states are central to quantum computing and error correction, but their learnability exhibits a gap where non-adaptive single-copy measurements require an exponential number of copies,

Key concepts

Stabilizer States
These are special quantum states that are fundamental in quantum computing and error correction. They have a specific mathematical structure that makes them easy to analyze and manipulate, which is why learning them is important for understanding quantum information.
Adaptive Algorithm
An adaptive algorithm means the next action taken depends on the results of previous measurements. In this context, it allows the algorithm to strategically choose which Clifford operation to apply next based on what it has already measured, enabling efficient state transformation.
Sample Complexity
This refers to the minimum number of copies or measurements needed from a quantum state to reliably estimate its properties, like learning its exact structure. The paper proves that adaptivity can reduce this required number significantly compared to non-adaptive methods.

Terminology

Summary

Stabilizer states are central to quantum computing and error correction, but their learnability exhibits a gap where non-adaptive single-copy measurements require an exponential number of copies, whereas adaptivity closes this gap. This work demonstrates that a polynomial-time adaptive algorithm can learn an arbitrary n-qubit stabilizer state from only Θ(n) single-copy Clifford measurements, matching the optimal sample complexity achieved by Bell sampling without requiring coherent access to multiple copies.

The gist

A polynomial-time adaptive algorithm learns an arbitrary n-qubit stabilizer state from Θ(n) single-copy Clifford measurements, matching the optimal sample complexity of Bell sampling without any multi-copy measurements.

How it works (Exact Learning)

The core idea is to construct a Clifford circuit C such that Cψ⟩ = z⟩, where ψ⟩ is the unknown stabilizer state and z⟩ is a computational-basis state. The algorithm aims to progressively convert non-diagonal stabilizers into Z-type stabilizers without destroying those already found.

  1. In each round, two copies of the current state are measured separately in the computational basis, and their bitwise difference, u = x + y, is calculated.

  2. If u is non-zero (i.e., not zero), an adaptive Clifford operation C ← FuC is applied to turn a non-diagonal stabilizer into a Z-type stabilizer while preserving previous ones.

  3. A local correction (Hi or HiSi) is chosen adaptively between the two options, conditioned on u being non-zero, which increases the dimension of the diagonal stabilizer subspace D(CψC†).

  4. This process repeats until the state is transformed into a computational-basis state, at which point it can be reconstructed.

How it works (Tolerant Learning and Testing)

The approach is extended to states close to a stabilizer, allowing for tolerant learning and testing.

  1. For learning, the protocol runs adaptive Clifford updates and saves one stabilizer candidate in every round, estimating their fidelities on fresh copies to return the best one. This yields an algorithm using O(Rµ(n, δ) +ξ−2 log(Rµ/δ)) copies for a fidelity above p2/3.

  2. For testing, a three-step process is used: candidate generation (from the tolerant learner), classical-shadow estimation to filter states, and final validation on fresh copies. This yields an optimal sample complexity of Θ(n + ε2/(ε2 − ε1)) copies for distinguishing fidelity gaps Fstab(ρ) ≥ 1 − ε1 from Fstab(ρ) ≤ 1 − ε2.

Learning States with Low Stabilizer Nullity

The adaptive mechanism is also effective when only a large Pauli stabilizer subspace remains, defined by the stabilizer nullity ν(ψ) = n - dim Lψ.

  1. When ν(ψ) ≤ r, the difference samples reveal a genuine stabilizer direction with probability 2−O(r), while existing diagonal stabilizers are preserved.

  2. The number of rounds required to reach a state where all Pauli stabilizers are Z-type is bounded by O(2rn + log 1/δ) with high probability.

  3. The remaining low-dimensional affine subspace is then learned using additional samples, leading to a total copy complexity of O(2r n + log 1/δ + 2rε2/r).

Memory-Assisted Testing

When k qubits of coherent memory are allowed, the optimal sample complexity for non-tolerant stabilizer testing is determined by the tradeoff between memory and samples.

  1. The optimal sample complexity is Θ(n − k + 1/ε), even with mixed inputs.

  2. The tester involves learning a Clifford circuit to unentangle the last m qubits from the first k, followed by a two-copy testing algorithm on the remaining k qubits.

  3. This structure allows for distinguishing Fstab(ρ) = 1 from Fstab(ρ) ≤ 1 − ε with O(m + 1/ε) copies, where m = n - k.

Conclusion and Implications

The paper establishes that classical adaptivity closes the quadratic gap between non-adaptive single-copy learning and two-copy Bell sampling. The results extend to tolerant settings, memory constraints, and states with low stabilizer nullity. The findings suggest that measurement outcomes can provide information about structural transformations that preserve existing structure while making monotone progress toward a known state. While the leading constant is larger than in some collective measurement schemes, the asymptotic scaling remains optimal for single-copy measurements.

Key Results Summary

  1. Exact learning of an n-qubit stabilizer state is achieved with N = O(n + log 1/δ) copies using adaptive single-copy measurements.

Improvements for AI systems

As a fastidious researcher, I have analyzed this paper, Adaptivity is all you need: Optimal stabilizer learning using just single-copy measurements. The core contribution is demonstrating that classical adaptivity closes the gap between optimal two-copy Bell sampling and non-adaptive single-copy measurements for learning and testing stabilizer states.

Here are the specific improvements to AI systems derived from this research:

)Adaptive Subroutine for State Identification (Core Improvement):

The fundamental improvement is a new, highly efficient learning subroutine that requires only a few (specifically, linear in the number of qubits) single-copy measurements. By adapting the measurement basis based on previous outcomes (using the computational difference sampling and subsequent Clifford updates), the system can progressively simplify an unknown quantum state into its computational basis form.

  1. From an unknown stabilizer state, it can be converted into a known computational-basis state with high probability in time polynomial in the number of qubits, using only single-copy measurements.

  2. This process preserves all previously identified diagonal stabilizers while sequentially identifying new ones, ensuring that the entire stabilizer structure is recovered efficiently.

)Specific Applications and Capabilities of the Improved AI System:

  1. From a raw quantum measurement output (representing an unknown state), the system can rapidly determine if that state is a pure stabilizer state or close to one (within a fidelity threshold).

  2. It can perform high-fidelity, single-copy stabilizer testing on mixed input states without needing coherent quantum memory, achieving optimal sample complexity scaling of O(n + 1/ε) copies.

  3. For general learning tasks involving structured quantum states (states with low stabilizer nullity, i.e., those prepared by circuits with few non-Clifford gates), the system can provide a classical description of the state within a guaranteed error bound, achieving a sample complexity scaling of O(n2r).

)System Enhancements Based on Specific Theorems:

  1. From its Tolerant Learning module, the AI system can perform robust state estimation. Given an unknown mixed quantum state, it can output the closest pure stabilizer state with high probability (fidelity above a threshold) using a sample complexity scaling of O(n + ε2/δ).

  2. It can distinguish between two classes of states: stabilizer-like states (high fidelity to any stabilizer) and far-from-stabilizer states, with the optimal sample complexity scaling as O(n + ε2/(ε2 - ε1)). This is crucial for classifying unknown quantum data efficiently.

  3. It can perform optimal quantum verification/certification by identifying whether an unknown state is a perfect stabilizer state or deviates from it within a specified error tolerance, using only single-copy measurements.

)Overall Impact on AI Development:

The improved AI system shifts the paradigm of quantum state characterization from requiring expensive, multi-copy coherent access to requiring only classical feedback and sequential single-copy measurements. This makes quantum machine learning and verification protocols significantly more resource-efficient for real-world experimental setups where coherent memory is limited.

Abstract

Stabilizer states are central to quantum computing, underlying quantum error correction, benchmarking, and efficient classical simulation. Yet their learnability exhibits a striking gap: an n-qubit stabilizer state can be learned from Θ(n) copies using two-copy Bell measurements, whereas non-adaptive single-copy measurements require Ω(n 2) copies. Here we show that adaptivity completely closes this gap. We give a polynomial-time adaptive algorithm that learns an arbitrary n-qubit stabilizer state from Θ(n) single-copy Clifford measurements, matching the optimal sample complexity of Bell sampling without any multi-copy measurements. The same ideas yield a sample-optimal single-copy tolerant tester and, with k qubits of quantum memory, the optimal testing tradeoff Θ(n-k+1/epsilon) at infidelity epsilon. Finally, we show that this adaptive mechanism extends beyond exact stabilizer states: states of stabilizer nullity at most r, including states prepared by Clifford circuits with a bounded number of T gates, can be learned using O(n2 r) single-copy measurements.

Sources

Related papers