Adaptivity Closes the Stabilizer Learning Gap: An Analytical Account of Optimal Single-Copy Stabilizer State Learning

#1. Introduction

A central question in quantum state learning is how many copies of an unknown state are needed to identify it, and what measurement structures achieve the optimum. For general $n$-qubit states, tomography requires exponentially many copies, but structured families — matrix product states, stabilizer states, low-magic states — admit far more efficient procedures. Stabilizer states, the simultaneous eigenstates of a maximal abelian subgroup of the $n$-qubit Pauli group, are the most important such family: they are exactly the states producible by Clifford circuits, they define the code spaces of stabilizer quantum error-correcting codes, and they are efficiently classically simulable via the Gottesman–Knill theorem.

For stabilizer states specifically, the learnability landscape before the work analyzed here was sharply divided. With access to two copies at a time and the ability to perform Bell measurements across copy pairs, $\Theta(n)$ copies suffice: Bell sampling reveals, per shot, a uniformly random stabilizer generator of the unknown state, and $O(n)$ generators pin the state down. Without joint measurements, and with measurement choices fixed in advance (non-adaptive), the best known upper bounds and matching lower bounds sit at $\Omega(n^2)$ copies [6]. This raised a natural question: is the quadratic overhead an intrinsic price of giving up joint measurements, or an artifact of non-adaptive strategies?

The result of [1],[2] answers this decisively: adaptivity is all you need. A polynomial-time adaptive algorithm using only single-copy Clifford measurements learns an arbitrary $n$-qubit stabilizer state from $\Theta(n)$ copies — matching the optimal Bell-sampling sample complexity with no multi-copy operations at all. The same machinery yields a sample-optimal single-copy tolerant tester (deciding whether a state is a stabilizer state or $\varepsilon$-far in infidelity), and, when the learner holds $k$ qubits of quantum memory between rounds, the optimal tradeoff $\Theta(n - k + 1/\varepsilon)$. Beyond exact stabilizer states, states of stabilizer nullity at most $r$ — including magic-state-injected states from Clifford circuits with at most $r$ $T$ gates — are learnable with $O(n\,2^r)$ single-copy measurements.

This paper's contribution is analytical and expository-derivative rather than a claim of new theorems. We reconstruct the information-theoretic skeleton of the result with all arithmetic explicit, compute concrete numerical instances that make the separation vivid, derive the memory tradeoff and nullity extensions from stated assumptions, and critically assess the result's scope, limitations, and falsifiability. We also connect the adaptivity principle to structurally analogous phenomena in machine learning, where adaptive (active) information acquisition provably beats fixed schedules [3],[5], and to single-copy estimation frameworks that are inherently non-adaptive and therefore subject to the quadratic penalty [7].

#2. Background and Related Work

The target result. Reference [1] (identical content under identifier [2]) establishes that adaptive single-copy Clifford measurements achieve $\Theta(n)$ sample complexity for exact stabilizer state learning, closing the gap between the $\Theta(n)$ Bell-measurement bound and the $\Omega(n^2)$ non-adaptive single-copy lower bound. It further gives a tolerant tester with the optimal memory tradeoff $\Theta(n - k + 1/\varepsilon)$ and an $O(n\,2^r)$ learner for states of stabilizer nullity at most $r$. Our entire analysis is grounded in this work.

Non-adaptive lower bounds. Reference [6] studies tomography and shadow tomography with single-copy measurements chosen independently of prior outcomes, sharpening a lower bound of Haah et al. (2017) on trace-distance-accurate tomography. The techniques there — building on information-theoretic packing arguments over hypothesis classes — are precisely what yield the $\Omega(n^2)$ bound for non-adaptive stabilizer learning, and understanding them is essential to seeing why adaptivity, not joint measurement, is the operative resource. Our Section 4 reconstructs the counting logic underlying such bounds.

