DLR-Logo -> http://www.dlr.de
DLR Portal Home | Imprint | Privacy Policy | Contact | Deutsch
Fontsize: [-] Text [+]

Quantum Annealing versus Digital Computing: An Experimental Comparison

Jünger, Michael and Lobe, Elisabeth and Mutzel, Petra and Reinelt, Gerhard and Rendl, Franz and Rinaldi, Giovanni and Stollenwerk, Tobias (2021) Quantum Annealing versus Digital Computing: An Experimental Comparison. Journal of Experimental Algorithmics, 26 (1.9), pp. 1-30. Association for Computing Machinery (ACM). doi: 10.1145/3459606. ISSN 1084-6654.

[img] PDF - Only accessible within DLR - Published version

Official URL: https://dl.acm.org/doi/10.1145/3459606


Quantum annealing is getting increasing attention in combinatorial optimization. The quantum processing unit by D-Wave is constructed to approximately solve Ising models on so-called Chimera graphs. Ising models are equivalent to quadratic unconstrained binary optimization (QUBO) problems and maximum cut problems on the associated graphs. We have tailored branch-and-cut as well as semidefinite programming algorithms for solving Ising models for Chimera graphs to provable optimality and use the strength of these approaches for comparing our solution values to those obtained on the current quantum annealing machine, D-Wave 2000Q. This allows for the assessment of the quality of solutions produced by the D-Wave hardware. In addition, we also evaluate the performance of a heuristic by Selby. It has been a matter of discussion in the literature how well the D-Wave hardware performs at its native task, and our experiments shed some more light on this issue. In particular, we examine how reliably the D-Wave computer can deliver true optimum solutions and present some surprising results.

Item URL in elib:https://elib.dlr.de/146751/
Document Type:Article
Additional Information:https://dl.acm.org/doi/10.1145/3459606
Title:Quantum Annealing versus Digital Computing: An Experimental Comparison
AuthorsInstitution or Email of AuthorsAuthor's ORCID iDORCID Put Code
Jünger, MichaelUniversity of CologneUNSPECIFIEDUNSPECIFIED
Lobe, ElisabethUNSPECIFIEDhttps://orcid.org/0000-0002-3473-8906UNSPECIFIED
Mutzel, PetraTU Dortmund UniversityUNSPECIFIEDUNSPECIFIED
Reinelt, GerhardHeidelberg UniversityUNSPECIFIEDUNSPECIFIED
Rendl, FranzUniversity of KlagenfurtUNSPECIFIEDUNSPECIFIED
Rinaldi, GiovanniIstituto di Analisi dei Sistemi ed Informatica, RomeUNSPECIFIEDUNSPECIFIED
Stollenwerk, TobiasUNSPECIFIEDhttps://orcid.org/0000-0001-5445-8082UNSPECIFIED
Date:9 July 2021
Journal or Publication Title:Journal of Experimental Algorithmics
Refereed publication:Yes
Open Access:No
Gold Open Access:No
In ISI Web of Science:No
Page Range:pp. 1-30
Publisher:Association for Computing Machinery (ACM)
Keywords:branch and cut, chimera graphs, exact methods for combinatorial optimization, experimental evaluation, maximum cut problem, integer programming, quadratic unconstrained binary optimization, Ising model, semidefinite programming, Quantum annealing
HGF - Research field:Aeronautics, Space and Transport
HGF - Program:Space
HGF - Program Themes:Space System Technology
DLR - Research area:Raumfahrt
DLR - Program:R SY - Space System Technology
DLR - Research theme (Project):R - Quantum computing
Location: Köln-Porz
Institutes and Institutions:Institute for Software Technology > High-Performance Computing
Institute for Software Technology
Deposited By: Lobe, Elisabeth
Deposited On:07 Dec 2021 12:04
Last Modified:07 Dec 2021 12:04

Repository Staff Only: item control page

Help & Contact
electronic library is running on EPrints 3.3.12
Website and database design: Copyright © German Aerospace Center (DLR). All rights reserved.