Adaptivity is all you need: Optimal stabilizer learning using just single-copy measurements
L. Bittel, J. Eisert, W. Gong, A. A. Mele, L. Schatzki
quant-ph
Oct 1, 2026 · v1
TL;DR
The main theorems on adaptive single-copy stabilizer learning and testing were formally verified in Lean 4 using Mathlib.
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/\varepsilon)$ at infidelity $\varepsilon$. 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.
Problem
An n-qubit stabilizer state can be learned from Θ(n) copies with two-copy Bell measurements, but non-adaptive single-copy measurements need Ω(n^2) copies. The question is whether adaptive single-copy measurements can close this gap.
Approach
An adaptive algorithm builds a Clifford circuit, one round at a time, that maps the unknown stabilizer state to a computational-basis state. Each round uses differences of measurement outcomes to apply CNOT and local corrections. These grow the subspace of diagonal stabilizers and never shrink it. The analysis is extended with birth–death chain potentials to tolerant learning, tolerant testing, memory-assisted testing via partial Bell sampling, and states of low stabilizer nullity. The main theorems were formally verified in Lean 4 with Mathlib.
Results
Stabilizer states can be learned exactly in polynomial time from Θ(n) single-copy Clifford measurements. The work also gives a sample-optimal single-copy tolerant tester, an optimal Θ(n−k+1/ε) tester with k qubits of quantum memory, and an O(n2^r)-copy learner for states of stabilizer nullity at most r.
