Quantum Speed-Ups for Solving Semidefinite Programs
Abstract
We give a quantum algorithm for solving semidefinite programs (SDPs). It has worst-case running time n^(1/2) m^(1/2) s^2 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 upper bounds on the size of the optimal primal and dual solutions, respectively. 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 Ω(n^(1/2) + m^2) 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.
Additional Information
© 2017 IEEE. We thank Joran van Apeldoorn, Ronald de Wolf, Andras Gilyen, Aram Harrow, Sander Gribling, Matt Hastings, Cedric Yen-Yu Lin, Ojas Parekh, and David Poulin for interesting discussions and useful comments on the paper. This work was funded by Cambridge Quantum Computing, Microsoft and the National Science Foundation.Additional details
- Eprint ID
- 84139
- Resolver ID
- CaltechAUTHORS:20180105-142517243
- Cambridge Quantum Computing
- Microsoft
- NSF
- Created
-
2018-01-05Created from EPrint's datestamp field
- Updated
-
2021-11-15Created from EPrint's last_modified field