



@article {2207,
	title = {Quantum algorithms and lower bounds for convex optimization},
	journal = {Quantum},
	volume = {4},
	year = {2020},
	month = {12/18/2019},
	abstract = {<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>},
	doi = {https://doi.org/10.22331/q-2020-01-13-221},
	url = {https://arxiv.org/abs/1809.01731},
	author = {Shouvanik Chakrabarti and Andrew M. Childs and Tongyang Li and Xiaodi Wu}
}
