Local Minima in Quantum Systems
summary
Defines local minima with inverse‑polynomial epsilon under two perturbation families: local unitary perturbations (where typical random states sit on barren plateaus so the problem is BPP‑easy) and physically motivated thermal Lindbladian jump operators that pick downward Bohr‑frequency transitions. Proves a quantum algorithm — a thermal gradient descent algorithm using simulating thermal dynamics — always finds an approximate local minimum efficiently. Constructs modified 2D circuit Hamiltonians (Kitaev style) with a Bohr‑frequency gap so every thermal local minimum is global, yielding classical hardness unless BQP ⊆ BPP.
AI-written summary · about
chapters (9)
- 0:00Local minima in quantum systems
- 2:10Motivation and definition
- 12:17Two perturbation classes
- 19:38Complexity for unitary perturbations
- 21:45Quantum advantage for thermal perturbations
- 24:54Classical hardness for thermal perturbations
- 36:21Proof idea for energy landscape
- 43:51Quantum advantage at low temperatures
- 44:13Open problems
related talks
44mOptimal Learning of Quantum Hamiltonians From High-Temperature Gibbs States
56mRapid quantum ground state preparation via dissipative dynamics
01h 08mFast mixing of all-to-all quantum systems at high temperatures
01h 15mDissipative State Preparation and the Dissipative Quantum Eigensolver
16mRobust Quantum Entanglement at (nearly) Room Temperature
43mEfficient Quantum Algorithm for Heisenberg Spin Systems
30mQuantum Thermal Simulation
36mA Combinatorial Approach to Complexity Transitions in Quantum Physics