A Quantum Interior Point Method for LPs and SDPs

We present a quantum interior point method with worst case running time widetildeO(fracn2.5xi2 μ kappa3 log (1/ε)) for SDPs and widetildeO(fracn1.5xi2 μ kappa3 log (1/ε)) for LPs, where the output of our algorithm is a pair of matrices (S,Y) that are ε-optimal xi-approximate SDP solutions. The factor μ is at most √2n for SDPs and √2n for LP's, and kappa is an upper bound on the condition number of the intermediate solution matrices. For the case where the intermediate matrices for the interior point method are well conditioned, our method provides a polynomial speedup over the best known classical SDP solvers and interior point based LP solvers, which have a worst case running time of O(n6) and O(n3.5) respectively. Our results build upon recently developed techniques for quantum linear algebra and pave the way for the development of quantum algorithms for a variety of applications in optimization and machine learning.