Solving the traveling salesman problem on a quantum annealer

Matthias Troyer, Bettina Heim, Ethan Brown +1 more

Florian Klug

Luke Ellert-Beck, Michael J. Lawler, Samuel Gosin

Alexander Sauer, Sebastian Luhn, Jannes Weghake

At land, sea and in the air mobility and traffic management offer a vast amount of problems with a large potential of optimization with quantum computers, e.g. service scheduling, route planning, or path optimization. Many of these problems can be described at a fundamental level by the traveling salesman problem (TSP), in which the shortest route while visiting each point exactly once is to be found [1]. The TSP has already received a lot of attention in the quantum computing community, for example, implementations for adiabatic quantum annealers exist and have been tested [2,3]. We investigate the TSP with a focus on going beyond qubits by employing continuous quantum systems. Using bosonic Qiskit we simulate potential algorithms for solving the TSP and compare their performance. [1] Flood, M. M., The traveling-salesman problem. Operations research, 4(1), 61-75, (1956). [2] Martoňák, Roman, Giuseppe E. Santoro, and Erio Tosatti., Quantum annealing of the traveling-salesman problem. Physical Review E 70.5: 057701, (2004). [3] Jain, S., Solving the traveling salesman problem on the d-wave quantum computer. Frontiers in Physics, 646, (2021).

Hans R. Moser

Alessia Ciacco, Francesca Guerriero, Eneko Osaba

The Steiner Traveling Salesman Problem (STSP) is a variant of the classical Traveling Salesman Problem. The STSP involves incorporating steiner nodes, which are extra nodes not originally part of the required visit set but that can be added to the route to enhance the overall solution and minimize the total travel cost. Given the NP-hard nature of the STSP, we propose a quantum approach to address it. Specifically, we employ quantum annealing using D-Wave's hardware to explore its potential for solving this problem. To enhance computational feasibility, we develop a preprocessing method that effectively reduces the network size. Our experimental results demonstrate that this reduction technique significantly decreases the problem complexity, making the Quadratic Unconstrained Binary Optimization formulation, the standard input for quantum annealers, better suited for existing quantum hardware. Furthermore, the results highlight the potential of quantum annealing as a promising and innovative approach for solving the STSP.