Evaluating quantum-classical heuristics for traveling salesman problem

Abstract

In this paper, we develop and evaluate a hybrid quantum-classical heuristic approach to solving the Traveling Salesman Problem. This approach uses exhaustive enumeration of the starting paths and optimizes the remainder of the route using quantum computing. For quantum co-processing, we use either the Variational Quantum Eigensolver or the Quantum Annealing. Results of evaluation of the approach on several datasets including TSPLIB and touristic data for Petrozavodsk and Karelia Republic, both in simulation and in hardware, are presented. Issues of practical applicability are also discussed.

Keywords

• hybrid quantum-classical heuristics
• traveling salesman problem
• variational quantum eigensolver
• quantum annealing