Stabilizer state testing requires Θ(n-k) samples with limited quantum memory

Researchers analyze the sample complexity of testing and learning n-qubit stabilizer states when an algorithm is restricted to keeping only k qubits of coherent quantum memory between measurements. The study demonstrates that this memory constraint eliminates the separation between testing and learning that exists with unrestricted memory.

• Testing stabilizer states requires Θ(n-k) samples in the k-qubit memory framework.
• Learning stabilizer states in the non-adaptive framework requires Θ(n²/k) samples.
• An exponential lower bound is proven for purity testing even when memory remains coherent throughout the protocol.
• With k=cn qubits of memory (0<c<1), stabilizer testing becomes as hard as learning, both requiring Θ(n) copies.

The results identify coherent quantum memory as the critical resource enabling the usual separation between stabilizer testing and learning complexity.