



01173nas a2200157   4500008004100000245006400041210006400105260001500169490000600184520070600190100002700896700002300923700001700946700001500963856003700978       2020                        eng d00aQuantum algorithms and lower bounds for convex optimization0 aQuantum algorithms and lower bounds for convex optimization  c12/18/20190 v43 a<p>While recent work suggests that quantum computers can speed up the solution of semidefinite programs, little is known about the quantum complexity of more general convex optimization. We present a quantum algorithm that can optimize a convex function over an n-dimensional convex body using O~(n) queries to oracles that evaluate the objective function and determine membership in the convex body. This represents a quadratic improvement over the best-known classical algorithm. We also study limitations on the power of quantum computers for general convex optimization, showing that it requires Ω~(n&minus;&minus;&radic;) evaluation queries and Ω(n&minus;&minus;&radic;) membership queries.</p>1 aChakrabarti, Shouvanik1 aChilds, Andrew, M.1 aLi, Tongyang1 aWu, Xiaodi  uhttps://arxiv.org/abs/1809.01731