  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.
