Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
Medientyp:
E-Artikel
Titel:
Faster quantum and classical SDP approximations for quadratic binary optimization
Beteiligte:
G.S L. Brandão, Fernando;
Kueng, Richard;
Stilck França, Daniel
Erschienen:
Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften, 2022
Erschienen in:
Quantum, 6 (2022), Seite 625
Sprache:
Englisch
DOI:
10.22331/q-2022-01-20-625
ISSN:
2521-327X
Entstehung:
Anmerkungen:
Beschreibung:
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-the-art algorithms. Such instances include approximating the ground state of spin glasses and MaxCut on Erdös-Rényi graphs. We also provide an efficient randomized rounding procedure that converts approximately optimal SDP solutions into approximations of the original quadratic optimization problem.