A Caltech Library Service

Quantum Speed-ups for Semidefinite Programming

Brandão, Fernando G. S. L. and Svore, Krysta M. (2017) Quantum Speed-ups for Semidefinite Programming. . (Submitted)

[img] PDF - Submitted Version
See Usage Policy.


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 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. 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 giving a Ω(n^(1/2) + m^(1/2)) quantum lower bound for solving semidefinite programs with constant s, R, r and δ. We then argue that in some instances the algorithm offer even exponential speed-ups. This is the case whenever the quantum Gibbs states of Hamiltonians given by linear combinations of the input matrices of the SDP can be prepared efficiently on a quantum computer. An example are SDPs in which the input matrices have low-rank: For SDPs with the maximum rank of any input matrix bounded by rank, we show the quantum algorithm runs in time poly(log(n), log(m), rank, r, R, δ)m^(1/2). The quantum algorithm is constructed by a combination of quantum Gibbs sampling and the multiplicative weight method. In particular it is based on an classical algorithm of Arora and Kale for approximately solving SDPs. We present a modification of their algorithm to eliminate the need of solving an inner linear program which may be of independent interest.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Brandão, Fernando G. S. L.0000-0003-3866-9378
Additional Information:(Submitted on 18 Sep 2016 (v1), last revised 20 Apr 2017 (this version, v4)) 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.
Group:Institute for Quantum Information and Matter
Record Number:CaltechAUTHORS:20170726-063707920
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:79370
Deposited By: Ruth Sustaita
Deposited On:26 Jul 2017 14:36
Last Modified:02 Jun 2023 00:26

Repository Staff Only: item control page