# Quantum Speed-ups for Semidefinite Programming

arXiv: https://arxiv.org/abs/1609.05537 · HTML: https://mlsanity.com/paper/1609.05537/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Sep 2016.

## Built on by (most cited first, 6 of 6)

- [Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Bandits](https://mlsanity.com/paper/2209.12897/) (2022)
- [On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks](https://mlsanity.com/paper/2209.14501/) (2022)
- [Quantum Algorithms and Lower Bounds for Finite-Sum Optimization](https://mlsanity.com/paper/2406.03006/) (2024)
- [Meta-learning of Gibbs states for many-body Hamiltonians with applications to Quantum Boltzmann Machines](https://mlsanity.com/paper/2507.16373/) (2025)
- [Payoff-based learning with matrix multiplicative weights in quantum games](https://mlsanity.com/paper/2311.02423/) (2023)
- [Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexities](https://mlsanity.com/paper/2507.04438/) (2025)

## Abstract (arXiv)

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