Faster quantum and classical SDP approximations for quadratic binary optimization

Research output: Contribution to journal › Journal article › Research › peer-review

Standard

Faster quantum and classical SDP approximations for quadratic binary optimization. / Brandão, Fernando G.S.L.; Kueng, Richard; França, Daniel Stilck.

In: Quantum, Vol. 6, 625, 2022, p. 1-42.

Research output: Contribution to journal › Journal article › Research › peer-review

Harvard

Brandão, FGSL, Kueng, R & França, DS 2022, 'Faster quantum and classical SDP approximations for quadratic binary optimization', Quantum, vol. 6, 625, pp. 1-42. https://doi.org/10.22331/Q-2022-01-20-625

APA

Brandão, F. G. S. L., Kueng, R., & França, D. S. (2022). Faster quantum and classical SDP approximations for quadratic binary optimization. Quantum, 6, 1-42. [625]. https://doi.org/10.22331/Q-2022-01-20-625

Vancouver

Brandão FGSL, Kueng R, França DS. Faster quantum and classical SDP approximations for quadratic binary optimization. Quantum. 2022;6:1-42. 625. https://doi.org/10.22331/Q-2022-01-20-625

Author

Brandão, Fernando G.S.L. ; Kueng, Richard ; França, Daniel Stilck. / Faster quantum and classical SDP approximations for quadratic binary optimization. In: Quantum. 2022 ; Vol. 6. pp. 1-42.

Bibtex

@article{7ea4faa8ce804a829a6f82f8eee5b0d2,
title = "Faster quantum and classical SDP approximations for quadratic binary optimization",
abstract = "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 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.",
author = "Brand{\~a}o, {Fernando G.S.L.} and Richard Kueng and Fran{\c c}a, {Daniel Stilck}",
note = "Publisher Copyright: {\textcopyright} 2022 Quantum. All rights reserved.",
year = "2022",
doi = "10.22331/Q-2022-01-20-625",
language = "English",
volume = "6",
pages = "1--42",
journal = "Quantum",
issn = "2521-327X",
publisher = "Verein zur F{\"o}rderung des Open Access Publizierens in den Quantenwissenschaften",

}

RIS

TY - JOUR

T1 - Faster quantum and classical SDP approximations for quadratic binary optimization

AU - Brandão, Fernando G.S.L.

AU - Kueng, Richard

AU - França, Daniel Stilck

N1 - Publisher Copyright: © 2022 Quantum. All rights reserved.

PY - 2022

Y1 - 2022

N2 - 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 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.

AB - 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 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.

UR - http://www.scopus.com/inward/record.url?scp=85124614668&partnerID=8YFLogxK

U2 - 10.22331/Q-2022-01-20-625

DO - 10.22331/Q-2022-01-20-625

M3 - Journal article

AN - SCOPUS:85124614668

VL - 6

SP - 1

EP - 42

JO - Quantum

JF - Quantum

SN - 2521-327X

M1 - 625

ER -

ID: 297605824