Quantum approach to classical optimization: why bother and what to do?
summary
Introduces Quantum Hamiltonian Descent (QHD) as a path‑integral quantization of gradient descent, implements it with Hamiltonian simulation and analog embedding, and proves polynomial‑time solution for a class of nonconvex continuous problems that have exponentially many local minima. Demonstrates improved numerical stability versus classical accelerated gradient dynamics, shows empirical separation on >20 test problems and solves 75-dimensional nonconvex quadratic programs on commercial analog hardware, and publishes the QHDopt library for reproduction.
AI-written summary · about
chapters (8)
- 0:00Quantum optimization intro
- 1:04Optimization math landscape
- 2:49Gradient descent quantum link
- 4:57Quantum heavy ball descent
- 7:22Quantum advantage non-convex
- 8:26Quantum algorithms hardware
- 10:10Future beyond optimization
- 11:39Q&A
related talks
27mA Haskell Adiabatic DSL: Solving Classical Optimization Problems on Quantum Hardware
44mNo Quantum Speedup Over Gradient Descent for Non-Smooth Convex Optimization
15mAccelerQ: Accelerating Quantum Eigensolvers With Machine Learning on Quantum Simulators
01h 04mConvex Optimization and Quantum Information
19mAn Industry Perspective on the Path Forward in Quantum Optimization
46mLocal Minima in Quantum Systems
20mQuantum Software: Taking Computational Fluid Dynamics as an Example
44mQuantum machine learning: Prospects and challenges