Faster quantum and classical SDP approximations for quadratic binary optimization

doi:10.22331/q-2022-01-20-625

Faster quantum and classical SDP approximations for quadratic binary optimization

2022-01-20

6

OA

AI

F

Fernando G. S. L. Brandão *

DOI：10.22331/q-2022-01-20-625

Original

Original request for help

Save

Abstract

En 中文

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 MAxeuT on Erdos-Renyi graphs. We also provide an efficient randomized rounding procedure that converts approximately optimal SDP solutions into approximations of the original quadratic optimization problem.

Keywords:

ALGORITHMS

NORMS

MATRICES

CUT

Faster quantum and classical SDP approximations for quadratic binary optimization

Abstract

Journal

Organization