In this paper we present a variational algorithm for the Traveling Salesman Problem (TSP) that combines (i) a compact encoding of permutations, which reduces the qubit requirement too, (ii) an optimize-freeze-reuse strategy: where the circuit topology (``Ansatz'') is first optimized on a training instance by Simulated Annealing (SA), then ``frozen'' and re-used on novel instances, limited to a rapid re-optimization of only the circuit parameters. This pipeline eliminates costly structural research in testing, making the procedure immediately implementable on NISQ hardware. On a set of
40 randomly generated symmetric instances that span
4−7 cities, the resulting Ansatz achieves an average optimal trip sampling probability of
100% for 4 city cases,
90% for 5 city cases and
80% for 6 city cases. With 7 cities the success rate drops markedly to an average of
∼20%, revealing the onset of scalability limitations of the proposed method. The results show robust generalization ability for moderate problem sizes and indicate how freezing the Ansatz can dramatically reduce time-to-solution without degrading solution quality. The paper also discusses scalability limitations, the impact of ``warm-start'' initialization of parameters, and prospects for extension to more complex problems, such as Vehicle Routing and Job-Shop Scheduling.
In this paper we present a variational algorithm for the Traveling Salesman Problem (TSP) thatcombines (i) a compact encoding of permutations, which reduces the qubit requirement too, (ii) anoptimize-freeze-reuse strategy: where the circuit topology (“Ansatz”) is first optimized on a train-ing instance by Simulated Annealing (SA), then “frozen” and re-used on novel instances, limitedto a rapid re-optimization of only the circuit parameters. This pipeline eliminates costly structuralresearch in testing, making the procedure immediately implementable on NISQ hardware.On a set of 40 randomly generated symmetric instances that span 4 − 7 cities, the resultingAnsatz achieves an average optimal trip sampling probability of 100% for 4 city cases, 90% for 5city cases and 80% for 6 city cases. With 7 cities the success rate drops markedly to an average of∼ 20%, revealing the onset of scalability limitations of the proposed method.The results show robust generalization ability for moderate problem sizes and indicate howfreezing the Ansatz can dramatically reduce time-to-solution without degrading solution quality.The paper also discusses scalability limitations, the impact of “warm-start” initialization of pa-rameters, and prospects for extension to more complex problems, such as Vehicle Routing andJob-Shop Scheduling.
A classical algorithm is tested against D-Wave hybrid quantum annealers for special cases of the Traveling Salesman Problem where the weights of the edges in a graph form an arithmetic progression. The classical algorithm, Christofides, Nearest Neighbor, Simulated Annealing, Ant Colony Optimization, Genetic Algorithm, and D-Wave hybrid quantum annealers are also tested on the Euclidean Traveling Salesman Problem. D-Wave never outperformed the classical algorithm within its specified scope but outperformed all classical algorithms and heuristics for the Euclidean Traveling Salesman Problem before being overtaken at larger problem sizes.