Fernando Brandao: Quantum speed-ups for semidefinite programming

Опубликовано 1 февраля 2017, 0:52

"We give a quantum algorithm for solving semidenite programs (SDPs). It has worst-case running
time O(n^1/1 m^1/2 s R^10/delta^10), with n and s the dimension and row sparsity of the input matrices, respectively, m the number of constraints, delta the accuracy of the solution, and R an upper bound on the trace of the optimal solution. 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 (in terms of n and m).

We then argue that in some instances the algorithm offers 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 r, we show the quantum algorithm runs in time poly(log(n), log(m), r, R 1/delta)m^1/2 . This constitutes an exponential speed-up in terms of the dimension of the input matrices over the best-known classical method.

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 modication of their algorithm to eliminate the need for
solving an inner linear program, which may be of independent interest."