CaltechAUTHORS
  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. http://resolver.caltech.edu/CaltechAUTHORS:20180105-142517243

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

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20180105-142517243

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.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.1109/FOCS.2017.45DOIArticle
http://ieeexplore.ieee.org/document/8104077/PublisherArticle
ORCID:
AuthorORCID
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.
Funders:
Funding AgencyGrant Number
Cambridge Quantum ComputingUNSPECIFIED
MicrosoftUNSPECIFIED
NSFUNSPECIFIED
Subject Keywords:quantum algorithms, semidefinite programs, Gibbs sampling
Record Number:CaltechAUTHORS:20180105-142517243
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20180105-142517243
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 http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8104077&isnumber=8104011
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:84139
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:05 Jan 2018 22:46
Last Modified:30 Jul 2018 15:19

Repository Staff Only: item control page