title: Quantum annealing of the traveling-salesman problem.
abstract: 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.
authors.affiliation: Computational Science, Department of Chemistry and Applied Biosciences, ETH Zürich, USI Campus, Via Giuseppe Buffi 13, CH-6900 Lugano, Switzerland.
authors.forename: Roman
authors.initials: R
authors.lastname: Martonák
authors.forename: Giuseppe E
authors.initials: GE
authors.lastname: Santoro
authors.forename: Erio
authors.initials: E
authors.lastname: Tosatti