elib
DLR-Header
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
3MB

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

Abstract

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
Authors:
AuthorsInstitution or Email of AuthorsAuthor's ORCID iD
Jünger, MichaelUniversity of CologneUNSPECIFIED
Lobe, ElisabethElisabeth.Lobe (at) dlr.dehttps://orcid.org/0000-0002-3473-8906
Mutzel, PetraTU Dortmund UniversityUNSPECIFIED
Reinelt, GerhardHeidelberg UniversityUNSPECIFIED
Rendl, FranzUniversity of KlagenfurtUNSPECIFIED
Rinaldi, GiovanniIstituto di Analisi dei Sistemi ed Informatica, RomeUNSPECIFIED
Stollenwerk, Tobiastobias.stollenwerk (at) dlr.dehttps://orcid.org/0000-0001-5445-8082
Date:9 July 2021
Journal or Publication Title:Journal of Experimental Algorithmics
Refereed publication:Yes
Open Access:No
Gold Open Access:No
In SCOPUS:Yes
In ISI Web of Science:No
Volume:26
DOI :10.1145/3459606
Page Range:pp. 1-30
Publisher:Association for Computing Machinery (ACM)
ISSN:1084-6654
Status:Published
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

Browse
Search
Help & Contact
Information
electronic library is running on EPrints 3.3.12
Copyright © 2008-2017 German Aerospace Center (DLR). All rights reserved.