We study to what extent quantum algorithms can speed up solving convex optimization problems. Following the classical literature we assume access to a convex set via various oracles, and we examine the efficiency of reductions between the different oracles. In particular, we show how a separation oracle can be implemented using $\stackrel{~}{O}\left(1\right)$ quantum queries to a membership oracle, which is an exponential quantum speed-up over the $\Omega \left(n\right)$ membership queries that are needed classically. We show that a quantum computer can very efficiently compute an approximate subgradient of a convex Lipschitz function. Combining this with a simplification of recent classical work of Lee, Sidford, and Vempala gives our efficient separation oracle. This in turn implies, via a known algorithm, that $\stackrel{~}{O}\left(n\right)$ quantum queries to a membership oracle suffice to implement an optimization oracle (the best known classical upper bound on the number of membership queries is quadratic). We also prove several lower bounds: $\Omega \left(\sqrt{n}\right)$ quantum separation (or membership) queries are needed for optimization if the algorithm knows an interior point of the convex set, and $\Omega \left(n\right)$ quantum separation (or membership) queries are needed for optimization if the algorithm knows an interior point of the convex set, and $\Omega \left(n\right)$ quantum separation queries are needed if it does not.
arXiv.org e-Print archive
Networks and Optimization

van Apeldoorn, J.T.S, Gilyén, A.P, Gribling, S.J, & de Wolf, R.M. (2018). Convex optimization using quantum oracles. arXiv.org e-Print archive.