We study stabilizer state testing and learning with limited coherent quantum memory. The algorithm sequentially receives copies of an unknown $n$-qubit state but can retain only $k$ qubits of coherent quantum memory between measurements. With unrestricted memory, seminal work by Gross, Nezami, and Walter demonstrated how to test $n$-qubit stabilizer states using $6$ copies, which is dimension-independent, unlike the learning complexity of $\Theta(n)$. We show that this testing-vs-learning separation is lost under memory constraints. Specifically, we show that:
-
The sample complexity of testing stabilizer states in the $k$-qubit memory framework is $\Theta(n-k)$. Our upper bound is derived through a novel connection to the hidden shift problem, while the lower bound is proven using a new approach to average case bounds on likelihood ratios via combinatorics of the stochastic orthogonal group.
-
The sample complexity of learning stabilizer states with $k$ qubits of memory in the non-adaptive framework is $\Theta(n^2/k)$. As a further application of our techniques, we prove an exponential lower bound for purity testing even when the memory may remain 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$), the situation remains the same.
Blogger's Review: This paper delves into the impact of quantum memory on stabilizer state testing and learning, revealing variations in sample complexity under coherent quantum memory constraints. It holds significant theoretical value and practical application potential. Compared to traditional methods, this research provides new insights for quantum information processing, making it worthy of attention.