Skip to yearly menu bar Skip to main content


Quantum speedups for stochastic optimization

Aaron Sidford · Chenyi Zhang

Great Hall & Hall B1+B2 (level 1) #1207
[ ]
Wed 13 Dec 8:45 a.m. PST — 10:45 a.m. PST


We consider the problem of minimizing a continuous function given given access to a natural quantum generalization of a stochastic gradient oracle. We provide two new methods for the special case of minimizing a Lipschitz convex function. Each method obtains a dimension versus accuracy trade-off which is provably unachievable classically and we prove that one method is asymptotically optimal in low-dimensional settings. Additionally, we provide quantum algorithms for computing a critical point of a smooth non-convex function at rates not known to be achievable classically. To obtain these results we build upon the quantum multivariate mean estimation result of Cornelissen et al. and provide a general quantum variance reduction technique of independent interest.

Chat is not available.