Quantum Computational Advantage With Constant-Temperature Gibbs Sampling
summary
Claims a family of n‑qubit commuting parent Hamiltonians at log log n locality and a fixed inverse temperature whose Davies generator is provably rapid mixing via Log‑Sobolev, so thermalization time is polylogarithmic and a quantum computer prepares the Gibbs state in depth O(n · exp(locality)) — which for locality O(log log n) is O(n log n). Shows classical sampling is intractable by reducing to hardness of shallow IQP circuits and gives a fault‑tolerant embedding of shallow IQP using repetition‑tree gadgets and postprocessing to survive input depolarizing noise.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 0:27Thermalization
- 1:57Task
- 4:25Hamiltonians
- 7:53Outline
- 10:40Davies Generator
- 11:48Mixing Time
- 14:57Example
- 17:28Proof Sketch
- 25:07Main Result
- 27:05Fall Tolerance
- 32:35Future Directions
related talks
44mOptimal Learning of Quantum Hamiltonians From High-Temperature Gibbs States
01h 08mFast mixing of all-to-all quantum systems at high temperatures
16mRobust Quantum Entanglement at (nearly) Room Temperature
30mQuantum Thermal Simulation
01h 26mQuantum Gibbs Sampling
56mRapid quantum ground state preparation via dissipative dynamics
01h 07mClassical algorithms for quantum Gibbs states
01h 08mPutting Quantum Supremacy on a Rigorous Footing