A Magnetism-Inspired Quantum Algorithm to Solve the Traveling Salesman Problem

The Traveling Salesman Problem (TSP) is a standard example of an NP-hard problem in combinatorial optimization. Although many researchers are looking for faster classical algorithms to solve TSP, it has yet to receive much attention from the quantum community. Our approach uses the Variational Quantum Eigensolver algorithm with tunable Heisenberg exchange gates in our variational ansatz instead of the standard gate set. This choice is motivated by the ability of Heisenberg exchange gates to generate superpositions of permutations. The goal of this research is to compare the performance of this quantum circuit with an analogous classical circuit to investigate whether the quantum circuit has an inherent advantage over its classical counterpart in this variational algorithm. We have implemented the Heisenberg exchange gates using SWAPⁿ gates on a circuit with cyclic, nearest-neighbor connectivity in IBM's Qiskit library for a complete graph with 4 nodes, and we have evidence that, on average, the quantum algorithm descends into the optimal solution more quickly than the classical version for this simple case on the IBM QASM Simulator.