Activities per year
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 higherdegree 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/quantumalgorithmsday2017/ 
Workshop
Workshop  Heilbronn Quantum Algorithms Day 2017 

Country  United Kingdom 
City  Bristol 
Period  4/04/17 → … 
Internet address 
Structured keywords
 QITG
 Bristol Quantum Information Institute
Fingerprint
Dive into the research topics of 'Quantum speedup of the Travelling Salesman Problem for boundeddegree graphs'. Together they form a unique fingerprint.Activities
 2 Participation in workshop, seminar, course

Physics PostGraduate Research Conference
Dom J Moylett (Participant)
10 May 2017Activity: Participating in or organising an event types › Participation in workshop, seminar, course

Bristol Quantum Information Technology 2017
Dom J Moylett (Participant)
5 Apr 2017 → 7 Apr 2017Activity: Participating in or organising an event types › Participation in workshop, seminar, course
File