Hybrid Quantum-Classical Optimisation of Traveling Salesperson Problem

• URL: http://arxiv.org/abs/2509.26229v1
• Date: Tue, 30 Sep 2025 13:26:12 GMT
• Title: Hybrid Quantum-Classical Optimisation of Traveling Salesperson Problem
• Abstract summary: We propose a hybrid quantum-classical framework integrating variational quantum eigensolver (VQE) optimisation with classical machine learning.<n>We evaluate the framework on 80 European cities via Qiskit's AerSimulator and ibm_kyiv 127-qubit backend.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Traveling Salesperson Problem (TSP), a quintessential NP-hard combinatorial optimisation challenge, is vital for logistics and network design but limited by exponential complexity in large instances. We propose a hybrid quantum-classical framework integrating variational quantum eigensolver (VQE) optimisation with classical machine learning, using K-means clustering for problem decomposition and a RandomForestRegressor for path refinement. Evaluated on 80 European cities (from 4 to 80 cities, 38,500 samples in total) via Qiskit's AerSimulator and ibm_kyiv 127-qubit backend, the hybrid approach outperforms quantum-only methods, achieving an approximation ratio of 1.0287 at 80 cities, a 47.5% improvement over quantum-only's 1.9614, nearing the classical baseline. Machine learning reduces variability in tour distances (interquartile range, IQR - the spread of the middle 50% of results relative to the median - from 0.06 to 0.04), enhancing stability despite noisy intermediate-scale quantum (NISQ) noise. This framework underscores hybrid strategies' potential for scalable TSP optimisation, with future hardware advancements promising practical quantum advantages.

Related papers

• A Hybrid Quantum-Classical Coordination Architecture for Portfolio Optimization via Global Context Injection [2.4660652494309936]
  Near-term quantum and quantum-inspired solvers for portfolio optimization rely on local subproblem execution under severe size constraints.<n>We propose Context-Aware Folding (CAF), a lightweight hybrid quantum-classical coordination layer between one-shot static decomposition and full-matrix optimization.<n>CAF injects a compressed global risk state into each local subproblem via a state-dependent linear bias, decouples local candidate generation from global commitment, and retains a sequential acceptance rule.
  arXiv  Detail & Related papers  (2026-09-14T15:12:22Z)
• Stochastic Pauli-path simulator for large-scale quantum optimization [57.179828941706006]
  Pauli-path simulators offer a promising route to large-scale classical simulation of quantum circuits in the low-magic regime.<n>Existing approaches either lack native support for gradient-based optimization or suffer from severe gradient bias.<n>Here we propose the Pauli-path simulator (SPPS), a computational framework for large-scale quantum optimization.
  arXiv  Detail & Related papers  (2026-07-20T10:43:44Z)
• Hybrid Quantum Neighborhood Selection: NISQ-Compatible Combinatorial Optimization via Stochastic Frontier Decomposition [0.0]
  This work introduces Hybrid Quantum Neighborhood Selection (HQNS)<n>HQNS selects a compact frontier of F N active variables per stage, freezing the rest into reduced QUBO coefficients.<n>We evaluate HQNS on the Maximum Diversity Subset Selection Problem (MDSSP) across six scales, N up to 1000.
  arXiv  Detail & Related papers  (2026-06-28T23:35:46Z)
• Quantum-Assisted Optimal Rebalancing with Uncorrelated Asset Selection for Algorithmic Trading Walk-Forward QUBO Scheduling via QAOA [0.2538209532048867]
  We present a hybrid classical-quantum framework for portfolio construction and rebalancing.<n>Our primary contribution is the formulation of the portfolio rebalancing schedule as a Quadratic Unconstrained Binary optimisation problem.<n>This approach recasts dynamic rebalancing as a structured binary scheduling problem amenable to variational quantum methods.
  arXiv  Detail & Related papers  (2026-03-04T15:15:55Z)
• Methods for non-variational heuristic quantum optimisation [0.5586191108738564]
  We introduce a novel class of quantum optimisations that forgo this variational framework in favour of a hybrid quantum-classical approach.<n>These algorithms are expected to exhibit inherent robustness to noise and support parallel execution across both quantum and classical resources.
  arXiv  Detail & Related papers  (2026-02-01T17:46:57Z)
• Continual Quantum Architecture Search with Tensor-Train Encoding: Theory and Applications to Signal Processing [68.35481158940401]
  CL-QAS is a continual quantum architecture search framework.<n>It mitigates challenges of costly encoding amplitude and forgetting in variational quantum circuits.<n>It achieves controllable robustness expressivity, sample-efficient generalization, and smooth convergence without barren plateaus.
  arXiv  Detail & Related papers  (2026-01-10T02:36:03Z)
• Quantum Approaches to Urban Logistics: From Core QAOA to Clustered Scalability [0.0]
  The Traveling Salesman Problem (TSP) is a fundamental challenge in optimization, widely applied in logistics and transportation.<n>Traditional algorithms often struggle to produce high-quality solutions within reasonable timeframes.<n>This study investigates the potential of the Quantum Approximate Optimization Algorithm (QAOA), a hybrid quantum-classical method.
  arXiv  Detail & Related papers  (2025-12-11T17:00:24Z)
• Hybrid Sequential Quantum Computing [33.72751145910978]
  We introduce hybrid sequential quantum computing (HSQC)<n>HSQC systematically integrates classical and quantum methods within a structured, stage-wise workflow.<n>Compared to standalone classical solvers, HSQC achieves a speedup of up to 700 times over SA and up to 9 times over runtime.
  arXiv  Detail & Related papers  (2025-10-07T12:15:43Z)
