Quantum SDP-Solvers: Better upper and lower bounds
Joran van Apeldoorn, András Gilyén, Sander Gribling, Ronald de Wolf
Abstract
Brandão and Svore \cite{brandao2016QSDPSpeedup} recently gave quantum algorithms for approximately solving semidefinite programs, which in some regimes are faster than the best-possible classical algorithms in terms of the dimension <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi></mml:math> of the problem and the number <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>m</mml:mi></mml:math> of constraints, but worse in terms of various other parameters. In this paper we improve their algorithms in several ways, getting better dependence on those other parameters. To this end we develop new techniques for quantum algorithms, for instance a general way to efficiently implement smooth functions of sparse Hamiltonians, and a generalized minimum-finding procedure.We also show limits on this approach to quantum SDP-solvers, for instance for combinatorial optimization problems that have a lot of symmetry. Finally, we prove some general lower bounds showing that in the worst case, the complexity of every quantum LP-solver (and hence also SDP-solver) has to scale linearly with <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>m</mml:mi><mml:mi>n</mml:mi></mml:math> when <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>m</mml:mi><mml:mo>≈</mml:mo><mml:mi>n</mml:mi></mml:math>, which is the same as classical.