On the emerging potential of quantum annealing hardware for combinatorial optimization

Byron Tasseff, Tameem Albash, Zachary Morrell, Marc Vuffray, Andrey Y. Lokhov, Sidhant Misra and Carleton Coffrin ()
Additional contact information
Byron Tasseff: Los Alamos National Laboratory
Tameem Albash: University of New Mexico
Zachary Morrell: Los Alamos National Laboratory
Marc Vuffray: Los Alamos National Laboratory
Andrey Y. Lokhov: Los Alamos National Laboratory
Sidhant Misra: Los Alamos National Laboratory
Carleton Coffrin: Los Alamos National Laboratory

Journal of Heuristics, 2024, vol. 30, issue 5, No 4, 325-358

Abstract: Abstract Over the past decade, the usefulness of quantum annealing hardware for combinatorial optimization has been the subject of much debate. Thus far, experimental benchmarking studies have indicated that quantum annealing hardware does not provide an irrefutable performance gain over state-of-the-art optimization methods. However, as this hardware continues to evolve, each new iteration brings improved performance and warrants further benchmarking. To that end, this work conducts an optimization performance assessment of D-Wave Systems’ Advantage Performance Update computer, which can natively solve sparse unconstrained quadratic optimization problems with over 5,000 binary decision variables and 40,000 quadratic terms. We demonstrate that classes of contrived problems exist where this quantum annealer can provide run time benefits over a collection of established classical solution methods that represent the current state-of-the-art for benchmarking quantum annealing hardware. Although this work does not present strong evidence of an irrefutable performance benefit for this emerging optimization technology, it does exhibit encouraging progress, signaling the potential impacts on practical optimization tasks in the future.

Keywords: Ising; Optimization; Quadratic; Quantum annealing; QUBO (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-024-09530-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:30:y:2024:i:5:d:10.1007_s10732-024-09530-5

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-024-09530-5

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().