Average-case single-copy learning. Reference [4] studies the complementary question of identifying a stabilizer group of codimension $n - t$ (i.e., a stabilizer state with $t$ "free" directions) from single copies, showing that for almost all stabilizer groups with $t = O(\log n)$, logarithmic-depth local Clifford measurement circuits suffice, improving on the linear-depth measurements previously required. This average-case result is orthogonal to but consistent with [1]: the worst case still demands the full adaptive machinery, while typical instances are structurally easier.

Non-adaptive group-structured estimation. Reference [7] extends the classical algebraic diversity framework to quantum measurement: a group-structured POVM applied to a single copy yields a full-rank, group-averaged density-matrix estimator whose eigenstructure tracks the true state's. This provides a systematic non-adaptive single-copy estimation methodology — and hence a concrete instantiation of the class of strategies that incur the $\Omega(n^2)$ penalty for stabilizer learning. The contrast with [1] is instructive: group structure organizes information but cannot, by itself, condition future measurements on past outcomes.

Adaptivity in meta-learning. Reference [3] (Alpha MAML) addresses model-agnostic meta-learning, where a model is primed across tasks for few-shot adaptation, with the goal of reducing costly hyperparameter tuning. The structural analogy is direct: meta-learning is adaptivity at the task level, and its success rests on the same principle that a learner primed by past outcomes needs fewer new samples. We use this analogy in Section 6 to argue that the adaptivity advantage of [1] is an instance of a general phenomenon, not a quirk of stabilizer structure.

Adaptive stopping. Reference [5] surveys stopping methods in active learning and proposes stopping when predictions stabilize, emphasizing wide applicability and annotation savings. Active learning is the classical prototype of adaptive sample acquisition: query choices depend on accumulated labels. The stabilizer learner of [1] is, in this sense, an active learner over Pauli-basis queries, and stabilization-based stopping heuristics of [5] suggest practical halting criteria for implementations.

Stabilization in value-based learning. Reference [8] stabilizes extreme Q-learning via a Maclaurin expansion of the in-sample value objective, controlling out-of-distribution evaluation error in offline reinforcement learning. Though distant in subject matter, it shares the theme that naive greedy information use destabilizes learning, and principled restructuring of the update restores stability — echoing how naive non-adaptive measurement schedules waste information in quantum learning.

Adaptive control with models. Reference [9] develops coprocessor actor-critic, a model-based RL approach for adaptive brain stimulation, where per-patient heterogeneity demands individually adapted policies. Again the analogy is structural: closed-loop adaptation outperforms open-loop schedules when the system under study is heterogeneous — exactly the worst-case-versus-average-case distinction between [1] and [4].

Workload-level reuse in simulation. Reference [11] analyzes workload-level reuse planning for quantum circuit simulation (QuWARP), observing that modern simulation appears as repeated-run workloads — VQE sweeps, noisy multishot studies, QEC cycles — rather than isolated executions. Learning stabilizer structure of prepared states is a natural sub-routine inside such workloads; amortizing an $O(n)$-copy adaptive learner across a workload, versus an $O(n^2)$-copy non-adaptive one, changes the classical-simulation cost model materially. We quantify this in Section 4.

Structural-program context. Reference [13] proposes that seven research domains share one structural object — nested hierarchical partition logic, with the hierarchy as invariant — and lists falsifiable hypotheses including a compression prior. Stabilizer groups are precisely nested hierarchical partitions of the Pauli group (generators at the top, derived stabilizers below), so stabilizer learning can be read as recovering a hierarchical partition from measurements; we note this reading in Section 6 as a interpretive framing, not a theorem. References [10] and [12] are project-level records without technical content relevant to our derivations; we acknowledge them as corpus context only.

#3. Methods

Our method is analytical reconstruction with explicit arithmetic. We fix notation and state the three quantitative claims we will derive.

Notation. Let $n$ denote the number of qubits. A stabilizer state $|\psi_S\rangle$ is specified by a maximal abelian subgroup $S \subset \mathcal{P}_n$ of the $n$-qubit Pauli group (modulo phases), with $|S| = 2^n$ and $n$ independent generators. Stabilizer nullity $\mathrm{Nul}(\rho) = n - \dim(S_\rho)$, where $S_\rho$ is the stabilizer group of $\rho$; nullity $r$ states include Clifford+$T$ outputs with at most $r$ $T$ gates. Infidelity $\varepsilon = 1 - F$ with $F = |\langle \psi_S | \phi \rangle|^2$. Quantum memory of $k$ qubits means the learner may store $k$ qubits between measurement rounds.

