mlsanityData to 7 Oct 2026

Quantum algorithms and lower bounds for convex optimization

arXiv 1809.01731 ↗First posted 4 Sep 2018quant-ph cs.DS math.OCcited by 15

Not on the map. Why?

Abstract (arXiv)

While recent work suggests that quantum computers can speed up the solution of semidefinite programs, little is known about the quantum complexity of more general convex optimization. We present a quantum algorithm that can optimize a convex function over an n-dimensional convex body using tildeO(n) queries to oracles that evaluate the objective function and determine membership in the convex body. This represents a quadratic improvement over the best-known classical algorithm. We also study limitations on the power of quantum computers for general convex optimization, showing that it requires tildeOmega(√ n) evaluation queries and Omega(√n) membership queries.

Key facts. Cited by 15 papers in the map (data through 7 Oct 2026). First posted on arXiv 4 Sep 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 3; 2023: 1; 2024: 2; 2025: 4; 2026: 2.

15 papers.

Sort:

  1. 2021Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraintscited by 11
  2. 2022Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Banditscited by 11
  3. 2022On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walkscited by 9
  4. 2022Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constantscited by 8
  5. 2023Quantum Langevin Dynamics for Optimizationcited by 7
  6. 2021Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothnesscited by 6
  7. 2021Noisy intermediate-scale quantum algorithm for semidefinite programmingcited by 5
  8. 2024Quantum Algorithms and Lower Bounds for Finite-Sum Optimizationcited by 3
  9. 2025Quantum Non-Linear Bandit Optimizationcited by 2
  10. 2025Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexitiescited by 2
  11. 2025Quantum Speedups for Sampling and Non-convex Optimization with Stochastic Oraclescited by 1
  12. 2026Sublinear Time Quantum Algorithm for Attention Approximationcited by 1
3 more
  1. 2024Gradient Testing and Estimation by Comparisonscited by 0
  2. 2025Quantum Algorithms for Projection-Free Sparse Convex Optimizationcited by 0
  3. 2026A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Modelcited by 0