Quantum Annealing and GNN for Solving TSP with QUBO

This paper investigates the application of Quadratic Unconstrained Binary Optimization (QUBO) models for solving the Travelling Salesman Problem (TSP) using Quantum Annealing (QA) and Graph Neural Networks (GNNs). Quantum Annealing leverages quantum tunneling to escape local minima, solving QUBO formulations of TSP on Coherent Ising Machines (CIMs). Additionally, we introduce a novel method that integrates QUBO as a loss function within a GNN framework tailored for TSP. By exploiting GNNs’ capability to learn graph representations, this approach efficiently approximates TSP solutions with improved computational time over traditional exact solvers. We detail the construction of a QUBO model for TSP, encoding city visits into binary variables and formulating constraints to ensure valid tours. The implementation of the QUBO-based Quantum Annealing algorithm for TSP (QQA-TSP) is demonstrated using quantum simulation platforms. Furthermore, a solution for TSP (QGNN-TSP) is presented, which learns the problem’s structure and generates competitive solutions through gradient descent over a QUBO-based loss function. Experimental results show that QQA-TSP performs competitively with state-of-the-art classical solvers like dynamic programming, Concorde, and Gurobi. The QGNN-TSP approach is trained and evaluated on various TSP datasets, demonstrating efficiency and scalability. This study highlights the potential of combining deep learning with quantum-inspired optimization for solving NP-hard problems, suggesting future directions for enhancing GNN architectures and applying QUBO frameworks to more complex combinatorial optimization tasks.