• TensoMeta-VQC: A Tensor-Train-Guided Meta-Learning Framework for Robust and Scalable Variational Quantum Computing [60.996803677584424]
  TensoMeta-VQC is a novel tensor-train (TT)-guided meta-learning framework designed to improve the robustness and scalability of VQC significantly.<n>Our framework fully delegates the generation of quantum circuit parameters to a classical TT network, effectively decoupling optimization from quantum hardware.
  arXiv  Detail & Related papers  (2025-08-01T23:37:55Z)
• A Neural-Guided Variational Quantum Algorithm for Efficient Sign Structure Learning in Hybrid Architectures [11.258303973058377]
  Variational quantum algorithms hold great promise for unlocking the power of near-term quantum processors.<n>Here, we introduce sVQNHE, a neural-guided variational quantum algorithm that decouples amplitude and sign learning across classical and quantum modules.<n>This hybrid quantum-classical synergy not only reduces measurement costs but also achieves high expressivity with limited quantum resources.
  arXiv  Detail & Related papers  (2025-07-10T08:54:49Z)
• Sculpting Quantum Landscapes: Fubini-Study Metric Conditioning for Geometry Aware Learning in Parameterized Quantum Circuits [0.0]
  We present a novel meta learning framework called Sculpture that explicitly conditions the Fubini Study metric tensor to mitigate barren plateaus in variational quantum algorithms.<n>Our theoretical analysis identifies the logarithmic condition number of the Fubini Study metric as a critical geometric quantity governing trainability, optimization dynamics, and generalization.
  arXiv  Detail & Related papers  (2025-06-27T06:30:33Z)
• VQC-MLPNet: An Unconventional Hybrid Quantum-Classical Architecture for Scalable and Robust Quantum Machine Learning [50.95799256262098]
  Variational quantum circuits (VQCs) hold promise for quantum machine learning but face challenges in expressivity, trainability, and noise resilience.<n>We propose VQC-MLPNet, a hybrid architecture where a VQC generates the first-layer weights of a classical multilayer perceptron during training, while inference is performed entirely classically.
  arXiv  Detail & Related papers  (2025-06-12T01:38:15Z)
• Threshold for Fault-tolerant Quantum Advantage with the Quantum Approximate Optimization Algorithm [6.328164687610608]
  We find that a quantum computer is unlikely to surpass classical state-of-the-art on optimization problems under realistic assumptions.<n>We further show that this restriction on classical solver energy consumption can be relaxed given optimistic but plausible reductions in physical error rates and fault-tolerance overheads.<n>These findings support the hypothesis that large-scale fault-tolerant quantum computers will be useful for optimization.
  arXiv  Detail & Related papers  (2025-04-02T16:57:28Z)
• Hybrid Quantum-Classical Optimisation of Traveling Salesperson Problem [0.0]
  The Traveling Salesperson Problem (TSP) is a fundamental NP-hard optimisation challenge.<n>We present a hybrid quantum-classical approach that integrates quantum optimisation techniques with classical machine learning methods.
  arXiv  Detail & Related papers  (2025-02-28T22:07:28Z)
• Bayesian Quantum Amplitude Estimation [46.03321798937855]
  We present BAE, a problem-tailored and noise-aware Bayesian algorithm for quantum amplitude estimation.<n>In a fault tolerant scenario, BAE is capable of saturating the Heisenberg limit; if device noise is present, BAE can dynamically characterize it and self-adapt.<n>We propose a benchmark for amplitude estimation algorithms and use it to test BAE against other approaches.
  arXiv  Detail & Related papers  (2024-12-05T18:09:41Z)
• Bias-field digitized counterdiabatic quantum optimization [39.58317527488534]
  We call this protocol bias-field digitizeddiabatic quantum optimization (BF-DCQO) Our purely quantum approach eliminates the dependency on classical variational quantum algorithms. It achieves scaling improvements in ground state success probabilities, increasing by up to two orders of magnitude.
  arXiv  Detail & Related papers  (2024-05-22T18:11:42Z)
• A Quantum-Classical Collaborative Training Architecture Based on Quantum State Fidelity [50.387179833629254]
  We introduce a collaborative classical-quantum architecture called co-TenQu. Co-TenQu enhances a classical deep neural network by up to 41.72% in a fair setting. It outperforms other quantum-based methods by up to 1.9 times and achieves similar accuracy while utilizing 70.59% fewer qubits.
  arXiv  Detail & Related papers  (2024-02-23T14:09:41Z)
• Reconfigurable Intelligent Surface (RIS)-Assisted Entanglement Distribution in FSO Quantum Networks [62.87033427172205]
  Quantum networks (QNs) relying on free-space optical (FSO) quantum channels can support quantum applications in environments where establishing an optical fiber infrastructure is challenging and costly. A reconfigurable intelligent surface (RIS)-assisted FSO-based QN is proposed as a cost-efficient framework providing a virtual line-of-sight between users for entanglement distribution.
  arXiv  Detail & Related papers  (2024-01-19T17:16:40Z)
• Efficient DCQO Algorithm within the Impulse Regime for Portfolio Optimization [41.94295877935867]
  We propose a faster digital quantum algorithm for portfolio optimization using the digitized-counterdiabatic quantum optimization (DCQO) paradigm. Our approach notably reduces the circuit depth requirement of the algorithm and enhances the solution accuracy, making it suitable for current quantum processors. We experimentally demonstrate the advantages of our protocol using up to 20 qubits on an IonQ trapped-ion quantum computer.
  arXiv  Detail & Related papers  (2023-08-29T17:53:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.