Quantum Algorithms for Non-smooth Non-convex Optimization

This paper considers the problem for finding the (\delta,\epsilon) -Goldstein stationary point of Lipschitz continuous objective, which is a rich function class to cover a great number of important applications. We construct a novel 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 \tilde{\mathcal{O}}(d {3/2}\delta {-1}\epsilon {-3}) on the stochastic function value oracle, where d is the dimension of the problem. 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 \epsilon by a factor of \epsilon {-2/3} .