Quick Navigation

Overview Topics Abstract Importance Paper Tools References Reactions Discussion Publication Related

Topics

Quantum Optimization Quantum Machine Learning

Revisiting old combinatorial beasts in the quantum age: quantum annealing versus maximal matching

arXiv
Authors: Daniel Vert, Renaud Sirdey, Stéphane Louise

Year

2019

Paper ID

7271

Status

Preprint

Abstract Read

~2 min

Abstract Words

111

Citations

N/A

Abstract

This paper experimentally investigates the behavior of analog quantum computers such as commercialized by D-Wave when confronted to instances of the maximum cardinality matching problem 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 suggests that quantum annealing, at least as implemented in a D-Wave device, falls in the same pitfalls as simulated annealing and therefore suggest that there exist polynomial-time problems that such a machine cannot solve efficiently to optimality.

Why This Paper Matters

  • This paper contributes to the Quantum Machine Learning research area in the Quantum Articles archive.
  • It adds a 2019 reference point for readers tracking recent quantum research.
  • This paper experimentally investigates the behavior of analog quantum computers such as commercialized by D-Wave when confronted to instances of the maximum cardinality...

Paper Tools

Become a member to use research tools

Sign in to open papers, visit source links, share, cite, compare, copy DOI links, request category corrections, and build your reading list.

Become a member Sign in
Show Paper arXiv Publisher Share Cite This Paper Copy URL Compare Copy DOI Add to Reading List Category Correction Request

References & Citation Signals

[1] DOI https://doi.org/arXiv:1910.05129 [2] arXiv https://arxiv.org/abs/1910.05129 [3] Publisher https://arxiv.org/abs/1910.05129

Local Citation Graph (Related-Paper Links)

Current Paper #7271 #78828 Verifiable Sampling for Delegat... #78813 Large-Scale Benchmarking of Qua... #78775 On linearity or non-linearity i...

External citation index: OpenAlex citation signal

Community Reactions

Quick sentiment from readers on this paper.

Score: 0
Likes: 0 Dislikes: 0

Sign in to react to this paper.

Discussion & Reviews (Moderated)

Average Rating: 0.0 / 5 (0 ratings)

No written reviews yet.