  We present a quantum interior point method with worst case running time
$\widetilde{O}(\frac{n^{2.5}}{\xi^{2}} \mu \kappa^3 \log (1/\epsilon))$ for
SDPs and $\widetilde{O}(\frac{n^{1.5}}{\xi^{2}} \mu \kappa^3 \log
(1/\epsilon))$ for LPs, where the output of our algorithm is a pair of matrices
$(S,Y)$ that are $\epsilon$-optimal $\xi$-approximate SDP solutions. The factor
$\mu$ is at most $\sqrt{2}n$ for SDPs and $\sqrt{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(n^{6})$ and $O(n^{3.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.
