A Caltech Library Service

Quantum Speed-Ups for Solving Semidefinite Programs

Brandão, Fernando G. S. L. and Svore, Krysta M. (2017) Quantum Speed-Ups for Solving Semidefinite Programs. In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE , Piscataway, NJ, pp. 415-426. ISBN 978-1-5386-3464-6.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Brandão, Fernando G. S. L.0000-0003-3866-9378
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.
Funding AgencyGrant Number
Cambridge Quantum ComputingUNSPECIFIED
Subject Keywords:quantum algorithms, semidefinite programs, Gibbs sampling
Record Number:CaltechAUTHORS:20180105-142517243
Persistent URL:
Official Citation:F. G. S. L. Brandao and K. M. Svore, "Quantum Speed-Ups for Solving Semidefinite Programs," 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), Berkeley, CA, 2017, pp. 415-426. doi: 10.1109/FOCS.2017.45
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:84139
Deposited By: George Porter
Deposited On:05 Jan 2018 22:46
Last Modified:15 Nov 2021 20:17

Repository Staff Only: item control page