Claim A (hypothesis-class size and non-adaptive lower bound). The number $N_n$ of $n$-qubit stabilizer states satisfies $N_n = 2^{\Theta(n^2)}$; each non-adaptive single-copy Clifford measurement yields at most $n + 1$ distinct outcomes (measurement of a Pauli operator with eigenvalues $\pm 1$ per generator, aggregated as at most $2^n$ outcomes but carrying at most $O(n)$ bits of usable stabilizer information per copy under the information-theoretic accounting of [6]); hence non-adaptive learning requires $\Omega(n^2)$ copies.

Claim B (adaptive upper bound). An adaptive strategy extracts $O(n)$ bits of stabilizer information per copy by choosing the measurement basis as a function of the transcript so far, achieving $\Theta(n)$ total copies, matching the lower bound $\Omega(n)$ from the class size.

Claim C (memory tradeoff and nullity extension). With $k$ qubits of memory, tolerant testing at infidelity $\varepsilon$ costs $\Theta(n - k + 1/\varepsilon)$ copies; nullity-$r$ states cost $O(n\,2^r)$ single-copy measurements.

We derive each claim's arithmetic in Section 4 and report only those numbers, plus clearly labeled projections, in Section 5.

#4. Analysis

#4.1 Counting stabilizer states

Every $n$-qubit stabilizer group is generated by choosing, sequentially, $n$ independent commuting Pauli operators. The number of Pauli operators on $n$ qubits (modulo phase) is $4^n$. The first generator can be any non-identity Pauli: $4^n - 1$ choices. The $j$-th generator must commute with all previous $j-1$ generators and be independent of them; the count of valid choices at step $j$ is $2^{n+j} - 2^j$ (standard symplectic-lattice counting: the centralizer of $j-1$ independent generators has $2^{n+j-1}$ elements, of which $2^{j-1}$ lie in the span, and we exclude phases, giving $(2^{n+j-1} - 2^{j-1})/1$ choices up to the conventional factor; the asymptotic product is what matters). The product telescopes to

and the standard sharp form is $N_n = 2^{n^2/2 + O(n)}$. We take the leading exponent:

Concrete instance, $n = 100$: $\log_2 N_{100} = \frac{100^2}{2} + O(100) = 5000 + O(100)$, so $N_{100} \approx 2^{5000}$ up to subexponential corrections. To identify one state among $N_n$ candidates, any strategy must acquire at least $\log_2 N_n$ bits of information, giving the information-theoretic floor

where $b_{\mathrm{copy}}$ is the usable bits per copy.

#4.2 Bits per copy: non-adaptive versus adaptive

A single-copy Clifford measurement is a full $n$-qubit computational-basis measurement in a Clifford-rotated basis. Its outcome is an $n$-bit string. However, for a stabilizer state, the outcome distribution is uniform over $2^n$ strings regardless of basis — the identity of the basis is where the stabilizer information lives. Under the non-adaptive accounting of [6], with measurement choices fixed in advance, each copy's outcome is a sample from a distribution determined by the unknown $S$; extracting one independent stabilizer generator reliably requires distinguishing among $O(n)$ candidate generator directions per qubit-row, and the per-copy usable information is $b_{\mathrm{copy}}^{\mathrm{na}} = O(n)$ bits — at most the $n$ raw bits, and in the worst case only a constant number of new bits after redundancy across fixed bases is accounted for. Taking the generous bound $b_{\mathrm{copy}}^{\mathrm{na}} = n$:

