  This paper explores the application of Quadratic Unconstrained Binary
Optimization (QUBO) models in solving the Travelling Salesman Problem (TSP)
through Quantum Annealing algorithms and Graph Neural Networks. Quantum
Annealing (QA), a quantum-inspired optimization method that exploits quantum
tunneling to escape local minima, is used to solve QUBO formulations of TSP
instances on Coherent Ising Machines (CIMs). The paper also presents a novel
approach where QUBO is employed as a loss function within a GNN architecture
tailored for solving TSP efficiently. By leveraging GNN's capability to learn
graph representations, this method finds approximate solutions to TSP with
improved computational time compared to traditional exact solvers. The paper
details how to construct a QUBO model for TSP by encoding city visits into
binary variables and formulating constraints that guarantee valid tours. It
further discusses the implementation of QUBO-based Quantum Annealing algorithm
for TSP (QQA-TSP) and its feasibility demonstration using quantum simulation
platforms. In addition, it introduces a Graph Neural Network solution for TSP
(QGNN-TSP), which learns the underlying structure of the problem and produces
competitive solutions via gradient descent over a QUBO-based loss function. The
experimental results compare the performance of QQA-TSP against
state-of-the-art classical solvers such as dynamic programming, Concorde, and
Gurobi, while also presenting empirical outcomes from training and evaluating
QGNN-TSP on various TSP datasets. The study highlights the promise of combining
deep learning techniques with quantum-inspired optimization methods for solving
NP-hard problems like TSP, suggesting future directions for enhancing GNN
architectures and applying QUBO frameworks to more complex combinatorial
optimization tasks.
