Speaker
Description
We study stabilizer state testing and learning with limited coherent quantum memory. Here one 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 unlike the learning complexity of $\Theta(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 $\Theta(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 $\Theta(n^2/k)$. 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 and stabilizer testing is as hard as learning, with both requiring $\Theta(n)$ copies.
| Topic | Theoretical foundations of quantum learning |
|---|---|
| Additional Topic | Quantum state reconstruction from data |