TY - JOUR T1 - Quantum algorithms and lower bounds for convex optimization JF - Quantum Y1 - 2020 A1 - Shouvanik Chakrabarti A1 - Andrew M. Childs A1 - Tongyang Li A1 - Xiaodi Wu AB -

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−−√) evaluation queries and Ω(n−−√) membership queries.

VL - 4 UR - https://arxiv.org/abs/1809.01731 CP - 221 U5 - https://doi.org/10.22331/q-2020-01-13-221 ER -