Fundamental limits to quantum computation
Talkat Near-Term Quantum Computers: Fault Tolerance + Benchmarking + Quantum Advantage + Quantum Algorithms · 2024-04-22..04-26·
summary
Proves that a single T-gate renders learning hard for Born‑machine output distributions, gives concrete sample‑complexity lower bounds showing error mitigation needs about exp(Ω(n·d)) noisy copies (so scaling hits already at d ≈ log log n), and shows generic non‑unital noise truncates circuits so only a thin suffix matters — a noise‑induced shallow circuits picture — which removes barren plateaus but limits expressivity and enables efficient average‑case classical estimation of expectation values.
AI-written summary · about
chapters (16)
- 0:00Introduction and overview
- 1:20Quantum advantage in sampling
- 3:00Verification of quantum devices
- 10:51Data input in quantum ML
- 12:08Optimization and learned tasks
- 14:16Limitations of born machines
- 22:53Clifford circuit simulation
- 23:35Limitations of error mitigation
- 40:52The impact of noise types
- 41:46Summary of near-term prospects
- 41:57Analog quantum simulation
- 43:56Training variational circuits
- 44:42Final conclusions
- 46:34Question and answer session
- 49:00Specific algorithm constraints
- 49:26Final audience queries
related talks
50mQuantum Benchmarking
01h 08mPutting Quantum Supremacy on a Rigorous Footing
45mNoise vs Imprecision in the Hardness of Random Quantum Circuits
19mAvenues for Quantum Error Correction and Mitigation
33mA lower bound on the space overhead of fault-tolerant quantum computation
01h 01mWhat Is "Quantum" About Quantum Computing?
46mQuantum Learning Algorithms Imply Circuit Lower Bounds
42mQuantum Learning Algorithms Imply Circuit Lower Bounds