Exponential Separations Between Learning With and Without Quantum Memory

on YouTube ↗39m

" summary

Claims an exponential gap between protocols that can store quantum states and those limited to classical memory, supported by a new learning tree framework and Haar-integral bounds. Concrete results: a purity test needs only O(1) queries with quantum memory (swap test) but Θ(2^{n/2}) copies with classical memory; a Pauli state-property tester uses O(n) queries versus ~2^n classically; shadow tomography lower bound scales like min(M,2^n)/ε^2 classically; a bounded quantum memory trade-off forces exponentially many copies in the gap N−K.

AI-written summary · about

" chapters (15)

1. 0:00Introduction
2. 0:18What are experiments
3. 1:06Recent perspectives
4. 2:19The power of quantum memory
5. 3:22Protocols with a classical memory
6. 6:32Goal
7. 7:39Recent work
8. 13:46Notation
9. 15:51Purity testing
10. 17:46Lower bound for purity
11. 22:00New results
12. 24:40Quantum channels
13. 26:24Symmetry distinction
14. 28:01Bounded quantum memory
15. 31:36Shadow tomography