The sharper argument: a fixed basis reveals a generator of $S$ only if $S$ contains a Pauli with support aligned to that basis's measurement axes. A random stabilizer state has, for each fixed basis, probability $\approx 2^{-n}$ that the basis is "compatible" in the sense of yielding a full generator set; hence each non-adaptive copy yields $O(1)$ aligned bits in the worst case over states, and covering all $n$ generator directions requires sweeping $\Theta(n)$ basis families each with $\Theta(n)$ repetitions:

Numerical instance, $n = 100$ (projection): the $\Omega(n^2)$ bound of [6] gives $m_{\mathrm{na}}^{\mathrm{tight}}(100) = c \cdot 100^2 = 10^4 c$ copies for an unspecified constant $c \gt 0$ fixed by the packing proof of [6]; since that constant is not extracted in [6], we report $m_{\mathrm{na}}^{\mathrm{tight}}(100) \geq 10^4$ copies only as an assumption-bounded projection under the explicit assumption $c \geq 1$, with the full range $m_{\mathrm{na}}^{\mathrm{tight}}(100) \in [10^3,\, 10^5]$ if $c \in [0.1, 10]$.

By contrast, the adaptive strategy of [1] uses each copy's outcome to choose the next basis so that each copy certifies at least one new independent generator with constant probability. Extracting $n$ generators then needs

with the information floor $m_{\mathrm{floor}}(100) \geq \log_2 N_{100} / n = 5000/100 = 50$ copies (using $b_{\mathrm{copy}}^{\mathrm{ad}} = n$ usable bits per adaptive copy), and the upper bound $m_{\mathrm{ad}}(100) = C \cdot 100$ for the algorithm's constant $C$; the matching $\Theta$ asserts $C$ is itself $O(1)$-bounded relative to the floor, i.e., $m_{\mathrm{ad}}(100) \in [50, \, C\cdot 100]$ with $C$ a small constant. The gap factor at $n = 100$ is

i.e., at least a factor of $\sim 100$ and up to $\sim 1000$ if $C \approx 1$–$10$.

#4.3 The memory tradeoff $\Theta(n - k + 1/\varepsilon)$

For tolerant testing at infidelity $\varepsilon$: the learner must distinguish $|\psi_S\rangle$ from any state with fidelity at most $1 - \varepsilon$. Each stored qubit of quantum memory $k$ effectively substitutes for one "fresh" qubit's worth of stabilizer information the learner would otherwise extract by measurement, reducing the transcript length by $k$; the residual testing precision requires $1/\varepsilon$ copies to accumulate constant total-variation signal at distance $\varepsilon$ (Chernoff-style: after $t$ copies, the fidelity-estimation standard error scales as $\sim 1/\sqrt{t}$, so resolving $\varepsilon$ needs $t \gtrsim 1/\varepsilon^2$ for naive estimation but $1/\varepsilon$ with the amplitude-amplified tolerant test of [1], which attains the optimal rate). Thus

Numerical instance: $n = 100$, $k = 10$, $\varepsilon = 0.01$:

With $k = 0$: $\Theta(200)$; with $k = 100$ (full memory): $\Theta(1/\varepsilon) = \Theta(100)$. Each stored qubit saves exactly one copy, and the $\varepsilon$-term dominates once $\varepsilon \lt 1/n$: for $n = 100$, the crossover is $\varepsilon^* = 1/n = 0.01$ — precisely the instance above, where the two terms contribute equally ($90$ vs.\ $100$).

#4.4 Nullity-$r$ states

A state of nullity $r$ has a stabilizer group of dimension $n - r$; the residual $r$ "non-stabilizer" directions must be resolved by brute force over the $2^r$-sized effective local Hilbert-space structure of the magic sector. The algorithm of [1] spends $O(n)$ copies to learn the stabilizer part (as in Section 4.2) and $O(2^r)$ copies to resolve the nullity sector, giving

Numerical instances: $n = 100$, $r = 5$: $m_{\mathrm{null}} = O(100 \cdot 32) = O(3200)$ copies. $r = 10$: $O(100 \cdot 1024) = O(102{,}400)$ — already exceeding the non-adaptive exact-stabilizer cost scale $10^4$ at $n=100$, showing the method's sweet spot is small $r$ (consistent with the $T$-gate-bounded circuits of [1], where $r$ counts $T$ gates).

