A Hybrid Classical-Quantum Annealing Algorithm for the TSP
For researchers in quantum optimization, this is an incremental hybrid approach that addresses current quantum hardware limitations.
The paper proposes a hybrid classical-quantum annealing algorithm for the Traveling Salesperson Problem (TSP) that uses graph contraction to reduce problem size for quantum devices. The method is demonstrated on classical simulation and a D-Wave quantum annealer, but no concrete performance numbers are provided.
Hybrid quantum-classical algorithms can help mitigating the physical limitations of current quantum devices, particularly the low qubit count and the reduced topological connectivity. In this paper, we propose a hybrid technique to solve a well-known NP-hard optimization problem: the Traveling Salesperson Problem (TSP). Our approach is based on a graph contraction technique that removes most of the dimensionality of the original problem instance, producing a sub-TSP of a size suitable to be efficiently solved by a quantum device. The performance of our approach is first demonstrated on classical quantum simulation using Path Integral Monte Carlo, and then run on a D-Wave quantum annealer.