Learning Beyond Stabilizer States
summary
Shows concrete algorithms and limits: outputs of Clifford+T circuits with n qubits and k T gates are learnable in poly(n) time with sample and runtime scaling like 2^k, and any state prepared with fewer than n T gates is distinguishable from Haar random. Key tools are Bell difference sampling to estimate the distribution p_psi over Pauli strings, a duality that concentrates mass on the commutant, and computing a Clifford that compresses nonstabilizerness to k qubits so tomography on those k qubits recovers the state.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 1:30Learning a Quantum State
- 5:00Clifford Group
- 6:40Stabilizer States
- 7:58Efficient Learning
- 18:27Stabilizer Fidelity
- 20:31Results
- 25:31Zen Outlook
- 30:11Observations
- 34:01Computational Efficiency
- 35:46Conclusion
- 54:16Summary
related talks
42mLearning Shallow Quantum Circuits and Quantum States Prepared by Shallow Circuits in Polynomial Time
22mLower Bounds on Stabilizer Rank
50mQuantum Benchmarking
20mLow-Stabilizer-Complexity Quantum States Are Not Pseudorandom
29mEfficiently Verifying Quantum Programs with Few T Gates
01h 10mLearning from Quantum Experiments
53mFundamental limits to quantum computation
42mQuantum Learning Algorithms Imply Circuit Lower Bounds