#4.5 Workload-level cost projection

Under the repeated-run workload framing of [11] (e.g., a QEC study with $W$ state-preparation instances to characterize), the total measurement budget scales as

Projection (labeled): assuming $C_{\mathrm{ad}} = 5$, $c_{\mathrm{na}} = 10$ (constants within the $\Theta$-bounds, not measured), $n = 100$, $W = 1000$:

Ratio: $M_{\mathrm{na}} / M_{\mathrm{ad}} = 1.0 \times 10^{8} / 5.0 \times 10^{5} = 200$. Uncertainty: the ratio scales as $(c_{\mathrm{na}}/C_{\mathrm{ad}})\cdot n$, so for $C_{\mathrm{ad}} \in [1,10]$, $c_{\mathrm{na}} \in [1,10]$, the ratio lies in $[10, 1000]$ at $n = 100$.

#5. Results

All numbers below are computed in Section 4 or explicitly labeled projections.

1. Hypothesis-class size. $\log_2 N_n = n^2/2 + O(n)$; at $n = 100$, $N_{100} \approx 2^{5000}$ (up to $2^{O(100)}$ corrections).

1. Non-adaptive cost. $m_{\mathrm{na}}^{\mathrm{tight}}(n) = \Theta(n^2)$ [6]; at $n = 100$, $10^4 c$ copies with unspecified constant $c \gt 0$; the figure $\geq 10^4$ is an assumption-bounded projection requiring $c \geq 1$ (§4.2).

1. Adaptive cost. $m_{\mathrm{ad}}(n) = \Theta(n)$ [1]; at $n = 100$, information floor $50$ copies, upper bound $C \cdot 100$ with small constant $C$.

1. Separation factor. At $n = 100$: $m_{\mathrm{na}}^{\mathrm{tight}}(100)/m_{\mathrm{ad}}(100) \geq 100c/C$, i.e., roughly $10$–$1000\times$ fewer copies adaptively under the assumed ranges $c \in [0.1, 10]$, $C \in [1, 10]$; asymptotically the separation is quadratic in $n$ up to the constant ratio $c/C$.

1. Memory tradeoff. $m_{\mathrm{test}}(n,k,\varepsilon) = \Theta(n - k + 1/\varepsilon)$; at $n=100$, $k=10$, $\varepsilon=0.01$: $\Theta(190)$ copies, with the $\varepsilon$-term and memory-savings term balanced at $\varepsilon^* = 1/n = 0.01$.

1. Nullity extension. $m_{\mathrm{null}}(n,r) = O(n\,2^r)$: $O(3200)$ copies at $(n,r) = (100,5)$; $O(102{,}400)$ at $(100,10)$.

1. Workload projection (labeled projection, assumptions in §4.5). For $W = 1000$ characterization runs at $n = 100$: $5.0 \times 10^{5}$ adaptive versus $1.0 \times 10^{8}$ non-adaptive measurements, ratio $200$, with stated-constant uncertainty range $[10, 1000]$.

#6. Discussion

Limitations. First, our numerical instances rely on asymptotic $\Theta$-bounds with unspecified constants; the values $C_{\mathrm{ad}} = 5$ and $c_{\mathrm{na}} = 10$ in §4.5 are assumptions, not measurements, and all workload figures are projections. Second, the algorithm of [1] is adaptive in a strong sense: each measurement basis depends on the full transcript, which in practice serializes the experiment and forbids the parallelization that non-adaptive schedules enjoy. If wall-clock time, not copy count, is the binding constraint, the $\Theta(n)$-copy adaptive learner may lose to a $\Theta(n^2)$-copy parallel non-adaptive one; the crossover depends on hardware latency ratios we have not measured. Third, the $\Omega(n^2)$ non-adaptive lower bound of [6] is worst-case; average-case instances are far easier [4], so for typical states from local Clifford circuits the adaptive advantage may be modest. Fourth, noise: all bounds assume ideal single-copy Clifford measurements; depolarizing noise at rate $p$ effectively caps the achievable fidelity and may break the exact-identification guarantee, converting the problem to the tolerant-testing regime at $\varepsilon \approx O(p)$.

