Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Cross Strait Radio Science and Wireless Technology Conference (CSRSWTC)

Solving the Traveling Salesman Problem with Quantum Self-Attention Networks

Hao Li, Yue Ruan

Published Nov 4, 2024• 0 citations
Publisher

Abstract

The Traveling Salesman Problem (TSP), a well-known NP-hard problem, has intrigued computer scientists and mathematicians for over two centuries. In recent years, end-to-end deep reinforcement learning algorithms have been increasingly employed to tackle the TSP. However, these algorithms typically rely on classical neural networks, which face challenges such as a high number of training parameters and the necessity for large training datasets. This paper proposes a novel approach that integrates quantum computing with transformer modeling to address these challenges. By utilizing variational quantum circuits within the encoder and employing a quantum self-attentive neural network, we train the model using deep reinforcement learning algorithms. Experimental results on benchmark datasets demonstrate that the quantum self-attentive neural network model significantly outperforms existing classical neural network models. This new approach not only substantially reduces the number of training parameters and the size of the training dataset while solving the TSP problem, but also achieves superior optimization results compared to classical neural networks.

DOI
10.1109/csrswtc64338.2024.10811473

Related papers

Quantum-Inspired Deep Reinforcement Learning for Solving the Traveling Salesman Problem

Qianqian Liu, Jiahong Rui, Yue Ruan

The Traveling Salesman Problem (TSP), a well-known NP-hard optimization problem, has been widely studied for decades due to its broad practical applicability. In recent years, deep learning methods have shown promise in solving TSP; however, existing approaches often struggle to extract informative edge features between cities, which limits solution quality. To address this, we propose a Quantum-Inspired Deep Learning (QIDL) model that enhances node representations through quantum-inspired embedding, integrates Euclidean distance into the Transformer to strengthen spatial reasoning, and employs a quantum-inspired pointer network to replace greedy decoding with global optimization search. Experimental results demonstrate that QIDL outperforms traditional pointer networks, achieving faster convergence, improved stability, and a 1.76% reduction in tour length, with strong performance on medium-scale TSP instances. These results highlight the potential of QIDL to open new avenues for quantum-inspired learning in combinatorial optimization.

Cross Strait Radio Science and Wireless Technology Conference (CSRSWTC)•Nov 14, 2025•0 citations

Vehicle Routing Problems via Quantum Graph Attention Network Deep Reinforcement Learning

Le Tung Giang, Vu Hoang Viet, Nguyen Xuan Tung +2 more

The vehicle routing problem (VRP) is a fundamental NP-hard task in intelligent transportation systems with broad applications in logistics and distribution. Deep reinforcement learning (DRL) with Graph Neural Networks (GNNs) has shown promise, yet classical models rely on large multi-layer perceptrons (MLPs) that are parameter-heavy and memory-bound. We propose a Quantum Graph Attention Network (Q-GAT) within a DRL framework, where parameterized quantum circuits (PQCs) replace conventional MLPs at critical readout stages. The hybrid model maintains the expressive capacity of graph attention encoders while reducing trainable parameters by more than 50%. Using proximal policy optimization (PPO) with greedy and stochastic decoding, experiments on VRP benchmarks show that Q-GAT achieves faster convergence and reduces routing cost by about 5% compared with classical GAT baselines. These results demonstrate the potential of PQC-enhanced GNNs as compact and effective solvers for large-scale routing and logistics optimization.

cs.LGCross-listedarXiv:2511.15175•Nov 20, 2025•0 citations

Quantum Self-Organizing Map for Solving the Euclidean Traveling Salesman Problem

Rui XU, Jean-Charles Créput

Hybrid quantum-classical algorithms are the subject of intensive research in quantum computing and specifically in the domains of Machine Learning and Approximate Optimization. Simple distance-based learning classifiers such as kNN or k-means classifiers have already been the subject of many proposals, but most of their quantum implementation only consider a very small number of classes/clusters and only use metrics suitable for normalized unit length quantum data. Very few approaches combine the need for Euclidean distance of unnormalized data with an efficient quantum computation implementation. Based on two kNN and k-means proposals from the literature, this paper proposes their adaptation to the design of a Quantum Self-Organizing Map in order to solve the NP-hard Traveling Salesman Optimization Problem (TSP) specifically. Hence, we evaluate the hybrid quantum-classical approach to Euclidean TSP instances of sizes from 52 to 127 cities and present the properties, advantages, and limitations of the quantum implementation in solving the TSP optimization problem.

International Conference on Control, Decision and Information Technologies (CoDIT)•Jul 15, 2025•1 citation

Quantum iterative approach to the Traveling Salesman Problem

Arturo Rodríguez-Almazán, Guillermo Rivas, Ricardo S. Alonso +2 more

