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 (2019) Faster quantum and classical SDP approximations for quadratic binary optimization. . (Unpublished)

[img] PDF - 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. The 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. We also provide an efficient randomized rounding procedure that converts approximately optimal SDP solutions into constant factor approximations of the original quadratic optimization problem.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Brandão, Fernando G. S. L.0000-0003-3866-9378
Stilck França, Daniel0000-0001-9699-5994
Additional Information:We would like to thank Aram Harrow for inspiring discussions. Our gratitude extends, in particular, to Ronald deWolf, András Gilyén and Joran van Apeldoorn who provided valuable feedback regarding an earlier version of this draft. 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:UNSPECIFIED, 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
Elite Network of BavariaUNSPECIFIED
Technische Universität MünchenUNSPECIFIED
German Excellence InitiativeUNSPECIFIED
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:04 Jun 2020 10:14

Repository Staff Only: item control page