  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.
