Quantum Speed-ups for Semidefinite Programming

We give a quantum algorithm for solving semidefinite programs (SDPs). It has worst-case running time \({n^}_{\frac{1/}{2 }}{m^}_{\frac{1/}{2 }}{s^}_{2 }\text{poly}(log(n),log(m),R,r,1/\delta )\) , with \(n\) and \(s\) the dimension and row-sparsity of the input matrices, respectively, \(m\) the number of constraints, \(\delta\) 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 \(\Omega ({n^}_{\frac{1/}{2}}+{m^}_{\frac{1/}{2}})\) quantum lower bound for solving semidefinite programs with constant \(s,R,r\) and \(\delta\) . 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.