A Caltech Library Service

Faster quantum and classical SDP approximations for quadratic binary optimization

Brandão, Fernando G. S. L. and Kueng, Richard and Stilck França, Daniel (2022) Faster quantum and classical SDP approximations for quadratic binary optimization. Quantum, 6 . Art. No. 625. ISSN 2521-327X. doi:10.22331/q-2022-01-20-625.

[img] PDF (10 Jan 2022) - Published Version
Creative Commons Attribution.

[img] PDF (10 Sep 2019) - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Brandão, Fernando G. S. L.0000-0003-3866-9378
Kueng, Richard0000-0002-8291-648X
Stilck França, Daniel0000-0001-9699-5994
Additional Information:This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions. Published: 2022-01-20. We would like to thank Aram Harrow for inspiring discussions. Our gratitude extends, in particular, to Ronald de Wolf, Andás Gilyén and Joran van Apeldoorn who provided valuable feedback regarding an earlier version of this draft. Finally, we would like to thank the anonymous reviewers for in-depth comments and suggestions. D.S.F. would like to thank the hospitality of Caltech's Institute for Quantum Information and Matter, where the main ideas in this paper were conceived during a visit. F.G.L.S.B and R.K. acknowledge funding provided by the Institute for Quantum Information and Matter, an NSF Physics Frontiers Center (NSF Grant PHY-1733907), as well as financial support from Samsung. R.K's work is also supported by the Office of Naval Research (Award N00014-17-1-2146) and the Army Research Office (Award W911NF121054). D.S.F. acknowledges financial support from VILLUM FONDEN via the QMATH Centre of Excellence (Grant no. 10059), the graduate program TopMath of the Elite Network of Bavaria, the TopMath Graduate Center of TUM Graduate School at Technische Universität München and by the Technische Universität München - Institute for Advanced Study, funded by the German Excellence Initiative and the European Union Seventh Framework Programme under grant agreement no. 291763.
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
Office of Naval Research (ONR)N00014-17-1-2146
Army Research Office (ARO)W911NF121054
Villum Foundation10059
Elite Network of BavariaUNSPECIFIED
Technische Universität MünchenUNSPECIFIED
Deutsche Forschungsgemeinschaft (DFG)UNSPECIFIED
European Research Council (ERC)291763
Record Number:CaltechAUTHORS:20190912-075203295
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:98596
Deposited By: Tony Diaz
Deposited On:12 Sep 2019 17:23
Last Modified:16 Feb 2022 18:20

Repository Staff Only: item control page