EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Scaling Advantage in Approximate Optimization with Quantum Annealing

Humberto Munoz-Bauza, Daniel Lidar

Physical Review Letters · 23.04.2025 · 134 (16)

DOI: 10.1103/physrevlett.134.160601 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Physical Review Letters, online erschienen am 23.04.2025. Verfasst von Humberto Munoz-Bauza und 1 weiteren Autor:innen. Beteiligte Einrichtung: NASA Ames Research Center, Quantum Artificial Intelligence Lab. (QuAIL), Moffett Field, California 94035, USA. Die Arbeit wurde bisher 38-mal zitiert (Crossref) und nennt 74 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Defense Advanced Research Projects Agency, Army Research Office, National Aeronautics and Space Administration.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Quantum annealing is a heuristic optimization algorithm that exploits quantum evolution to find low-energy states. Quantum annealers have scaled up in recent years to tackle increasingly larger and more highly connected discrete optimization and quantum simulation problems. Nevertheless, a computational quantum advantage in exact optimization using quantum annealing hardware has so far remained elusive. Here, we present evidence for a quantum annealing scaling advantage in approximate optimization. The advantage is relative to the top classical heuristic algorithm: parallel tempering with isoenergetic cluster moves (PT-ICM). The setting is a family of 2D spin-glass problems with high-precision spin-spin interactions. To achieve this advantage, we implement quantum annealing correction (QAC): an embedding of a bit-flip error-correcting code with energy penalties that leverages the properties of the D-Wave Advantage quantum annealer to yield over 1,300 error-suppressed logical qubits on a degree-5 interaction graph. We generate random spin-glass instances on this graph and benchmark their time-to-epsilon, a generalization of the time-to-solution metric for low-energy states. We demonstrate that, with QAC, quantum annealing exhibits a scaling advantage over PT-ICM at sampling low-energy states with an optimality gap of at least 1.0%. This amounts to the first demonstration of an algorithmic quantum speedup in approximate optimization.

Autor:innen und Institutionen

  • NASA Ames Research Center, Quantum Artificial Intelligence Lab. (QuAIL), Moffett Field, California 94035, USA.
  • KBR, Inc., 601 Jefferson St., Houston, Texas 77002, USA.
  • University of Southern California, Department of Physics and Astronomy, Los Angeles, California 90089, USA.
  • University of Southern California, Center for Quantum Information Science & Technology, Los Angeles, California 90089, USA.
  • University of Southern California, Department of Electrical Engineering, Los Angeles, California 90089, USA.
  • University of Southern California, Department of Chemistry, Los Angeles, California 90089, USA.

Förderung

  • Defense Advanced Research Projects Agency
  • Army Research Office
  • National Aeronautics and Space Administration
  • University of Southern California

Zitieren

APA

Munoz-Bauza, H., & Lidar, D. (2025). Scaling Advantage in Approximate Optimization with Quantum Annealing. Physical Review Letters, 134(16). https://doi.org/10.1103/physrevlett.134.160601

Vancouver

Munoz-Bauza H, Lidar D. Scaling Advantage in Approximate Optimization with Quantum Annealing. Physical Review Letters. 2025;134(16). doi:10.1103/physrevlett.134.160601

BibTeX
@article{MunozBauza2025,
  author = {Munoz-Bauza, Humberto and Lidar, Daniel},
  title = {Scaling Advantage in Approximate Optimization with Quantum Annealing},
  journal = {Physical Review Letters},
  year = {2025},
  volume = {134},
  number = {16},
  doi = {10.1103/physrevlett.134.160601}
}
Kostenlos starten →