  We consider the problem of minimizing a continuous function given quantum
access to 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. 2022 and provide a general
quantum-variance reduction technique of independent interest.
