Quantum annealing of the traveling-salesman problem

We propose a path-integral Monte Carlo quantum annealing scheme for the symmetric traveling-salesman problem, based on a highly constrained Ising-like representation, and we compare its performance against standard thermal simulated annealing. The Monte Carlo moves implemented are standard, and consist in restructuring a tour by exchanging two links (two-opt moves). The quantum annealing scheme, even with a drastically simple form of kinetic energy, appears definitely superior to the classical one, when tested on a 1002-city instance of the standard TSPLIB.

Figure 1

(Color online) Left: Representation of an eight-city tour, with the corresponding matrix ${\widehat{T}}_{\mathrm{in}}$ and ${\widehat{U}}_{\mathrm{in}}={\widehat{T}}_{\mathrm{in}}+{\widehat{T}}_{\mathrm{in}}^t$. Right: The final tour obtained when a two-opt move is performed, with a whole section reversed (dotted line). The matrices ${\widehat{T}}_{\mathrm{fin}}$ and ${\widehat{U}}_{\mathrm{fin}}$ are shown, the circles indicating the entries that have been switched $(0\leftrightarrow 1)$ by the two-opt move. The dotted circles in ${\widehat{T}}_{\mathrm{fin}}$ are entries related to the trivial reversal of a section of the tour.

Figure 2

(Color online) Average residual excess length found after Monte Carlo annealing for a total time $\tau$ (in MC steps), for the $N=1002$ instance pr1002 of the TSPLIB. Notice how quantum annealing (QA) provides residual excess lengths decaying faster than classical annealing (SA).