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

Dominic J. Moylett; Noah Linden; Ashley Montanaro

doi:10.1103/PhysRevA.95.032323

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

Dominic J. Moylett, Noah Linden, Ashley Montanaro

Research output: Contribution to journal › Article (Academic Journal) › peer-review

30 Citations (Scopus)

474 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 language	English
Article number	032323
Number of pages	10
Journal	Physical Review A
Volume	95
Issue number	3
Early online date	22 Mar 2017
DOIs	https://doi.org/10.1103/PhysRevA.95.032323
Publication status	Published - Mar 2017

Research Groups and Themes

Bristol Quantum Information Institute
QITG
QETLabs

Keywords

Quantum Algorithms
Quantum Information
Computer Science

Access to Document

10.1103/PhysRevA.95.032323

Full-text PDF (accepted author manuscript)
This is the author accepted manuscript (AAM). The final published version (version of record) is available online via APS at http://journals.aps.org/pra/abstract/10.1103/PhysRevA.95.032323. Please refer to any applicable terms of use of the publisher.
Accepted author manuscript, 406 KB

Handle.net

Persistent link

Cite this

@article{13e01a0612c248049d39f0b1bab3f533,

title = "Quantum speedup of the traveling-salesman problem for bounded-degree graphs",

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.",

keywords = "Quantum Algorithms, Quantum Information, Computer Science",

author = "Moylett, \{Dominic J.\} and Noah Linden and Ashley Montanaro",

year = "2017",

month = mar,

doi = "10.1103/PhysRevA.95.032323",

language = "English",

volume = "95",

journal = "Physical Review A",

issn = "2469-9926",

publisher = "American Physical Society (APS)",

number = "3",

}

TY - JOUR

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

AU - Moylett, Dominic J.

AU - Linden, Noah

AU - Montanaro, Ashley

PY - 2017/3

Y1 - 2017/3

N2 - 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.

AB - 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.

KW - Quantum Algorithms

KW - Quantum Information

KW - Computer Science

UR - https://arxiv.org/abs/1612.06203

U2 - 10.1103/PhysRevA.95.032323

DO - 10.1103/PhysRevA.95.032323

M3 - Article (Academic Journal)

SN - 2469-9926

VL - 95

JO - Physical Review A

JF - Physical Review A

IS - 3

M1 - 032323

ER -

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

Abstract

Research Groups and Themes

Keywords

Access to Document

Handle.net

Other files and links

Fingerprint

Quantum speedup of the Travelling Salesman Problem for bounded-degree graphs

New insights in quantum algorithms and complexity

New insights in quantum algorithms and complexity

Towards a Quantum Speedup via Applications and Architectures

Professor Noah Linden

Cite this

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

Abstract

Research Groups and Themes

Keywords

Access to Document

Handle.net

Other files and links

Fingerprint

Research output

Quantum speedup of the Travelling Salesman Problem for bounded-degree graphs

Projects

New insights in quantum algorithms and complexity

New insights in quantum algorithms and complexity

Student theses

Towards a Quantum Speedup via Applications and Architectures

Profiles

Professor Noah Linden

Cite this