Fernando Brandao: Quantum speed-ups for semidefinite programming
Episode details
Episode description
"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."
Watch also from the same channel
More episodes from this channel
You might be interested in
