arXiv:2610.02031
Adaptivity is all you need: Optimal stabilizer learning using just single-copy measurements
L. Bittel, J. Eisert, W. Gong, A. A. Mele, L. Schatzki
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.
AI Summary
The paper asks whether adaptive single-copy measurements can learn stabilizer states as sample-efficiently as two-copy Bell measurements. Bell-based learning uses $\Theta(n)$ copies, whereas non-adaptive single-copy learning requires $\Omega(n^2)$. It gives a polynomial-time adaptive learner using $O(n+\log(1/\delta))$ copies at failure probability $\delta$, with $4n+O(\sqrt n)$ copies at fixed confidence. The learner measures pairs of copies separately after an accumulated Clifford transformation. Differences of computational-basis outcomes identify stabilizer $X$-components. Outcome-dependent CNOTs and a random local Clifford preserve all existing diagonal stabilizers and increase their dimension with constant probability. Geometric waiting-time bounds establish convergence to a computational-basis state, whose label completes reconstruction. Extensions include mixed-input single-copy stabilizer testing with optimal complexity $\Theta(n+1/\varepsilon)$, and testing with $k$ persistent quantum-memory qubits using the optimal $\Theta(n-k+1/\varepsilon)$ copies. Tolerant learning assumes stabilizer fidelity at least a fixed $f_0>\sqrt{2/3}$; candidate generation is analyzed through a birth–death chain and candidates are evaluated using Clifford classical shadows. In this regime, tolerant testing uses $O(n+\varepsilon_2/(\varepsilon_2-\varepsilon_1)^2)$ copies at constant confidence, with matching lower bounds for $\varepsilon_2\leq1/5$. For pure states of stabilizer nullity at most $r$, adaptive compression followed by residual tomography uses $O(2^r(n+\log(1/\delta))+2^r\varepsilon^{-2}(r+\log(1/\delta)))$ copies for trace-distance error $\varepsilon$. Here the overhead arises from collision probabilities among stabilizer cosets. Open questions include replacing the multiplicative $n2^r$ cost by additive dependence, improving the leading constant for exact learning, and removing the high-fidelity assumption for tolerant learning. Single-copy measurements may involve entangling Clifford operations within each copy.
Instead, it proposed the $\Theta(n)$ adaptive learning algorithm that, after verification and further development by the authors, forms the main result of this work.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 17 pages