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

arXiv:2407.13616 · International Conference on Quantum Communications, Networking, and Computing (QCNC)

Quantum Local Search for Traveling Salesman Problem with Path-Slicing Strategy

Chen-Yu Liu, Hiromichi Matsuyama, Wei‐Hao Huang, Yu Yamashiro

Published Mar 31, 2025• 1 citation
arXivHTMLPDF

Abstract

We present novel path-slicing strategies integrated with quantum local search to optimize solutions for the Traveling Salesman Problem (TSP), addressing the limitations of current Noisy Intermediate-Scale Quantum (NISQ) technologies. Our hybrid quantum-classical approach leverages classical path initialization and quantum optimization to effectively manage the computational challenges posed by the TSP. We explore various path slicing methods, including k-means and anti-k-means clustering, to divide the TSP into manageable subproblems. These are then solved using quantum or classical solvers. Our analysis, performed on multiple TSP instances from the TSPlib, demonstrates the ability of our strategies to achieve near-optimal solutions efficiently, highlighting significant improvements in solving efficiency and resource utilization. This approach paves the way for future applications in larger combinatorial optimization scenarios, advancing the field of quantum optimization.

DOI
10.1109/qcnc64685.2025.00110

Related papers

Tackling Traveling Salesman Problems with a Cluster-Based Quantum-Classical Optimization

Saweed Hussain, Lutfiana Sausan, Abdur Rahman +2 more

A hybrid quantum-classical framework is exploited to solve the Traveling Salesman Problem (TSP) based on a Quantum Approximate Optimization Algorithm (QAOA). To overcome the computational limitation of the Grover’s Search Algorithm (GSA) stemming from path encoding and arithmetic subroutines, a clustering-based strategy is employed to decompose a 16-city TSP into four 4-city subproblems, each of which can be solved with a 16-qubit budget. Intra-cluster solutions are optimized with QAOA, and are classically stitched to construct the global tour. Our results clearly validate the effectiveness of the hierarchical design of the algorithm, highlighting its feasibility for mid-scale quantum optimizations.

International Conference on Information and Communication Technology Convergence (ICTC)•Oct 14, 2025•0 citations

Evolutionary Algorithm for the Traveling Salesman Problem With Innovative Encoding on Hybrid Quantum-Classical Machines

Ravi Saini, Ashish Mani, Mani Shankar Prasad +2 more

The Traveling Salesman Problem (TSP) is a widely studied NP-complete optimization challenge with significant theoretical and practical implications. This study proposes a hybrid quantum-classical framework using a Quantum-Inspired Evolutionary Algorithm (QEA) with Sort Gray Binary Encoding to solve the TSP. The proposed method guarantees the generation of valid TSP tours by eliminating invalid solutions. It employs quantum superposition with intrinsic randomness to enhance computational efficiency and scalability. The framework was implemented on cloud-based NISQ platforms, including IBM Quantum and AWS Braket, demonstrating its practicality and effectiveness. Experimental evaluations revealed that the proposed framework successfully solved TSP instances with up to 15 cities, achieving superior performance compared to classical methods and showcasing its ability to scale under NISQ constraints. The results also highlight the potential of hybrid quantum-classical approaches to overcome hardware limitations in current quantum systems. This study establishes a robust hybrid methodology for solving combinatorial optimization problems. It also sets a benchmark for leveraging the capabilities of NISQ-era quantum devices in real-world applications, thereby providing a foundation for future research in hybrid quantum-classical optimization techniques.

IEEE Access•Jan 1, 2025•4 citations

Scalable Hybrid Quantum-Classical Optimization for the Traveling Salesman Problem

Ziyue Wang, Zhiwei Ye, Gongsheng Yuan +4 more

We will propose QUOTA, a lightweight quantum algorithm designed to obtain optimal solutions for small-scale TSP instances, and SQUARE, a hybrid quantum-classical framework that scales TSP via a divide-and-conquer strategy. Working together, they efficiently solve subproblems while extending the capability of current NISQ devices to handle larger-scale instances.

Workshop on Quantum Computing and Quantum-Inspired Technology for Data-Intensive Systems and Applications (Q-Data)•May 31, 2026•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

Hybrid Quantum-Classical Optimisation of Traveling Salesperson Problem

Christos Lytrosyngounis, Ioannis Lytrosyngounis

