EUVIMEDEUVIMED entdecken
Open Access

Quantum-enhanced greedy combinatorial optimization solver

Maxime Dupont iD, Bram Evert, Mark J Hodson, Bhuvanesh Sundar iD, Stephen Jeffrey, Yuki Yamaguchi, Dennis Feng, Filip B Maciejewski iD, Stuart Hadfield iD, M Sohaib Alam iD, Zhihui Wang, Shon Grabbe und 4 weitere

Science Advances · 10.11.2023 · 9 (45)

DOI: 10.1126/sciadv.adi0487 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Science Advances, erschienen am 10.11.2023. Verfasst von Maxime Dupont und 15 weiteren Autor:innen. Beteiligte Einrichtung: Rigetti Computing, Berkeley, CA 94710, USA. Die Arbeit wurde bisher 44-mal zitiert (Crossref) und nennt 62 Literaturangaben. Der Volltext ist frei in PubMed Central verfügbar.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Combinatorial optimization is a broadly attractive area for potential quantum advantage, but no quantum algorithm has yet made the leap. Noise in quantum hardware remains a challenge, and more sophisticated quantum-classical algorithms are required to bolster their performance. Here, we introduce an iterative quantum heuristic optimization algorithm to solve combinatorial optimization problems. The quantum algorithm reduces to a classical greedy algorithm in the presence of strong noise. We implement the quantum algorithm on a programmable superconducting quantum system using up to 72 qubits for solving paradigmatic Sherrington-Kirkpatrick Ising spin glass problems. We find the quantum algorithm systematically outperforms its classical greedy counterpart, signaling a quantum enhancement. Moreover, we observe an absolute performance comparable with a state-of-the-art semidefinite programming method. Classical simulations of the algorithm illustrate that a key challenge to reaching quantum advantage remains improving the quantum device characteristics.

Autor:innen und Institutionen

  • Rigetti Computing, Berkeley, CA 94710, USA.
  • QuAIL, NASA Ames Research Center, Moffett Field, CA 94035, USA.
  • USRA Research Institute for Advanced Computer Science, Mountain View, CA 94035, USA.

ORCID-Profile: Maxime Dupont, Bhuvanesh Sundar, Filip B Maciejewski, Stuart Hadfield, M Sohaib Alam, Davide Venturelli, Matthew J Reagor

Zitieren

APA

Dupont, M., Evert, B., Hodson, M. J., Sundar, B., Jeffrey, S., Yamaguchi, Y., Feng, D., Maciejewski, F. B., Hadfield, S., Alam, M. S., Wang, Z., Grabbe, S., Lott, P. A., Rieffel, E. G., Venturelli, D., & Reagor, M. J. (2023). Quantum-enhanced greedy combinatorial optimization solver. Science Advances, 9(45). https://doi.org/10.1126/sciadv.adi0487

Vancouver

Dupont M, Evert B, Hodson MJ, Sundar B, Jeffrey S, Yamaguchi Y, et al. Quantum-enhanced greedy combinatorial optimization solver. Science Advances. 2023;9(45). doi:10.1126/sciadv.adi0487

BibTeX
@article{Dupont2023,
  author = {Dupont, Maxime and Evert, Bram and Hodson, Mark J and Sundar, Bhuvanesh and Jeffrey, Stephen and Yamaguchi, Yuki and Feng, Dennis and Maciejewski, Filip B and Hadfield, Stuart and Alam, M Sohaib and Wang, Zhihui and Grabbe, Shon and Lott, P Aaron and Rieffel, Eleanor G and Venturelli, Davide and Reagor, Matthew J},
  title = {Quantum-enhanced greedy combinatorial optimization solver},
  journal = {Science Advances},
  year = {2023},
  volume = {9},
  number = {45},
  doi = {10.1126/sciadv.adi0487}
}
Kostenlos starten →