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• 2 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•1 citation

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 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•13 citations

Attention-Based Deep Reinforcement Learning for Qubit Allocation in Modular Quantum Architectures

Russo, Enrico, Maurizio Palesi, Davide Patti +2 more

Modular, distributed and multi-core architectures are currently considered a promising approach for scalability of quantum computing systems. The integration of multiple Quantum Processing Units necessitates classical and quantum-coherent communication, introducing challenges related to noise and quantum decoherence in quantum state transfers between cores. Optimizing communication becomes imperative, and the compilation and mapping of quantum circuits onto physical qubits must minimize state transfers while adhering to architectural constraints. The compilation process, inherently an NP-hard problem, demands extensive search times even with a small number of qubits to be solved to optimality. To address this challenge efficiently, we advocate for the utilization of heuristic mappers that can rapidly generate solutions. In this work, we propose a novel approach employing Deep Reinforcement Learning (DRL) methods to learn these heuristics for a specific multi-core architecture. Our DRL agent incorporates a Transformer encoder and Graph Neural Networks. It encodes quantum circuits using self-attention mechanisms and produce outputs through an attention-based pointer mechanism that directly signifies the probability of matching logical qubits with physical cores. This enables the selection of optimal cores for logical qubits efficiently. Experimental evaluations show that the proposed method can outperform baseline approaches in terms of reducing inter-core communications and minimizing online time-to-solution. This research contributes to the advancement of scalable quantum computing systems by introducing a novel learning-based heuristic approach for efficient quantum circuit compilation and mapping.

arXiv:2406.11452•Jun 17, 2024•10 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
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.
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.
Modular, distributed and multi-core architectures are currently considered a promising approach for scalability of quantum computing systems. The integration of multiple Quantum Processing Units necessitates classical and quantum-coherent communication, introducing challenges related to noise and quantum decoherence in quantum state transfers between cores. Optimizing communication becomes imperative, and the compilation and mapping of quantum circuits onto physical qubits must minimize state transfers while adhering to architectural constraints. The compilation process, inherently an NP-hard problem, demands extensive search times even with a small number of qubits to be solved to optimality. To address this challenge efficiently, we advocate for the utilization of heuristic mappers that can rapidly generate solutions. In this work, we propose a novel approach employing Deep Reinforcement Learning (DRL) methods to learn these heuristics for a specific multi-core architecture. Our DRL agent incorporates a Transformer encoder and Graph Neural Networks. It encodes quantum circuits using self-attention mechanisms and produce outputs through an attention-based pointer mechanism that directly signifies the probability of matching logical qubits with physical cores. This enables the selection of optimal cores for logical qubits efficiently. Experimental evaluations show that the proposed method can outperform baseline approaches in terms of reducing inter-core communications and minimizing online time-to-solution. This research contributes to the advancement of scalable quantum computing systems by introducing a novel learning-based heuristic approach for efficient quantum circuit compilation and mapping.
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.