Optimal Stabilizer Testing and Learning with Limited Quantum Memory
Abstract
We study stabilizer state testing and learning with limited coherent quantum memory. Here an algorithm sequentially receives copies of an unknown n-qubit state, but may keep only k qubits of coherent quantum memory between measurements. With unrestricted memory, seminal work of Gross, Nezami and Walter showed how to test n-qubit stabilizer states using $6$ copies, which is dimension independent, unlike the learning complexity of Θ(n). We show that this testing-vs-learning separation is lost under memory constraints. More concretely we show that (1) The sample complexity of testing stabilizer states in the k-qubit memory framework is Θ(n−k). Our upper bound goes via a novel connection to the hidden shift problem and the lower bound is proven using a novel approach to average case bounds on likelihood ratios via combinatorics of the stochastic orthogonal group. (2) The sample complexity of learning stabilizer states with k qubits of memory, in the non-adaptive framework, is Θ(n2/k). As a further application of our techniques, we prove an exponential lower bound for purity testing even when the memory may be left coherent throughout the protocol. Our main results identify coherent quantum memory as the resource enabling the usual separation between stabilizer testing and learning. In particular, even with k=0.99n qubits of memory, there is no constant-copy stabilizer tester; furthermore for k=cn qubits of memory (for 0< c < 1), stabilizer testing is as hard as learning, with both requiring Θ(n) copies.
Related
- Near-Optimal Learning of Quantum Many-Body Systems from Gibbs and Thermal Metastable States via the Stationarity Test
- Lifting an [n,k,d] Binary Linear Code to an $[[n,k,d]]$ Quantum Stabilizer Code
- Quantum XYZ Stabilizer Codes
- Optimal Support Size Testing
- PDE-Based Bounds on Optimal Exponents in Active Simple Hypothesis Testing
BibTeX
@misc{arunachalam2026optimal,
title = {{Optimal Stabilizer Testing and Learning with Limited Quantum Memory}},
author = {Srinivasan Arunachalam and Louis Schatzki},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2607.02444},
eprint = {2607.02444},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.02444},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Optimal Stabilizer Testing and Learning with Limited Quantum Memory
AU - Srinivasan Arunachalam
AU - Louis Schatzki
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2607.02444
UR - https://arxiv.org/abs/2607.02444
AB - We study stabilizer state testing and learning with limited coherent quantum memory. Here an algorithm sequentially receives copies of an unknown n-qubit state, but may keep only k qubits of coherent quantum memory between measurements. With unrestricted memory, seminal work of Gross, Nezami and Walter showed how to test n-qubit stabilizer states using $6$ copies, which is dimension independent, unlike the learning complexity of Θ(n). We show that this testing-vs-learning separation is lost under memory constraints. More concretely we show that (1) The sample complexity of testing stabilizer states in the k-qubit memory framework is Θ(n−k). Our upper bound goes via a novel connection to the hidden shift problem and the lower bound is proven using a novel approach to average case bounds on likelihood ratios via combinatorics of the stochastic orthogonal group. (2) The sample complexity of learning stabilizer states with k qubits of memory, in the non-adaptive framework, is Θ(n^2/k). As a further application of our techniques, we prove an exponential lower bound for purity testing even when the memory may be left coherent throughout the protocol. Our main results identify coherent quantum memory as the resource enabling the usual separation between stabilizer testing and learning. In particular, even with k=0.99n qubits of memory, there is no constant-copy stabilizer tester; furthermore for k=cn qubits of memory (for 0< c < 1), stabilizer testing is as hard as learning, with both requiring Θ(n) copies.
ER -