Projects 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 

Article number  032323 
Number of pages  10 
Journal  Physical Review A 
Volume  95 
Issue number  3 
Early online date  22 Mar 2017 
DOIs  
Publication status  Published  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 travelingsalesman problem for boundeddegree graphs'. Together they form a unique fingerprint.
Projects
 2 Finished
Student Theses

Towards a Quantum Speedup via Applications and Architectures
Author: Moylett, A. E., 23 Jun 2020Supervisor: Linden, N. (Supervisor) & Turner, P. (Supervisor)
Student thesis: Doctoral Thesis › Doctor of Philosophy (PhD)
File
Profiles

Professor Noah Linden
 Fundamental Bioscience
 School of Mathematics  Professor of Theoretical Physics
 The Bristol Centre for Nanoscience and Quantum Information
 Applied Mathematics
 Quantum Information Theory
 Mathematical Physics
Person: Academic , Member