We give a quantum algorithm for solving semidefinite programs (SDPs). It has worst-case running time
n21m21s2poly(log(n),log(m),R,r,1/δ), with
n and
s the dimension and row-sparsity of the input matrices, respectively,
m the number of constraints,
δ the accuracy of the solution, and
R,r a upper bounds on the size of the optimal primal and dual solutions. 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) giving a
Ω(n21+m21) quantum lower bound for solving semidefinite programs with constant
s,R,r and
δ. The quantum algorithm is constructed by a combination of quantum Gibbs sampling and the multiplicative weight method. In particular it is based on a classical algorithm of Arora and Kale for approximately solving SDPs. We present a modification of their algorithm to eliminate the need for solving an inner linear program which may be of independent interest.
We propose a branch-and-bound algorithm for minimizing a bilinear functional of the form f (X, Y) = tr((X ⊗ Y) Q) +tr(AX) +tr(BY), of pairs of Hermitian matrices (X, Y) restricted by joint semidefinite programming constraints. The functional is parametrized by self-adjoint matrices Q, A and B. This problem generalizes that of a bilinear program, where X and Y belong to polyhedra. The algorithm converges to a global optimum and yields upper and lower bounds on its value in every step. Various problems in quantum information theory can be expressed in this form. As an example application, we compute Dobrushin curves of quantum channels, giving upper bounds on classical coding with energy constraints.
We give a quantum algorithm for solving semidefinite programs (SDPs). It has worst-case running time n1/2m1/2s2poly(log(n), log(m), R, r, 1/δ), with n and s the dimension and row-sparsity of the input matrices, respectively, m the number of constraints, δ the accuracy of the solution, and R, r upper bounds on the size of the optimal primal and dual solutions, respectively. 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) giving a Ω(n1/2+ m2) quantum lower bound for solving semidefinite programs with constant s, R, r and δ. The quantum algorithm is constructed by a combination of quantum Gibbs sampling and the multiplicative weight method. In particular it is based on a classical algorithm of Arora and Kale for approximately solving SDPs. We present a modification of their algorithm to eliminate the need for solving an inner linear program which may be of independent interest.