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)

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

Qianqian Liu, Jiahong Rui, Yue Ruan

Published Nov 14, 2025• 0 citations
Publisher

Abstract

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.

DOI
10.1109/csrswtc67757.2025.11383891

Related papers

Solving the Traveling Salesman Problem with Quantum Self-Attention Networks

Hao Li, Yue Ruan

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.

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

Solving larger Travelling Salesman Problem networks with a penalty-free Variational Quantum Algorithm

Daniel Goldsmith, Xing Liang, Dimitrios Makris +1 more

The Travelling Salesman Problem (TSP) is a well-known NP-hard combinatorial optimisation problem with important industrial applications. Although extensively studied, quantum solutions for instances beyond a dozen locations remain uncommon. We present a hybrid penalty-free Variational Quantum Algorithm (VQA) that significantly reduces both the qubit count and the runtime through a compact penalty-free formulation scaling as $\mathcal{O}(nlog_2 n)$ qubits compared to conventional formulations with $\mathcal{O}(n^2)$ scaling. The VQA achieves solution qualities exceeding 90\% on Rigetti quantum hardware for instances of up to 17 locations. To the best of our knowledge, this represents the largest TSP instance solved on gate-based hardware. We systematically evaluate multiple encoding and optimisation strategies, and show that warm-start initialisation improves solution quality, while runtime is reduced by nearly two orders of magnitude through the use of gradient-free optimisation methods and cost-function caching. We additionally introduce a novel VQA inspired classical machine learning model (VQAi-CML) and benchmark the VQA against VQAi-CML, a greedy heuristic, a Monte Carlo baseline, and a strong classical optimisation baseline. Across the networks evaluated, the VQA consistently achieves superior solution quality relative to VQAi-CML, greedy heuristic, and Monte Carlo baselines, but not the classical solver

quant-pharXiv:2512.06523•Dec 9, 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 Approaches to Urban Logistics: From Core QAOA to Clustered Scalability

F. Picariello, G. Turati, R. Antonelli +10 more

The Traveling Salesman Problem (TSP) is a fundamental challenge in combinatorial optimization, widely applied in logistics and transportation. As the size of TSP instances grows, traditional algorithms often struggle to produce high-quality solutions within reasonable timeframes. This study investigates the potential of the Quantum Approximate Optimization Algorithm (QAOA), a hybrid quantum-classical method, to solve TSP under realistic constraints. We adopt a QUBO-based formulation of TSP that integrates real-world logistical constraints reflecting operational conditions, such as vehicle capacity, road accessibility, and time windows, while ensuring compatibility with the limitations of current quantum hardware. Our experiments are conducted in a simulated environment using high-performance computing (HPC) resources to assess QAOA's performance across different problem sizes and quantum circuit depths. In order to improve scalability, we propose clustering QAOA (Cl-QAOA), a hybrid approach combining classical machine learning with QAOA. This method decomposes large TSP instances into smaller sub-problems, making quantum optimization feasible even on devices with a limited number of qubits. The results offer a comprehensive evaluation of QAOA's strengths and limitations in solving constrained TSP scenarios. This study advances quantum optimization and lays groundwork for future large-scale applications.

quant-pharXiv:2512.10813•Dec 12, 2025•0 citations

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

Comparative Study of Variations in Quantum Approximate Optimization Algorithms for the Traveling Salesman Problem

Wenyang Qian, Robert Basili, Mary Mehrnoosh Eshaghian‐Wilner +3 more

The traveling salesman problem (TSP) is one of the most often-used NP-hard problems in computer science to study the effectiveness of computing models and hardware platforms. In this regard, it is also heavily used as a vehicle to study the feasibility of the quantum computing paradigm for this class of problems. In this paper, we tackle the TSP using the quantum approximate optimization algorithm (QAOA) approach by formulating it as an optimization problem. By adopting an improved qubit encoding strategy and a layer-wise learning optimization protocol, we present numerical results obtained from the gate-based digital quantum simulator, specifically targeting TSP instances with 3, 4, and 5 cities. We focus on the evaluations of three distinctive QAOA mixer designs, considering their performances in terms of numerical accuracy and optimization cost. Notably, we find that a well-balanced QAOA mixer design exhibits more promising potential for gate-based simulators and realistic quantum devices in the long run, an observation further supported by our noise model simulations. Furthermore, we investigate the sensitivity of the simulations to the TSP graph. Overall, our simulation results show that the digital quantum simulation of problem-inspired ansatz is a successful candidate for finding optimal TSP solutions.

