Quantum Algorithms for Non-smooth Non-convex Optimization

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.