aiqbench analysis
This study demonstrates a significant breakthrough in scaling variational quantum algorithms to solve larger instances of the Travelling Salesman Problem on gate-based hardware, achieving superior solution quality over classical heuristics and ML baselines for networks up to 17 locations. By utilizing a compact penalty-free formulation and gradient-free optimization, the approach reduces qubit requirements and runtime while maintaining high accuracy without relying on penalty terms that often hinder convergence. Although it does not yet outperform strong classical solvers, this work establishes a new benchmark for hybrid quantum-classical workflows in combinatorial optimization, highlighting the potential of VQAs to tackle industrially relevant NP-hard problems as hardware capabilities expand.
Solving larger Travelling Salesman Problem networks with a penalty-free Variational Quantum Algorithm
arXiv:2512.06523v2 Announce Type: replace Abstract: 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
Abstract: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
60 pages and 11 figures. Up-versioned to show simulation results for larger networks using Qiskit Matrix Product State (MPS) simulator and runs from real hardware using Rigetti Cepheus
arXiv:2512.06523 [quant-ph]
(or arXiv:2512.06523v2 [quant-ph] for this version)
Full text under the publisher's open licence · 227 words
Related coverage
Solving the traveling salesman problem on $\lceil \log_2 (N-1)! \rceil$ qubits with a variational quantum Kolmogorov--Arnold network: exact-gradient CVaR training and generalization over time-dependent graphs
arXiv · Oct 15, 2026
AlphaEvolve: How our Gemini-powered coding agent is scaling impact across fields
Google DeepMind · May 6, 2026
News Archive 2026
Quantum Computing Report · Jul 25, 2026
Graph Neural Network-based Algorithm Selection for the Traveling Salesman Problem: A Systematic Study of Cost and Rank Losses under Distinct Budget Regimes
arXiv · Jul 22, 2026