arXiv:2307.07243•Entropy•Aug 21, 2023•41 citations
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 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 Travelling Salesman Problem (TSP) is a well-known NP-hard combinatorial optimisation problem with important industrial applications. Although extensively studied, quantum solutions for instances beyond a dozen locations remain uncommon. We present a hybrid penalty-free Variational Quantum Algorithm (VQA) that significantly reduces both the qubit count and the runtime through a compact penalty-free formulation scaling as O(nlog2n)\mathcal{O}(nlog_2 n)O(nlog2​n) qubits compared to conventional formulations with O(n2)\mathcal{O}(n^2)O(n2) scaling. The VQA achieves solution qualities exceeding 90\% on Rigetti quantum hardware for instances of up to 17 locations. To the best of our knowledge, this represents the largest TSP instance solved on gate-based hardware. We systematically evaluate multiple encoding and optimisation strategies, and show that warm-start initialisation improves solution quality, while runtime is reduced by nearly two orders of magnitude through the use of gradient-free optimisation methods and cost-function caching. We additionally introduce a novel VQA inspired classical machine learning model (VQAi-CML) and benchmark the VQA against VQAi-CML, a greedy heuristic, a Monte Carlo baseline, and a strong classical optimisation baseline. Across the networks evaluated, the VQA consistently achieves superior solution quality relative to VQAi-CML, greedy heuristic, and Monte Carlo baselines, but not the classical solver
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 fundamental challenge in combinatorial optimization, widely applied in logistics and transportation. As the size of TSP instances grows, traditional algorithms often struggle to produce high-quality solutions within reasonable timeframes. This study investigates the potential of the Quantum Approximate Optimization Algorithm (QAOA), a hybrid quantum-classical method, to solve TSP under realistic constraints. We adopt a QUBO-based formulation of TSP that integrates real-world logistical constraints reflecting operational conditions, such as vehicle capacity, road accessibility, and time windows, while ensuring compatibility with the limitations of current quantum hardware. Our experiments are conducted in a simulated environment using high-performance computing (HPC) resources to assess QAOA's performance across different problem sizes and quantum circuit depths. In order to improve scalability, we propose clustering QAOA (Cl-QAOA), a hybrid approach combining classical machine learning with QAOA. This method decomposes large TSP instances into smaller sub-problems, making quantum optimization feasible even on devices with a limited number of qubits. The results offer a comprehensive evaluation of QAOA's strengths and limitations in solving constrained TSP scenarios. This study advances quantum optimization and lays groundwork for future large-scale applications.
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.
The traveling salesman problem (TSP) is one of the most often-used NP-hard problems in computer science to study the effectiveness of computing models and hardware platforms. In this regard, it is also heavily used as a vehicle to study the feasibility of the quantum computing paradigm for this class of problems. In this paper, we tackle the TSP using the quantum approximate optimization algorithm (QAOA) approach by formulating it as an optimization problem. By adopting an improved qubit encoding strategy and a layer-wise learning optimization protocol, we present numerical results obtained from the gate-based digital quantum simulator, specifically targeting TSP instances with 3, 4, and 5 cities. We focus on the evaluations of three distinctive QAOA mixer designs, considering their performances in terms of numerical accuracy and optimization cost. Notably, we find that a well-balanced QAOA mixer design exhibits more promising potential for gate-based simulators and realistic quantum devices in the long run, an observation further supported by our noise model simulations. Furthermore, we investigate the sensitivity of the simulations to the TSP graph. Overall, our simulation results show that the digital quantum simulation of problem-inspired ansatz is a successful candidate for finding optimal TSP solutions.