Quantum Speed-ups for Semidefinite Programming

Abstract

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.

24 pages. v2: modification of input model 2 and minor revisions v3: several errors corrected, v4: more corrections and clarifications, v5: published version, Proceedings FOCS 2017

References in corpus (1)

• Hamiltonian Simulation with Optimal Sample Complexity

Cited by in corpus (10)

• Quantum Computing in the NISQ era and beyond
• Quantum machine learning: a classical perspective
• Biology and medicine in the landscape of quantum advantages
• Machine learning \& artificial intelligence in the quantum domain
• Quantum algorithms and lower bounds for convex optimization
• Quantum computing through the lens of control: A tutorial introduction
• Small quantum computers and large classical data sets
• Quantum Machine Learning and its Supremacy in High Energy Physics
• Improved Quantum Boosting
• Quantum Technology for Military Applications