Quantum speedup of the traveling-salesman problem for bounded-degree graphs

Dominic J. Moylett, Noah Linden, Ashley Montanaro

Research output: Contribution to journalArticle (Academic Journal)peer-review

13 Citations (Scopus)
394 Downloads (Pure)

Abstract

The Travelling Salesman Problem is one of the most famous problems in graph theory. However, little is currently known about the extent to which quantum computers could speed up algorithms for the problem. In this paper, we prove a quadratic quantum speedup when the degree of each vertex is at most 3 by applying a quantum backtracking algorithm to a classical algorithm by Xiao and Nagamochi. We then use similar techniques to accelerate a classical algorithm for when the degree of each vertex is at most 4, before speeding up higher-degree graphs via reductions to these instances.
Original languageEnglish
Article number032323
Number of pages10
JournalPhysical Review A
Volume95
Issue number3
Early online date22 Mar 2017
DOIs
Publication statusPublished - Mar 2017

Structured keywords

  • Bristol Quantum Information Institute
  • QITG
  • QETLabs

Keywords

  • Quantum Algorithms
  • Quantum Information
  • Computer Science

Fingerprint Dive into the research topics of 'Quantum speedup of the traveling-salesman problem for bounded-degree graphs'. Together they form a unique fingerprint.

Cite this