Quantum Speed-ups for Semidefinite Programming

Quantum Speed-ups for Semidefinite Programming

Fernando G.S.L. Brandao, Krysta Svore

We give a quantum algorithm for solving semidefinite programs (SDPs). It has worst-case running time n12m12s2poly(log(n),log(m),R,r,1/δ), with n and s the dimension and row-sparsity of the input matrices, respectively, m the number of constraints, δ the accuracy of the solution, and R,r a upper bounds on the size of the optimal primal and dual solutions. This gives a square-root unconditional speed-up over any classical method for solving SDPs both in n and m. We prove the algorithm cannot be substantially improved (in terms of n and m) giving a Ω(n12+m12) quantum lower bound for solving semidefinite programs with constant s,R,r and δ.
The quantum algorithm is constructed by a combination of quantum Gibbs sampling and the multiplicative weight method. In particular it is based on a classical algorithm of Arora and Kale for approximately solving SDPs. We present a modification of their algorithm to eliminate the need for solving an inner linear program which may be of independent interest.