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

The traveling-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.

Figure 1

Example backtracking trees, where $l_5$ is a leaf corresponding to a solution to a constraint satisfaction problem: panel (a) shows an example of a perfectly balanced backtracking tree, where each leaf can be associated with a three-bit string corresponding to a path to that leaf; panel (b) on the other hand shows an example of an unbalanced backtracking tree, where specifying a path to a leaf requires six bits.

Figure 2

An instance of the recursive step in Eppstein's backtracking algorithm for the TSP [8] for a subgraph of a larger graph $G$, with forced edges displayed in bold and branching on edge $bc$. If we force $bc$, then $b$ and $c$ are both incident to two forced edges, so $bd$ and $ci$ cannot be part of the Hamiltonian cycle and can be removed from the graph. After these edges are removed, vertices $i$ and $d$ are both of degree 2, so in order to reach those vertices the edges $hi,ij,df$, and $dg$ must also be included in the Hamiltonian cycle. So forcing $bc$ has overall added five edges to the Hamiltonian cycle. On the other hand, if we remove edge $bc$, we find that $b$ and $c$ are vertices of degree 2, so edges $bd$ and $ci$ must be part of the Hamiltonian cycle. Thus we have only added two more edges to the Hamiltonian cycle.

Figure 3

Breaking a vertex of degree 5 or 6 into two lower-degree vertices. In the degree-5 case, dashed edge $f$ is not present and the vertex is split into one vertex of degree 3 and another of degree 4 connected by a forced edge in bold. In the degree-6 case, dashed edge $f$ is present and the vertex is split into two vertices of degree 4 connected by a forced edge. If edges $a$ and $b$ are included in the original graph's shortest Hamiltonian cycle, then they must not be adjacent to one another in the final graph. This holds in six of the ten ways of splitting the vertex.