The Traveling Salesman Problem (TSP) is a classical NP-hard problem in combinatorial optimization, where determining the shortest route among a set of cities becomes computationally prohibitive as the problem size increases. This work explores quantum computing as an alternative approach to address this complexity. Unlike existing methods that primarily rely on quantum annealing, we propose a quantum iterative framework integrating Quantum Phase Estimation (QPE) and Grover's search algorithm. Route costs are encoded as quantum phases, enabling QPE to efficiently evaluate them, while Amplitude Amplification, implemented via the Grover-Long algorithm, iteratively refines the solution space toward the optimal route. A proof-of-concept case study on a small-scale TSP instance demonstrates the feasibility of this approach and its potential for scaling to larger optimization problems. Furthermore, under an expectation-based analysis, the algorithm exhibits an expected computational complexity of $O(\frac{m^2\log_2(m)\log_2(1/ε)}{\sqrtε})$ which depends on the error tolerance parameter $ε$. This estimation omits the initialization term, which we expect future refinements to render subdominant to Phase Estimation.

quant-pharXiv:2606.11843•Physica Scripta•Jun 11, 2026•0 citations

Quantum Annealing Approach for Selective Traveling Salesman Problem

Thinh V. Le, Manh V. Nguyen, Sri Khandavilli +2 more

Quantum computing has paved a new way for faster and more efficient solutions to large-scale, real-world optimization problems that are challenging for classical computing systems. For instance, selective traveling salesman problem (sTSP) that is famous in such fields as logistic optimization and has attracted increasing attention from the research community, however, is known as an NP-Hard problem. Solving the sTSP is, therefore, extremely complex because the optimization function potentially comes with an exponential number of variables that cannot be solved in polynomial time in general. To this end, we propose a quantum annealing framework for time-bounded and near-optimal solutions for the sTSP, overcoming hardware limits of near-term quantum devices. In particular, we put forth an efficient Hamiltonian (QUBO) to encode the complex decision-making for the sTSP on noisy intermediate-scale quantum (NISQ) annealer. Furthermore, experimental results we obtained on the D-Wave 2000$Q$quantum hardware demonstrate that the optimal solutions for several instances can be attained.

International Conference on Communications•May 28, 2023•11 citations

Quantum evolutionary algorithm for TSP combinatorial optimisation problem

Ma, Yijiang, Tan Chye Cheah

This paper implements a new way of solving a problem called the traveling salesman problem (TSP) using quantum genetic algorithm (QGA). We compared how well this new approach works to the traditional method known as a classical genetic algorithm (CGA). The TSP is a well-established challenge in combinatorial optimization where the objective is to find the most efficient path to visit a series of cities, minimizing the total distance, and returning to the starting point. We chose the TSP to test the performance of both algorithms because of its computational complexity and importance in practical applications. We choose the dataset from the international standard library TSPLIB for our experiments. By designing and implementing both algorithms and conducting experiments on various sizes and types of TSP instances, we provide an in-depth analysis of the accuracy of the optimal solution, the number of iterations, the execution time, and the stability of the algorithms for both. The empirical findings indicate that the CGA outperforms the QGA in terms of finding superior solutions more quickly in most of the test instances, especially when the problem size is large. This suggests that although the principle of quantum computing provides a new way to solve complex combinatorial optimisation problems, the implementation of quantum phenomena and the setting of parameters such as the optimal angle for a quantum revolving gate is challenging and need further optimisation to achieve the desired results. Additionally, it is important to note that the QGA has not been tested on real quantum hardware, so its true performance remains unverified. These limitations provide rich opportunities for further research in the future.

