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.
|Titolo:||Quantum annealing of the Traveling Salesman Problem|
|Autori:||ROMAN MARTONAK; GIUSEPPE E. SANTORO; ERIO TOSATTI|
|Data di pubblicazione:||2004|
|Digital Object Identifier (DOI):||10.1103/PhysRevE.70.057701|
|Appare nelle tipologie:||1.1 Journal article|