Faster quantum and classical SDP approximations for quadratic binary optimization
Sprache des Titels:
Englisch
Original Kurzfassung:
We give a quantum speedup for solving the canonical semidefinite programming relaxation for binary quadratic optimization. This class of relaxations for
combinatorial optimization has so far eluded quantum speedups. Our methods
combine ideas from quantum Gibbs sampling and matrix exponent updates. A
de-quantization of the algorithm also leads to a faster classical solver. For generic
instances, our quantum solver gives a nearly quadratic speedup over state-of-theart algorithms. Such instances include approximating the ground state of spin
glasses and MaxCut on Erd¨os-R´enyi graphs. We also provide an efficient randomized rounding procedure that converts approximately optimal SDP solutions
into approximations of the original quadratic optimization problem.