Abstract

We give semidefinite program (SDP) quantum solvers with an exponential speed-up over classical ones. Specifically, we consider SDP instances with m constraint matrices of dimension n, each of rank at most r, and assume that the input matrices of the SDP are given as quantum states (after a suitable normalization). Then we show there is a quantum algorithm that solves the SDP feasibility problem with accuracy ǫ by using√ m log m· poly (log n, r, ǫ− 1) quantum gates. The dependence on n provides an exponential improvement over the work of Brandao and Svore [6] and the work of van Apeldoorn et al.[23], and demonstrates an exponential quantum speed-up when m and r are small.
We apply the SDP solver to the problem of learning 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 ρ, we show we can find in time√ m log m· poly (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.

Date

January 1, 1970

Authors

Fernando GSL Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M Svore, Xiaodi Wu

Journal

arXiv preprint arXiv:1710.02581

Volume

84