# No quantum speedup over gradient descent for non-smooth convex optimization

arXiv: https://arxiv.org/abs/2010.01801 · HTML: https://mlsanity.com/paper/2010.01801/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Oct 2020.

## Built on by (most cited first, 6 of 6)

- [Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints](https://mlsanity.com/paper/2110.13086/) (2021)
- [Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness](https://mlsanity.com/paper/2112.01118/) (2021)
- [Quark: A Gradient-Free Quantum Learning Framework for Classification Tasks](https://mlsanity.com/paper/2210.01311/) (2022)
- [Quantum Algorithms and Lower Bounds for Finite-Sum Optimization](https://mlsanity.com/paper/2406.03006/) (2024)
- [Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization](https://mlsanity.com/paper/2406.07373/) (2024)
- [Quantum Non-Linear Bandit Optimization](https://mlsanity.com/paper/2503.03023/) (2025)

## Abstract (arXiv)

We study the first-order convex optimization problem, where we have black-box access to a (not necessarily smooth) function f:ℝn → ℝ and its (sub)gradient. Our goal is to find an ε-approximate minimum of f starting from a point that is distance at most R from the true minimum. If f is G-Lipschitz, then the classic gradient descent algorithm solves this problem with O((GR/ε)2) queries. Importantly, the number of queries is independent of the dimension n and gradient descent is optimal in this regard: No deterministic or randomized algorithm can achieve better complexity that is still independent of the dimension n. In this paper we reprove the randomized lower bound of Omega((GR/ε)2) using a simpler argument than previous lower bounds. We then show that although the function family used in the lower bound is hard for randomized algorithms, it can be solved using O(GR/ε) quantum queries. We then show an improved lower bound against quantum algorithms using a different set of instances and establish our main result that in general even quantum algorithms need Omega((GR/ε)2) queries to solve the problem. Hence there is no quantum speedup over gradient descent for black-box first-order convex optimization without further assumptions on the function family.