No Quantum Speedup Over Gradient Descent for Non-Smooth Convex Optimization
summary
Claim: in the standard first-order black-box model for constrained non-smooth convex optimization, quantum algorithms need the same Theta((GR/ε)^2) oracle queries as classical gradient descent, so there is no asymptotic quantum speedup. The proof builds explicit hard function families (random orthonormal directions plus an index-dependent penalty), uses a quantum hybrid argument and reductions to subset-or queries, and succeeds in matching the classical lower bound; earlier special instances admit a Belovs sqrt(n) quantum speedup, but those do not generalize.
AI-written summary · about
chapters (10)
- 0:00Introduction
- 0:45Motivation
- 5:29Convex Optimization
- 8:44Formalizing the Problem
- 12:38Gradient Descent
- 16:18Formal Question
- 23:08No Quantum Speedup
- 29:33Questions
- 32:36Lower Bounds
- 37:36Optimal Algorithms
related talks
14mQuantum approach to classical optimization: why bother and what to do?
31mLimits of quantum speed-ups for computational geometry and other problems: Fine-grained complexity v
19mAn Industry Perspective on the Path Forward in Quantum Optimization
01h 04mConvex Optimization and Quantum Information
20mThe Quantum Supremacy Tsirelson Inequality
15mAccelerQ: Accelerating Quantum Eigensolvers With Machine Learning on Quantum Simulators
01h 09mRecent Progress in Quantum Advantage
44mQuantum machine learning: Prospects and challenges