Summary: We give two new 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 an input model where one is given access to an oracle to the entries of the matrices at unit cost. We show that it has run time \(\widetilde{O}(s^2 (\sqrt{m}\varepsilon^{-10}+\sqrt{n}\varepsilon^{-12}))\), with \(\varepsilon\) the error of the solution. This gives an optimal dependence in terms of \(m\), \(n\) and quadratic improvement over previous quantum algorithms (when \(m\approx n)\). The second algorithm assumes a fully quantum input model in which the input matrices are given as quantum states. We show that its run time is \(\widetilde{O}(\sqrt{m}+\text{poly}(r))\cdot\text{poly}(\log m,\log n,B,\varepsilon^{-1})\), with \(B\) an upper bound on the trace-norm of all input matrices. In particular the complexity depends only polylogarithmically 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 \(\rho\) with rank at most \(r\), we show we can find in time \(\sqrt{m}\cdot\text{poly}(\log m\log n,r,\varepsilon^{-1})\) a description of the state as a quantum circuit preparing a density matrix which has the same expectation values as \(\rho\) on the \(m\) measurements, up to error \(\varepsilon\). 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 update method. One of our main technical contributions is a quantum Gibbs state sampler for low-rank Hamiltonians, given quantum states encoding these Hamiltonians, with a poly-logarithmic dependence on its dimension, which is based on ideas developed in quantum principal component analysis. We also develop a “fast” quantum OR lemma with a quadratic improvement in gate complexity over the construction by A. W. Harrow et al. [in: Proceedings of the 28th annual ACM-SIAM symposium on discrete algorithms, SODA 2017, Barcelona, Spain, January 16–19, 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1598–1611 (2017; Zbl 1410.68133)]. We believe both techniques might be of independent interest.
For the entire collection see [Zbl 1414.68003].