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. https://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: https://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: |
| |||||||||
| ORCID: |
| |||||||||
| 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: |
| |||||||||
| Subject Keywords: | quantum algorithms, semidefinite programs, Gibbs sampling | |||||||||
| DOI: | 10.1109/FOCS.2017.45 | |||||||||
| Record Number: | CaltechAUTHORS:20180105-142517243 | |||||||||
| Persistent URL: | https://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: | 15 Nov 2021 20:17 |
Repository Staff Only: item control page
