No quantum speedup over gradient descent for non-smooth convex optimization
summary
Proves that quantum algorithms give no asymptotic advantage for non‑smooth 1‑Lipschitz convex optimization in high dimension by showing a matching 1/epsilon^2 lower bound on oracle queries, equal to projected subgradient descent. Construction: a rotated max‑of‑coordinates family with small gamma shifts that encodes either a bit string or K orthonormal vectors so any epsilon‑optimal point reveals the hidden data. Main techniques: a randomized information‑theoretic bound and a quantum hybrid argument over changed oracles applied to the rotated max‑of‑coordinates family.
AI-written summary · about
chapters (14)
- 0:00Introduction
- 0:18Gradient descent
- 1:37Quantum advantage
- 2:44convex optimization
- 4:37convexity
- 5:25algorithms
- 9:03lower bounds
- 12:56function class
- 13:44function comparison
- 14:36base function class
- 18:18hybrid argument
- 20:26limited information argument
- 21:14k1 queries
- 23:00Summary
related talks
46mSmooth Nonconvex Min-Max Optimization
46mCan Non-Convex Optimization be Robust?
42mGrover’s Quantum Search for Data Science and Why should we Care
57mComputationally Efficient Alternatives to Nonconvex-Nonconcave Min-Max Optimization
01h 07mOptimization Crash Course (continued)
01h 18mOptimization I
44mQuantum machine learning: Prospects and challenges
42mOptimization Crash Course