Quantum algorithms and lower bounds for convex optimization
Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, Xiaodi Wu
Abstract
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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi></mml:math>-dimensional convex body using <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mover><mml:mi>O</mml:mi><mml:mo stretchy="false">~</mml:mo></mml:mover></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:math> 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mover><mml:mi mathvariant="normal">Ω</mml:mi><mml:mo stretchy="false">~</mml:mo></mml:mover></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:msqrt><mml:mi>n</mml:mi></mml:msqrt><mml:mo stretchy="false">)</mml:mo></mml:math> evaluation queries and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="normal">Ω</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msqrt><mml:mi>n</mml:mi></mml:msqrt><mml:mo stretchy="false">)</mml:mo></mml:math> membership queries.