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

International Conference on Communications

Quantum Annealing Approach for Selective Traveling Salesman Problem

Thinh V. Le, Manh V. Nguyen, Sri Khandavilli, Thang N. Dinh, Tu N. Nguyen

Published May 28, 2023• 11 citations
Publisher

Abstract

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.

DOI
10.1109/icc45041.2023.10279785

Related papers

Steiner Traveling Salesman Problem with Quantum Annealing

Alessia Ciacco, Francesca Guerriero, Eneko Osaba

The Steiner Traveling Salesman Problem (STSP) is a variant of the classical Traveling Salesman Problem. The STSP involves incorporating steiner nodes, which are extra nodes not originally part of the required visit set but that can be added to the route to enhance the overall solution and minimize the total travel cost. Given the NP-hard nature of the STSP, we propose a quantum approach to address it. Specifically, we employ quantum annealing using D-Wave's hardware to explore its potential for solving this problem. To enhance computational feasibility, we develop a preprocessing method that effectively reduces the network size. Our experimental results demonstrate that this reduction technique significantly decreases the problem complexity, making the Quadratic Unconstrained Binary Optimization formulation, the standard input for quantum annealers, better suited for existing quantum hardware. Furthermore, the results highlight the potential of quantum annealing as a promising and innovative approach for solving the STSP.

arXiv:2504.02388•Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 14, 2025•2 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

Solving the Traveling Salesman Problem on the D-Wave Quantum Computer

Siddharth Jain

The traveling salesman problem is a well-known NP-hard problem in combinatorial optimization. This paper shows how to solve it on an Ising Hamiltonian based quantum annealer by casting it as a quadratic unconstrained binary optimization (QUBO) problem. Results of practical experiments are also presented using D-Wave’s 5,000 qubit Advantage 1.1 quantum annealer and the performance is compared to a classical solver. It is found the quantum annealer can only handle a problem size of 8 or less nodes and its performance is subpar compared to the classical solver both in terms of time and accuracy.

Frontiers in Physics•Nov 12, 2021•50 citations

Quantum Approaches to NP-Hard Combinatorial Optimization Problems: A Review

Charan Karnati, P. Venkata Subba Reddy

NP-hard problems are one of the most computationally intensive challenges in computer science, appearing in many domains such as logistics, cybersecurity, drug design, and financial modelling. Classical algorithms become impractical as problem size increases due to combinatorial explosion. This paper presents a structured framework for analysing quantum algorithms targeting NP-hard optimization problems, like the Traveling Salesman Problem (TSP), Max-Cut, and Boolean Satisfiability (SAT). We have developed a taxonomy which categorizes quantum approaches—quantum annealing, variational algorithms (QAOA/VQE), and Grover-based search—based on problem encoding strategies, resource requirements, and theoretical guarantees. From the comparative analysis of existing literature, we: 1) Map algorithm classes to problem domains (e.g., QAOA for Max-Cut, annealing for TSP) 2) Identify performance trade-offs between solution quality, qubit counts, and circuit depth 3) Analyse hardware compatibility constraints across NISQ platforms 4) Reveal fundamental scalability barriers including noise susceptibility and embedding overhead The framework establishes implementation guidelines for near- term quantum hardware and proposes hybrid quantum-classical pathways to bridge theoretical potential and practical deployment. This systematic analysis prioritizes research directions for achieving quantum advantage in combinatorial optimization.

•Aug 5, 2025•0 citations

Solving the traveling salesman problem via different quantum computing architectures

Venkat Aneesh Padmasola, zhuangbin li, Rupak Chatterjee +1 more

In this paper, we study the application of emerging photonic and quantum computing architectures to solving the Traveling Salesman Problem (TSP), a well-known NP-hard optimization problem. We investigate several approaches: Simulated Annealing (SA), Quadratic Unconstrained Binary Optimization (QUBO-Ising) methods implemented on quantum annealers and Optical Coherent Ising Machines, as well as the Quantum Approximate Optimization Algorithm (QAOA) and the Quantum Phase Estimation (QPE) algorithm on gate-based quantum computers. QAOA and QPE were tested on the IBM Quantum platform. The QUBO-Ising method was explored using the D-wave quantum annealer, which operates on superconducting Josephson junctions, and the Quantum Computing Inc (QCi) Dirac-1 entropy quantum optimization machine. Gate-based quantum computers demonstrated accurate results for small TSP instances in simulation. However, real quantum devices are hindered by noise and limited scalability. Circuit complexity grows with problem size, restricting performance to TSP instances with a maximum of six nodes. In contrast, Ising-based architectures show improved scalability for larger problem sizes. SQUID-based Ising machines can handle TSP instances with up to 12 nodes, while entropy computing implemented in hybrid optoelectronic components extend this capability to 18 nodes. Nevertheless, the solutions tend to be suboptimal due to hardware limitations and challenges in achieving ground state convergence as the problem size increases. Despite these limitations, Ising machines demonstrate significant time advantages over classical methods, making them a promising candidate for solving larger-scale TSPs efficiently.

arXiv:2502.17725•International Journal of Quantum Information•Oct 11, 2025•7 citations

Designing Adiabatic Quantum Optimization: A Case Study for the Traveling Salesman Problem

Bettina Heim, Ethan Brown, Dave Wecker +1 more

