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.
Quantum annealing of the traveling-salesman problem / Martoňák, R.; Santoro, G. E.; Tosatti, E.. - In: PHYSICAL REVIEW E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS. - ISSN 1539-3755. - 70:5(2004), pp. 057701.1-057701.4. [10.1103/PhysRevE.70.057701]
Quantum annealing of the traveling-salesman problem
Santoro, G. E.;Tosatti, E.
2004-01-01
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.| File | Dimensione | Formato | |
|---|---|---|---|
|
Martonak_TSP-PRE04.pdf
non disponibili
Licenza:
Non specificato
Dimensione
259.82 kB
Formato
Adobe PDF
|
259.82 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
