Penalty-free Variational Quantum Algorithm Solves Travelling Salesman Problem with 29 Qubits and 12 Locations
Summarize this article with:
The Travelling Salesman Problem, a notoriously difficult challenge in logistics and optimisation, seeks the shortest route to visit a series of locations and return to the starting point. Daniel Goldsmith, Xing Liang, and Dimitrios Makris, from the University of Kingston, alongside Hongwei Wu, now demonstrate a significant advance in solving this problem using quantum computing. Their work presents high-quality solutions for networks containing up to twelve locations, a scale rarely achieved with existing quantum algorithms. By employing a penalty-free Variational Quantum Algorithm and innovative techniques to reduce computational demands, the team not only simulates these complex networks but also establishes a pathway towards tackling even larger instances, potentially revolutionising route optimisation for industries such as delivery services. The research showcases a clear advantage over classical machine learning approaches and suggests that quantum algorithms will become increasingly competitive as problem sizes grow. Both VQA and classical ML benefit from efficient exploration of the network’s state space, and caching mechanisms significantly improve performance. As network size increases, the challenge of exploring all possible solutions demands more computational resources and sophisticated exploration strategies. The research demonstrates that the number of input data points is crucial for classical ML performance, with increased points generally improving accuracy but also increasing computational cost. For smaller networks, the number of sampled solutions can exceed the total number of unique cycles, but this quickly changes as the network expands, leaving only a tiny fraction of cycles explored. Researchers successfully simulated networks containing up to twelve locations, a significant advancement given the challenges of applying quantum solutions to problems exceeding a dozen locations.
The team developed a VQA model that requires fewer qubits than conventional methods, scaling efficiently with network size, thanks to penalty-free formulations that map all possible solutions to valid TSP cycles. To optimise the VQA, scientists harnessed a powerful gradient estimation method, reducing computational time and accelerating calculations through cost-function caching. They also investigated techniques to refine optimisation, analysing the differentiability of the cost function and the impact of averaging over a subset of the lowest-cost solutions. A classical Monte Carlo benchmark provided a fair comparison, allowing researchers to evaluate the performance of quantum and classical optimisation strategies.
The team’s approach utilises a qubit count that scales efficiently with network size, requiring significantly fewer qubits than conventional methods. Experiments reveal that the VQA achieves high-quality solutions for networks of up to nine locations, demonstrating robustness even under simulated noisy conditions. Computational time was dramatically reduced through the implementation of a powerful gradient estimation method and cost-function caching. Detailed studies of different encoding strategies resulted in significant runtime reductions. Inspired by the VQA, researchers also developed a novel classical machine-learning model capable of solving larger TSP networks than currently accessible with quantum simulations. Simulations demonstrate the ability to solve instances of the problem involving up to twelve locations, a significant advancement given the difficulty of applying quantum solutions to networks beyond a dozen points. This work represents the first successful simulation of a twelve-location TSP using a circuit-model variational quantum algorithm.
The team’s approach utilises a hybrid quantum-classical method, reducing the number of qubits required compared to conventional methods, and accelerating computational time through advanced optimisation techniques and cost-function caching. A quantum-inspired classical machine learning model was also developed for benchmarking, and the quantum algorithm consistently outperformed this classical counterpart. While the quantum algorithm’s performance currently matches that of a Monte Carlo method for small networks, results suggest a clear pathway towards superior performance with larger, more complex problems when implemented on actual quantum hardware. 👉 More information 🗞 Solving larger Travelling Salesman Problem networks with a penalty-free Variational Quantum Algorithm 🧠 ArXiv: https://arxiv.org/abs/2512.06523 Tags: Rohail T. As a quantum scientist exploring the frontiers of physics and technology. My work focuses on uncovering how quantum mechanics, computing, and emerging technologies are transforming our understanding of reality. I share research-driven insights that make complex ideas in quantum science clear, engaging, and relevant to the modern world. Latest Posts by Rohail T.: Masas of the Calkin Algebra, Generated by Projections, Achieve Complete Classification under Continuum Hypothesis December 10, 2025 Semi-implicit Variational Inference Achieves Arbitrarily Small KL Error under Tail-Dominance Conditions December 10, 2025 Crsb Exhibits Strain-Controlled Metal-Insulator Transition, Unifying Flat-Band and Altermagnetic Physics December 10, 2025