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

Dom Moylett; Noah Linden; Ashley Montanaro

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

Dom Moylett, Noah Linden, Ashley Montanaro

Research output: Contribution to conference › Conference Poster › peer-review

123 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
Number of pages	1
Publication status	Unpublished - 4 Apr 2017
Event	Heilbronn Quantum Algorithms Day 2017 - HH Wills Physics Laboratory, Bristol, United Kingdom Duration: 4 Apr 2017 → … http://heilbronn.ac.uk/2017/01/26/quantum-algorithms-day-2017/

Workshop

Workshop	Heilbronn Quantum Algorithms Day 2017
Country/Territory	United Kingdom
City	Bristol
Period	4/04/17 → …
Internet address	http://heilbronn.ac.uk/2017/01/26/quantum-algorithms-day-2017/

Research Groups and Themes

QITG
Bristol Quantum Information Institute

Access to Document

Poster PDF (final published version)
This is the final presented version of the poster.
Final published version, 433 KB

Handle.net

Persistent link

1 Article (Academic Journal)

Quantum speedup of the traveling-salesman problem for bounded-degree graphs
Moylett, D. J., Linden, N. & Montanaro, A., Mar 2017, In: Physical Review A. 95, 3, 10 p., 032323.
Research output: Contribution to journal › Article (Academic Journal) › peer-review

Open Access
File
22 Citations (Scopus)

486 Downloads (Pure)

2 Participation in workshop, seminar, course

Physics Post-Graduate Research Conference
Moylett, D. J. (Participant)
10 May 2017
Activity: Participating in or organising an event types › Participation in workshop, seminar, course
Bristol Quantum Information Technology 2017
Moylett, D. J. (Participant)
5 Apr 2017 → 7 Apr 2017
Activity: Participating in or organising an event types › Participation in workshop, seminar, course

File

Cite this

@conference{7880c61150964a4a91ae7960ed0ee244,

title = "Quantum speedup of the Travelling 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.",

author = "Dom Moylett and Noah Linden and Ashley Montanaro",

year = "2017",

month = apr,

day = "4",

language = "English",

note = "Heilbronn Quantum Algorithms Day 2017 ; Conference date: 04-04-2017",

url = "http://heilbronn.ac.uk/2017/01/26/quantum-algorithms-day-2017/",

}

TY - CONF

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

AU - Moylett, Dom

AU - Linden, Noah

AU - Montanaro, Ashley

PY - 2017/4/4

Y1 - 2017/4/4

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.

M3 - Conference Poster

T2 - Heilbronn Quantum Algorithms Day 2017

Y2 - 4 April 2017

ER -

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

Abstract

Workshop

Research Groups and Themes

Access to Document

Handle.net

Fingerprint

Research output

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

Activities

Physics Post-Graduate Research Conference

Bristol Quantum Information Technology 2017

Cite this