A Caltech Library Service

Quantum SDP Solvers: Large Speed-ups, Optimality, and Applications to Quantum Learning

Brandão, Fernando G. S. L. and Kalev, Amir and Li, Tongyang and Lin, Cedric Yen-Yu and Svore, Krysta M. and Wu, Xiaodi (2017) Quantum SDP Solvers: Large Speed-ups, Optimality, and Applications to Quantum Learning. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We give two quantum algorithms for solving semidefinite programs (SDPs) providing quantum speed-ups. We consider SDP instances with m constraint matrices, each of dimension n, rank at most r, and sparsity s. The first algorithm assumes access to an oracle to the matrices at unit cost. We show that it has run time Õ(s^2(√((mϵ)^(−10)) + √((nϵ)^(−12))), with ϵ the error of the solution. This gives an optimal dependence in terms of m, n and quadratic improvement over previous quantum algorithms when m ≈ n. The second algorithm assumes a fully quantum input model in which the matrices are given as quantum states. We show that its run time is Õ (√m + poly(r))⋅poly(log m,log n,B,ϵ^(−1)), with B an upper bound on the trace-norm of all input matrices. In particular the complexity depends only poly-logarithmically in n and polynomially in r. We apply the second SDP solver to learn a good description of a quantum state with respect to a set of measurements: Given m measurements and a supply of copies of an unknown state ρ with rank at most r, we show we can find in time √m⋅poly(log m,log n,r,ϵ^(−1)) a description of the state as a quantum circuit preparing a density matrix which has the same expectation values as ρ on the m measurements, up to error ϵ. The density matrix obtained is an approximation to the maximum entropy state consistent with the measurement data considered in Jaynes' principle from statistical mechanics. As in previous work, we obtain our algorithm by "quantizing" classical SDP solvers based on the matrix multiplicative weight method. One of our main technical contributions is a quantum Gibbs state sampler for low-rank Hamiltonians with a poly-logarithmic dependence on its dimension, which could 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:We thank Scott Aaronson, Joran van Apeldoorn, András Gilyén, Cupjin Huang, and anonymous reviewers for helpful discussions. We are also grateful to Joran van Apeldoorn and András Gilyén for sharing a working draft of [4] with us. FB was supported by NSF. CYL and AK are supported by the Department of Defense. TL is supported by NSF CCF-1526380. XW is supported by the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Quantum Algorithms Teams program. XW is also supported by NSF grants CCF-1755800 and CCF-1816695.
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
Department of DefenseUNSPECIFIED
Department of Energy (DOE)UNSPECIFIED
Subject Keywords:Quantum algorithms, Semidefinite program, Convex optimization
Classification Code:2012 ACM Subject Classification Theory of computation → Semidefinite programming; Theory of computation →Quantum query complexity; Theory of computation →Convex optimization
Record Number:CaltechAUTHORS:20190801-134527208
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:97597
Deposited By: George Porter
Deposited On:01 Aug 2019 22:13
Last Modified:04 Jun 2020 10:14

Repository Staff Only: item control page