The Traveling Salesperson Problem (TSP) is a fundamental NP-hard optimisation challenge with widespread applications in logistics, operations research, and network design. While classical algorithms effectively solve small to medium-sized instances, they struggle with scalability due to exponential complexity. In this work, we present a hybrid quantum-classical approach that leverages IBM's Qiskit Runtime to integrate quantum optimisation techniques with classical machine learning methods, specifically K-Means clustering and Random Forest classifiers. These machine learning components aid in problem decomposition and noise mitigation, improving the quality of quantum solutions. Experimental results for TSP instances ranging from 4 to 8 cities reveal that the quantum-only approach produces solutions up to 21.7% worse than the classical baseline, while the hybrid method reduces this cost increase to 11.3% for 8 cities. This demonstrates that hybrid approaches improve solution quality compared to purely quantum methods but remain suboptimal compared to classical solvers. Despite current hardware limitations, these results highlight the potential of quantum-enhanced methods for combinatorial optimisation, paving the way for future advancements in scalable quantum computing frameworks.

arXiv:2503.00219•Feb 28, 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
We present novel path-slicing strategies integrated with quantum local search to optimize solutions for the Traveling Salesman Problem (TSP), addressing the limitations of current Noisy Intermediate-Scale Quantum (NISQ) technologies. Our hybrid quantum-classical approach leverages classical path initialization and quantum optimization to effectively manage the computational challenges posed by the TSP. We explore various path slicing methods, including k-means and anti-k-means clustering, to divide the TSP into manageable subproblems. These are then solved using quantum or classical solvers. Our analysis, performed on multiple TSP instances from the TSPlib, demonstrates the ability of our strategies to achieve near-optimal solutions efficiently, highlighting significant improvements in solving efficiency and resource utilization. This approach paves the way for future applications in larger combinatorial optimization scenarios, advancing the field of quantum optimization.
A hybrid quantum-classical framework is exploited to solve the Traveling Salesman Problem (TSP) based on a Quantum Approximate Optimization Algorithm (QAOA). To overcome the computational limitation of the Grover’s Search Algorithm (GSA) stemming from path encoding and arithmetic subroutines, a clustering-based strategy is employed to decompose a 16-city TSP into four 4-city subproblems, each of which can be solved with a 16-qubit budget. Intra-cluster solutions are optimized with QAOA, and are classically stitched to construct the global tour. Our results clearly validate the effectiveness of the hierarchical design of the algorithm, highlighting its feasibility for mid-scale quantum optimizations.
The Traveling Salesman Problem (TSP) is a widely studied NP-complete optimization challenge with significant theoretical and practical implications. This study proposes a hybrid quantum-classical framework using a Quantum-Inspired Evolutionary Algorithm (QEA) with Sort Gray Binary Encoding to solve the TSP. The proposed method guarantees the generation of valid TSP tours by eliminating invalid solutions. It employs quantum superposition with intrinsic randomness to enhance computational efficiency and scalability. The framework was implemented on cloud-based NISQ platforms, including IBM Quantum and AWS Braket, demonstrating its practicality and effectiveness. Experimental evaluations revealed that the proposed framework successfully solved TSP instances with up to 15 cities, achieving superior performance compared to classical methods and showcasing its ability to scale under NISQ constraints. The results also highlight the potential of hybrid quantum-classical approaches to overcome hardware limitations in current quantum systems. This study establishes a robust hybrid methodology for solving combinatorial optimization problems. It also sets a benchmark for leveraging the capabilities of NISQ-era quantum devices in real-world applications, thereby providing a foundation for future research in hybrid quantum-classical optimization techniques.
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 Salesperson Problem (TSP) is a fundamental NP-hard optimisation challenge with widespread applications in logistics, operations research, and network design. While classical algorithms effectively solve small to medium-sized instances, they struggle with scalability due to exponential complexity. In this work, we present a hybrid quantum-classical approach that leverages IBM's Qiskit Runtime to integrate quantum optimisation techniques with classical machine learning methods, specifically K-Means clustering and Random Forest classifiers. These machine learning components aid in problem decomposition and noise mitigation, improving the quality of quantum solutions. Experimental results for TSP instances ranging from 4 to 8 cities reveal that the quantum-only approach produces solutions up to 21.7% worse than the classical baseline, while the hybrid method reduces this cost increase to 11.3% for 8 cities. This demonstrates that hybrid approaches improve solution quality compared to purely quantum methods but remain suboptimal compared to classical solvers. Despite current hardware limitations, these results highlight the potential of quantum-enhanced methods for combinatorial optimisation, paving the way for future advancements in scalable quantum computing frameworks.
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.