Benchmarking Quantum Annealing Against “Hard” Instances of the Bipartite Matching Problem

This paper experimentally investigates the behavior of analog quantum computers as commercialized by D-Wave when confronted to instances of the maximum cardinality matching problem which is specifically designed to be hard to solve by means of simulated annealing. We benchmark a D-Wave “Washington”...

Full description

Saved in:
Bibliographic Details
Published in:SN computer science 2021-04, Vol.2 (2), p.106, Article 106
Main Authors: Vert, Daniel, Sirdey, Renaud, Louise, Stéphane
Format: Article
Language:English
Subjects:
Algorithms
Analog computers
Commercialization
Computer Imaging
Computer Science
Computer Systems Organization and Communication Networks
Computers
Data Structures and Information Theory
Information Systems and Communication Service
Matching
Optimization
Original Research
Other
Pattern Recognition and Graphics
Polynomials
Quantum computers
Quantum computing
Quantum Computing: Circuits Systems Automation and Applications
Qubits (quantum computing)
Simulated annealing
Software Engineering/Programming and Operating Systems
Topology
Vision
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper experimentally investigates the behavior of analog quantum computers as commercialized by D-Wave when confronted to instances of the maximum cardinality matching problem which is specifically designed to be hard to solve by means of simulated annealing. We benchmark a D-Wave “Washington” (2X) with 1098 operational qubits on various sizes of such instances and observe that for all but the most trivially small of these it fails to obtain an optimal solution. Thus, our results suggest that quantum annealing, at least as implemented in a D-Wave device, falls in the same pitfalls as simulated annealing and hence provides additional evidences suggesting that there exist polynomial-time problems that such a machine cannot solve efficiently to optimality. Additionally, we investigate the extent to which the qubits interconnection topologies explains these latter experimental results. In particular, we provide evidences that the sparsity of these topologies which, as such, lead to QUBO problems of artificially inflated sizes can partly explain the aforementioned disappointing observations. Therefore, this paper hints that denser interconnection topologies are necessary to unleash the potential of the quantum annealing approach.
ISSN:2662-995X
2661-8907
DOI:10.1007/s42979-021-00483-1