# Quantum Algorithms for Non-smooth Non-convex Optimization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Oct 2024.

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

- [Quantum Non-Linear Bandit Optimization](https://mlsanity.com/paper/2503.03023/) (2025)
- [Quantum Speedups for Sampling and Non-convex Optimization with Stochastic Oracles](https://mlsanity.com/paper/2504.03626/) (2025)

## Abstract (arXiv)

This paper considers the problem for finding the (δ,ε)-Goldstein stationary point of Lipschitz continuous objective, which is a rich function class to cover a great number of important applications. We construct a zeroth-order quantum estimator for the gradient of the smoothed surrogate. Based on such estimator, we propose a novel quantum algorithm that achieves a query complexity of tildeO(d3/2δ-1ε-3) on the stochastic function value oracle, where d is the dimension of the problem. We also enhance the query complexity to tildeO(d3/2δ-1ε-7/3) by introducing a variance reduction variant. Our findings demonstrate the clear advantages of utilizing quantum techniques for non-convex non-smooth optimization, as they outperform the optimal classical methods on the dependency of ε by a factor of ε-2/3.