Failure modes and falsification. The central claim — adaptivity closes the gap — would be falsified by (i) a non-adaptive single-copy algorithm achieving $o(n^2)$ copies, or (ii) a lower bound showing any adaptive single-copy strategy needs $\omega(n)$ copies. Claim (ii) is ruled out by [1] itself; claim (i) is ruled out for stabilizer states by the same information-theoretic accounting if the per-copy non-adaptive information is genuinely $O(1)$ aligned bits in the worst case — but our derivation of that per-copy bound (§4.2) is the weakest link: if a clever fixed basis family extracts $\Theta(n)$ usable bits per copy for every stabilizer state, the quadratic separation collapses. The group-structured POVM framework of [7], which produces full-rank single-copy estimators, is the natural place to look for such a family; we consider demonstrating or refuting this an open problem.

Arguing against ourselves. One may object that the adaptivity analogy to classical ML [3],[5],[8],[9] is superficial: those settings involve statistical generalization, whereas stabilizer learning is exact identification of a combinatorial object. The analogy is nonetheless load-bearing for one claim — that adaptive advantage is generic rather than stabilizer-specific — and that claim is interpretive, not proven here. Similarly, the ultrametric/hierarchical reading via [13] is a framing device; stabilizer lattices are modular lattices, not ultrametric hierarchies, and we do not claim the correspondence is exact.

#References

[1] TITLE: arXiv Query: search_query=&id_list=2610.02031&start=0&max_results=1 [2] Adaptivity is all you need: Optimal stabilizer learning using just single-copy measurements. arXiv:2610.02031v1. https://arxiv.org/abs/2610.02031v1 [3] Alpha MAML: Adaptive Model-Agnostic Meta-Learning. arXiv:1905.07435v1. https://arxiv.org/abs/1905.07435v1 [4] Single-copy stabilizer learning: average case and worst case. arXiv:2604.24099v1. https://arxiv.org/abs/2604.24099v1 [5] A Method for Stopping Active Learning Based on Stabilizing Predictions and the Need for User-Adjustable Stopping. arXiv:1409.5165v1. https://arxiv.org/abs/1409.5165v1 [6] Lower Bounds for Learning Quantum States with Single-Copy Measurements. arXiv:2207.14438v3. https://arxiv.org/abs/2207.14438v3 [7] Quantum Algebraic Diversity: Single-Copy Density Matrix Estimation via Group-Structured Measurements. arXiv:2604.03725v3. https://arxiv.org/abs/2604.03725v3 [8] Stabilizing Extreme Q-learning by Maclaurin Expansion. arXiv:2406.04896v2. https://arxiv.org/abs/2406.04896v2 [9] Coprocessor Actor Critic: A Model-Based Reinforcement Learning Approach For Adaptive Brain Stimulation. arXiv:2406.06714v2. https://arxiv.org/abs/2406.06714v2 [10] DOI 10.5281/zenodo.19479493. QNFO: Alpha Pi Project. [11] DOI 10.5281/zenodo.23133404. QNFO: QuWARP Reconciled: An Analytical Cost-Model Assessment of Workload-Level Reuse Planning for Quantum Circuit Simulation. [12] DOI 10.5281/zenodo.18033018. QNFO: Thermodynamics of Structural Persistence (Topological Memory). [13] DOI 10.5281/zenodo.22076816. QNFO: The Ultrametric Program: One Structural Object Across Seven Research Domains, and Its Falsifiable Tests.

#Appendix A

No substantive draft divergence affects the derivations: Sections 4 and 5 are consistent with the source results of [1] and [6] as reconstructed here. The only editorial divergence concerned the status of constant-dependent figures, resolved by labeling all values that depend on the unspecified lower-bound constant $c$ of [6] and the algorithmic constant $C$ of [1] as assumption-bounded projections (§4.2, §4.5, Results 2 and 4).