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

Workshop on Quantum Computing and Quantum-Inspired Technology for Data-Intensive Systems and Applications (Q-Data)

Scalable Hybrid Quantum-Classical Optimization for the Traveling Salesman Problem

Ziyue Wang, Zhiwei Ye, Gongsheng Yuan, Mengying Zhu, Jiaye Li, Guanjie Cheng, Ling Qian

Published May 31, 2026• 0 citations
Publisher

Abstract

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.

DOI
10.1145/3811628.3811829

Related papers

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

Chen-Yu Liu, Hiromichi Matsuyama, Wei‐Hao Huang +1 more

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.

arXiv:2407.13616•International Conference on Quantum Communications, Networking, and Computing (QCNC)•Mar 31, 2025•1 citation

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

A Resource-Efficient Variational Quantum Framework for the Traveling Salesman Problem

Yuefeng Lin, Chao Zheng, Cong Guo

The Traveling Salesman Problem (TSP) is a prototypical combinatorial optimization problem, but its quantum implementation is limited by the O(n^2)-qubit overhead of standard one-hot encodings. Here, we propose a resource-efficient variational quantum framework based on compact binary-register encoding, a permutation-preserving problem-inspired ansatz, and a complementary divide-and-conquer execution strategy. The compact encoding reduces the data-qubit requirement to O(n log n), while the divide-and-conquer formulation lowers the number of qubits required in each local hardware execution to the size of the largest subsystem. Numerical simulations on TSP instances with 4, 5, and 6 cities achieve best average success rates of 100%, 100%, and 95.5%, respectively. A local two-qubit implementation of the divide-and-conquer approximation is further evaluated for a 5-city TSP instance on SpinQ Gemini Pro and SpinQ Triangulum II NMR quantum computers. Taken together, the results indicate how compact encoding and divide-and-conquer execution with classical post-processing can be used to study small combinatorial optimization instances on resource-constrained quantum hardware.

quant-pharXiv:2605.00739•May 4, 2026•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

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

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 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.
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.
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 prototypical combinatorial optimization problem, but its quantum implementation is limited by the O(n^2)-qubit overhead of standard one-hot encodings. Here, we propose a resource-efficient variational quantum framework based on compact binary-register encoding, a permutation-preserving problem-inspired ansatz, and a complementary divide-and-conquer execution strategy. The compact encoding reduces the data-qubit requirement to O(n log n), while the divide-and-conquer formulation lowers the number of qubits required in each local hardware execution to the size of the largest subsystem. Numerical simulations on TSP instances with 4, 5, and 6 cities achieve best average success rates of 100%, 100%, and 95.5%, respectively. A local two-qubit implementation of the divide-and-conquer approximation is further evaluated for a 5-city TSP instance on SpinQ Gemini Pro and SpinQ Triangulum II NMR quantum computers. Taken together, the results indicate how compact encoding and divide-and-conquer execution with classical post-processing can be used to study small combinatorial optimization instances on resource-constrained quantum hardware.
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
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 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.