With progress in quantum technology more sophisticated quantum annealing devices are becoming available. While they offer new possibilities for solving optimization problems, their true potential is still an open question. As the optimal design of adiabatic algorithms plays an important role in their assessment, we illustrate the aspects and challenges to consider when implementing optimization problems on quantum annealing hardware based on the example of the traveling salesman problem (TSP). We demonstrate that tunneling between local minima can be exponentially suppressed if the quantum dynamics are not carefully tailored to the problem. Furthermore we show that inequality constraints, in particular, present a major hurdle for the implementation on analog quantum annealers. We finally argue that programmable digital quantum annealers can overcome many of these obstacles and can - once large enough quantum computers exist - provide an interesting route to using quantum annealing on a large class of problems.

arXiv:1702.06248•Feb 21, 2017•11 citations
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.
The Steiner Traveling Salesman Problem (STSP) is a variant of the classical Traveling Salesman Problem. The STSP involves incorporating steiner nodes, which are extra nodes not originally part of the required visit set but that can be added to the route to enhance the overall solution and minimize the total travel cost. Given the NP-hard nature of the STSP, we propose a quantum approach to address it. Specifically, we employ quantum annealing using D-Wave's hardware to explore its potential for solving this problem. To enhance computational feasibility, we develop a preprocessing method that effectively reduces the network size. Our experimental results demonstrate that this reduction technique significantly decreases the problem complexity, making the Quadratic Unconstrained Binary Optimization formulation, the standard input for quantum annealers, better suited for existing quantum hardware. Furthermore, the results highlight the potential of quantum annealing as a promising and innovative approach for solving the STSP.
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 is a well-known NP-hard problem in combinatorial optimization. This paper shows how to solve it on an Ising Hamiltonian based quantum annealer by casting it as a quadratic unconstrained binary optimization (QUBO) problem. Results of practical experiments are also presented using D-Wave’s 5,000 qubit Advantage 1.1 quantum annealer and the performance is compared to a classical solver. It is found the quantum annealer can only handle a problem size of 8 or less nodes and its performance is subpar compared to the classical solver both in terms of time and accuracy.
NP-hard problems are one of the most computationally intensive challenges in computer science, appearing in many domains such as logistics, cybersecurity, drug design, and financial modelling. Classical algorithms become impractical as problem size increases due to combinatorial explosion. This paper presents a structured framework for analysing quantum algorithms targeting NP-hard optimization problems, like the Traveling Salesman Problem (TSP), Max-Cut, and Boolean Satisfiability (SAT). We have developed a taxonomy which categorizes quantum approaches—quantum annealing, variational algorithms (QAOA/VQE), and Grover-based search—based on problem encoding strategies, resource requirements, and theoretical guarantees. From the comparative analysis of existing literature, we: 1) Map algorithm classes to problem domains (e.g., QAOA for Max-Cut, annealing for TSP) 2) Identify performance trade-offs between solution quality, qubit counts, and circuit depth 3) Analyse hardware compatibility constraints across NISQ platforms 4) Reveal fundamental scalability barriers including noise susceptibility and embedding overhead The framework establishes implementation guidelines for near- term quantum hardware and proposes hybrid quantum-classical pathways to bridge theoretical potential and practical deployment. This systematic analysis prioritizes research directions for achieving quantum advantage in combinatorial optimization.
In this paper, we study the application of emerging photonic and quantum computing architectures to solving the Traveling Salesman Problem (TSP), a well-known NP-hard optimization problem. We investigate several approaches: Simulated Annealing (SA), Quadratic Unconstrained Binary Optimization (QUBO-Ising) methods implemented on quantum annealers and Optical Coherent Ising Machines, as well as the Quantum Approximate Optimization Algorithm (QAOA) and the Quantum Phase Estimation (QPE) algorithm on gate-based quantum computers. QAOA and QPE were tested on the IBM Quantum platform. The QUBO-Ising method was explored using the D-wave quantum annealer, which operates on superconducting Josephson junctions, and the Quantum Computing Inc (QCi) Dirac-1 entropy quantum optimization machine. Gate-based quantum computers demonstrated accurate results for small TSP instances in simulation. However, real quantum devices are hindered by noise and limited scalability. Circuit complexity grows with problem size, restricting performance to TSP instances with a maximum of six nodes. In contrast, Ising-based architectures show improved scalability for larger problem sizes. SQUID-based Ising machines can handle TSP instances with up to 12 nodes, while entropy computing implemented in hybrid optoelectronic components extend this capability to 18 nodes. Nevertheless, the solutions tend to be suboptimal due to hardware limitations and challenges in achieving ground state convergence as the problem size increases. Despite these limitations, Ising machines demonstrate significant time advantages over classical methods, making them a promising candidate for solving larger-scale TSPs efficiently.
With progress in quantum technology more sophisticated quantum annealing devices are becoming available. While they offer new possibilities for solving optimization problems, their true potential is still an open question. As the optimal design of adiabatic algorithms plays an important role in their assessment, we illustrate the aspects and challenges to consider when implementing optimization problems on quantum annealing hardware based on the example of the traveling salesman problem (TSP). We demonstrate that tunneling between local minima can be exponentially suppressed if the quantum dynamics are not carefully tailored to the problem. Furthermore we show that inequality constraints, in particular, present a major hurdle for the implementation on analog quantum annealers. We finally argue that programmable digital quantum annealers can overcome many of these obstacles and can - once large enough quantum computers exist - provide an interesting route to using quantum annealing on a large class of problems.