arXiv:2409.13788•Sep 20, 2024•0 citations
The Traveling Salesman Problem (TSP), a well-known NP-hard problem, has intrigued computer scientists and mathematicians for over two centuries. In recent years, end-to-end deep reinforcement learning algorithms have been increasingly employed to tackle the TSP. However, these algorithms typically rely on classical neural networks, which face challenges such as a high number of training parameters and the necessity for large training datasets. This paper proposes a novel approach that integrates quantum computing with transformer modeling to address these challenges. By utilizing variational quantum circuits within the encoder and employing a quantum self-attentive neural network, we train the model using deep reinforcement learning algorithms. Experimental results on benchmark datasets demonstrate that the quantum self-attentive neural network model significantly outperforms existing classical neural network models. This new approach not only substantially reduces the number of training parameters and the size of the training dataset while solving the TSP problem, but also achieves superior optimization results compared to classical neural networks.
The Traveling Salesman Problem (TSP), a well-known NP-hard optimization problem, has been widely studied for decades due to its broad practical applicability. In recent years, deep learning methods have shown promise in solving TSP; however, existing approaches often struggle to extract informative edge features between cities, which limits solution quality. To address this, we propose a Quantum-Inspired Deep Learning (QIDL) model that enhances node representations through quantum-inspired embedding, integrates Euclidean distance into the Transformer to strengthen spatial reasoning, and employs a quantum-inspired pointer network to replace greedy decoding with global optimization search. Experimental results demonstrate that QIDL outperforms traditional pointer networks, achieving faster convergence, improved stability, and a 1.76% reduction in tour length, with strong performance on medium-scale TSP instances. These results highlight the potential of QIDL to open new avenues for quantum-inspired learning in combinatorial optimization.
The vehicle routing problem (VRP) is a fundamental NP-hard task in intelligent transportation systems with broad applications in logistics and distribution. Deep reinforcement learning (DRL) with Graph Neural Networks (GNNs) has shown promise, yet classical models rely on large multi-layer perceptrons (MLPs) that are parameter-heavy and memory-bound. We propose a Quantum Graph Attention Network (Q-GAT) within a DRL framework, where parameterized quantum circuits (PQCs) replace conventional MLPs at critical readout stages. The hybrid model maintains the expressive capacity of graph attention encoders while reducing trainable parameters by more than 50%. Using proximal policy optimization (PPO) with greedy and stochastic decoding, experiments on VRP benchmarks show that Q-GAT achieves faster convergence and reduces routing cost by about 5% compared with classical GAT baselines. These results demonstrate the potential of PQC-enhanced GNNs as compact and effective solvers for large-scale routing and logistics optimization.
Hybrid quantum-classical algorithms are the subject of intensive research in quantum computing and specifically in the domains of Machine Learning and Approximate Optimization. Simple distance-based learning classifiers such as kNN or k-means classifiers have already been the subject of many proposals, but most of their quantum implementation only consider a very small number of classes/clusters and only use metrics suitable for normalized unit length quantum data. Very few approaches combine the need for Euclidean distance of unnormalized data with an efficient quantum computation implementation. Based on two kNN and k-means proposals from the literature, this paper proposes their adaptation to the design of a Quantum Self-Organizing Map in order to solve the NP-hard Traveling Salesman Optimization Problem (TSP) specifically. Hence, we evaluate the hybrid quantum-classical approach to Euclidean TSP instances of sizes from 52 to 127 cities and present the properties, advantages, and limitations of the quantum implementation in solving the TSP optimization problem.
The Traveling Salesman Problem (TSP) is a classical NP-hard problem in combinatorial optimization, where determining the shortest route among a set of cities becomes computationally prohibitive as the problem size increases. This work explores quantum computing as an alternative approach to address this complexity. Unlike existing methods that primarily rely on quantum annealing, we propose a quantum iterative framework integrating Quantum Phase Estimation (QPE) and Grover's search algorithm. Route costs are encoded as quantum phases, enabling QPE to efficiently evaluate them, while Amplitude Amplification, implemented via the Grover-Long algorithm, iteratively refines the solution space toward the optimal route. A proof-of-concept case study on a small-scale TSP instance demonstrates the feasibility of this approach and its potential for scaling to larger optimization problems. Furthermore, under an expectation-based analysis, the algorithm exhibits an expected computational complexity of O(m2log⁡2(m)log⁡2(1/ε)ε)O(\frac{m^2\log_2(m)\log_2(1/ε)}{\sqrtε})O(ε​m2log2​(m)log2​(1/ε)​) which depends on the error tolerance parameter εεε. This estimation omits the initialization term, which we expect future refinements to render subdominant to Phase Estimation.
Quantum computing has paved a new way for faster and more efficient solutions to large-scale, real-world optimization problems that are challenging for classical computing systems. For instance, selective traveling salesman problem (sTSP) that is famous in such fields as logistic optimization and has attracted increasing attention from the research community, however, is known as an NP-Hard problem. Solving the sTSP is, therefore, extremely complex because the optimization function potentially comes with an exponential number of variables that cannot be solved in polynomial time in general. To this end, we propose a quantum annealing framework for time-bounded and near-optimal solutions for the sTSP, overcoming hardware limits of near-term quantum devices. In particular, we put forth an efficient Hamiltonian (QUBO) to encode the complex decision-making for the sTSP on noisy intermediate-scale quantum (NISQ) annealer. Furthermore, experimental results we obtained on the D-Wave 2000QQQquantum hardware demonstrate that the optimal solutions for several instances can be attained.
This paper implements a new way of solving a problem called the traveling salesman problem (TSP) using quantum genetic algorithm (QGA). We compared how well this new approach works to the traditional method known as a classical genetic algorithm (CGA). The TSP is a well-established challenge in combinatorial optimization where the objective is to find the most efficient path to visit a series of cities, minimizing the total distance, and returning to the starting point. We chose the TSP to test the performance of both algorithms because of its computational complexity and importance in practical applications. We choose the dataset from the international standard library TSPLIB for our experiments. By designing and implementing both algorithms and conducting experiments on various sizes and types of TSP instances, we provide an in-depth analysis of the accuracy of the optimal solution, the number of iterations, the execution time, and the stability of the algorithms for both. The empirical findings indicate that the CGA outperforms the QGA in terms of finding superior solutions more quickly in most of the test instances, especially when the problem size is large. This suggests that although the principle of quantum computing provides a new way to solve complex combinatorial optimisation problems, the implementation of quantum phenomena and the setting of parameters such as the optimal angle for a quantum revolving gate is challenging and need further optimisation to achieve the desired results. Additionally, it is important to note that the QGA has not been tested on real quantum hardware, so its true performance remains unverified. These limitations provide rich opportunities for further research in the future.