We give a quantum algorithm for solving semidefinite programs (SDPs). 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.

Download PDF