.png){kind=icon}
.png){kind=icon}
Return
Quantum algorithms and lower bounds for convex optimization
.png){kind=icon}
OA
AI
DOI：10.22331/q-2020-01-13-221.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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) over tilde (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 (Omega) over tilde(root n) evaluation queries and Omega(root n) membership queries.