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

In the paper's words

Stabilizer states underpin quantum error correction, device benchmarking, and the classical simulation of quantum circuits, yet their learnability shows a sample-complexity gap: an n-qubit stabilizer state can be identified from Θ(n) copies using joint two-copy Bell measurements, while non-adaptive single-copy measurements provably require Ω(n²) copies. The specific gap addressed here is explanatory: the recent proof that adaptivity alone closes this gap has not been accompanied by an explicit numerical account of how large the separation is at concrete system sizes, which assumptions the numbers rest on, and where the result could fail. We reconstruct the information-theoretic skeleton of the result with all arithmetic shown.

The abstract, verbatim, and its opening sentence is the claim. Every line below is quoted from the text.

Numbers it reports

1. The count of Lagrangians is the product of these step counts divided by the $n!$ orderings of a basis: $$L_{n}=\frac{1}{n!}\prod_{i=1}^{n}\frac{2^{2n-2(i-1)}-2^{i-1}}{2}.$$ Re-indexing with $j=n-i+1$ so that $2^{2n-2(i-1)}=2^{2j}$ and $2^{i-1}=2^{n-j}$, the product becomes $\prod_{j=1}^{n}(2^{2j}-2^{n-j})/2$, and the standard closed form for the number of Lagrangian subspaces of a $2n$-dimensional symplectic space over $\mathbb{F}_{2}$ is $$L_{n}=\prod_{i=1}^{n}\left(2^{i}+1\right).$$ Step 2: from Lagrangians to states.

   from 4.1 Counting stabilizer states

2. We derive the hypothesis-class size $N_{n}=2^{n}\prod_{i=1}^{n}(2^{i}+1)$, giving $\log_{2}N_{n}=n^{2}/2+3n/2+O(1)$ and $N_{100}\approx 2^{5150}$; an information-theoretic floor of $52$ copies at $n=100$ for any single-copy learner; the memory-versus-samples tradeoff $\Theta(n-k+1/\varepsilon)$ with the instance $\Theta(190)$ at $(n,k,\varepsilon)=(100,10,0.01)$; and the nullity extension $O(n\,2^{r})$, giving $3200$ copies at $(n,r)=(100,5)$.

   from Abstract

3. Under stated constant assumptions, a workload of $1000$ characterizations at $n=100$ needs $5.0\times 10^{5}$ adaptive versus $1.0\times 10^{8}$ non-adaptive measurements, a factor of $200$.

   from Abstract

4. At $n=100$ the adaptive requirement lies between the derived floor of $52$ copies and the projection $C_{\mathrm{ad}}\cdot 100$, while the non-adaptive requirement is at least $c\cdot 10^{4}$ copies under the projection $c=1$ (Section 4.2) — a separation that decides whether state identification is a routine calibration step or an experiment in its own right.

   from 1. Introduction

5. An information-theoretic copy floor of $52$ copies at $n=100$ for any single-copy learner, with the adaptive and non-adaptive regimes placed against it, and a separation factor of $10$–$100$ under stated constant assumptions (Section 4.2).

   from 1. Introduction

6. A labeled workload-level projection comparing adaptive and non-adaptive measurement budgets, with stated constant assumptions and an uncertainty range of a factor $10$ to $1000$ (Section 4.5).

   from 1. Introduction

How it is done

1. The specific gap addressed here is explanatory: the recent proof that adaptivity alone closes this gap has not been accompanied by an explicit numerical account of how large the separation is at concrete system sizes, which assumptions the numbers rest on, and where the result could fail.

   from Abstract

2. Stabilizer states are the simultaneous eigenstates of a maximal abelian subgroup of the $n$-qubit Pauli group; they are 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 [1].

   from 1. Introduction

3. Reference [1] establishes that adaptive single-copy Clifford measurements achieve $\Theta(n)$ sample complexity for exact stabilizer state learning, closing the gap between the $\Theta(n)$ two-copy Bell-measurement bound and the $\Omega(n^{2})$ non-adaptive single-copy lower bound.

   from 2. Background and Related Work

4. Our method is analytical reconstruction with explicit arithmetic.

   from 3. Methods

What would falsify it

1. The account clarifies which experimental designs the result changes and what would falsify it.

   from Abstract

2. We reconstruct the information-theoretic skeleton of the result with every arithmetic step explicit, compute concrete numerical instances, derive the memory tradeoff and nullity extensions from stated assumptions, and critically assess scope, limitations, and falsifiability.

   from 1. Introduction

3. Failure modes and falsification.

   from 6. Discussion

Where the claim stops

1. The numerical instances rest on asymptotic bounds whose constants are not extracted in the cited texts; the values $C_{\mathrm{ad}}=5$ and $c_{\mathrm{na}}=10$ in Section 4.5 are assumptions, not measurements, and every workload figure is a projection.

   from 6. Discussion

2. All bounds assume ideal noiseless single-copy Clifford measurements; depolarizing noise effectively caps the achievable stabilizer fidelity and converts exact identification into the tolerant-testing regime at $\varepsilon=O(p)$ for noise rate $p$, a conversion whose constants we have not derived.

   from 6. Discussion

3. Direction (i) is closed by the same work's statement of the $\Omega(n^{2})$ non-adaptive lower bound, but our per-copy bit reconstruction in Section 4.2 is the weakest link in the account: it assumes a fixed basis aligns with an unidentified generator only with $n$-independent probability.

   from 6. Discussion

Where to read

1. Abstract185 words · 1 min
2. 1. Introduction555 words · 2 min
3. 2. Background and Related Work1,215 words · 5 min
4. 3. Methods413 words · 2 min
5. 4. Analysis1,227 words · 5 min
6. 5. Results204 words · 1 min
7. 6. Discussion773 words · 3 min
8. 7. Practical Implications and Engineering Pathways670 words · 3 min
9. 8. Conclusion172 words · 1 min
10. Provenance and AI Involvement225 words · 1 min