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)
https://resolver.caltech.edu/CaltechAUTHORS:20190801-134527208

PDF
- Submitted Version
See Usage Policy. 577kB |

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190801-134527208

## Abstract

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: |
| ||||||||||||

ORCID: |
| ||||||||||||

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 | ||||||||||||

Funders: |
| ||||||||||||

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: | https://resolver.caltech.edu/CaltechAUTHORS:20190801-134527208 | ||||||||||||

Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||

ID Code: | 97597 | ||||||||||||

Collection: | CaltechAUTHORS | ||||||||||||

Deposited By: | George Porter | ||||||||||||

Deposited On: | 01 Aug 2019 22:13 | ||||||||||||

Last Modified: | 04 Jun 2020 10:14 |

Repository Staff Only: item control page