A Hybrid Classical-Quantum Annealing Algorithm for the TSP

• URL: http://arxiv.org/abs/2605.09616v1
• Date: Sun, 10 May 2026 15:55:38 GMT
• Title: A Hybrid Classical-Quantum Annealing Algorithm for the TSP
• Abstract summary: We propose a hybrid technique to solve a well-known NP-hard optimization problem: the Traveling Salesperson Problem (TSP)<n>Our approach is based on a graph contraction technique that removes most of the dimensionality of the original problem instance.<n>The performance of our approach is first demonstrated on classical quantum simulation using Path Integral Monte Carlo, and then run on a D-Wave quantum annealer.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Hybrid quantum-classical algorithms can help mitigating the physical limitations of current quantum devices, particularly the low qubit count and the reduced topological connectivity. In this paper, we propose a hybrid technique to solve a well-known NP-hard optimization problem: the Traveling Salesperson Problem (TSP). Our approach is based on a graph contraction technique that removes most of the dimensionality of the original problem instance, producing a sub-TSP of a size suitable to be efficiently solved by a quantum device. The performance of our approach is first demonstrated on classical quantum simulation using Path Integral Monte Carlo, and then run on a D-Wave quantum annealer.

Related papers

• Quantum algorithm for the lattice Boltzmann method with applications on real quantum devices [0.0]
  We introduce a novel quantum algorithm for the lattice Boltzmann method (LBM) based on the one-step simplified LBM.<n>The new algorithm has potential for full end-to-end quantum utility especially for linear problems.
  arXiv  Detail & Related papers  (2026-03-02T17:45:07Z)
• Quantum Approximate Optimization Algorithm for MIMO with Quantized b-bit Beamforming [47.98440449939344]
  Multiple-input multiple-output (MIMO) is critical for 6G communication, offering improved spectral efficiency and reliability.<n>This paper explores the use of the Quantum Approximate Optimization Algorithm (QAOA) and alternating optimization to address the problem of b-bit quantized phase shifters both at the transmitter and the receiver.<n>We demonstrate that the structure of this quantized beamforming problem aligns naturally with hybrid-classical methods like QAOA, as the phase shifts used in beamforming can be directly mapped to rotation gates in a quantum circuit.
  arXiv  Detail & Related papers  (2025-10-07T17:53:02Z)
• Combinatorial optimization enhanced by shallow quantum circuits with 104 superconducting qubits [14.569660066740758]
  optimization problems have attracted tremendous attention due to their broad applicability and natural fitness to Ising Hamiltonians.<n>Here we propose a quantum sampling strategy, based on which we design an algorithm for accelerating solving the ground states of Ising model.<n>Using up to 104 superconducting qubits, we demonstrate that this algorithm outputs favorable solutions against even a highly-optimized classical simulated subroutine (SA) algorithm.
  arXiv  Detail & Related papers  (2025-09-15T02:58:38Z)
• RhoDARTS: Differentiable Quantum Architecture Search with Density Matrix Simulations [44.13836547616739]
  Variational Quantum Algorithms (VQAs) are a promising approach to leverage Noisy Intermediate-Scale Quantum (NISQ) computers.<n> choosing optimal quantum circuits that efficiently solve a given VQA problem is a non-trivial task.<n>Quantum Architecture Search (QAS) algorithms enable automatic generation of quantum circuits tailored to the provided problem.
  arXiv  Detail & Related papers  (2025-06-04T08:30:35Z)
• Solving the Traveling Salesman Problem via Different Quantum Computing Architectures [0.0]
  We study the application of emerging photonic and quantum computing architectures to solving the Traveling Salesman Problem (TSP)<n> Gate-based quantum computers demonstrated accurate results for small TSP instances in simulation.<n>Ising-based architectures show improved scalability for larger problem sizes.
  arXiv  Detail & Related papers  (2025-02-24T23:37:19Z)
• 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 Hybrid Quantum-Classical Physics-Informed Neural Network Architecture for Solving Quantum Optimal Control Problems [1.4811951486536687]
  The study showcases an innovative approach to optimizing quantum state manipulations. The proposed hybrid model effectively applies machine learning techniques to solve optimal control problems. This is illustrated through the design and implementation of a hybrid PINN network to solve a quantum state transition problem.
  arXiv  Detail & Related papers  (2024-04-23T13:22:22Z)
• Formulation of the Electric Vehicle Charging and Routing Problem for a Hybrid Quantum-Classical Search Space Reduction Heuristic [0.0]
  We show how to exploit multilevel carriers of quantum information -- qudits -- for the construction of constrained quantum optimization algorithms. We propose a hybrid classical quantum strategy that allows us to sample constrained solutions while greatly reducing the search space of the problem.
  arXiv  Detail & Related papers  (2023-06-07T13:16:15Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• Decomposition of Matrix Product States into Shallow Quantum Circuits [62.5210028594015]
  tensor network (TN) algorithms can be mapped to parametrized quantum circuits (PQCs) We propose a new protocol for approximating TN states using realistic quantum circuits. Our results reveal one particular protocol, involving sequential growth and optimization of the quantum circuit, to outperform all other methods.
  arXiv  Detail & Related papers  (2022-09-01T17:08:41Z)
• Synergy Between Quantum Circuits and Tensor Networks: Short-cutting the Race to Practical Quantum Advantage [43.3054117987806]
  We introduce a scalable procedure for harnessing classical computing resources to provide pre-optimized initializations for quantum circuits. We show this method significantly improves the trainability and performance of PQCs on a variety of problems. By demonstrating a means of boosting limited quantum resources using classical computers, our approach illustrates the promise of this synergy between quantum and quantum-inspired models in quantum computing.
  arXiv  Detail & Related papers  (2022-08-29T15:24:03Z)
• Simulating quantum circuits using the multi-scale entanglement renormalization ansatz [0.0]
  We propose a scalable technique for approximate simulations of intermediate-size quantum circuits.<n>We benchmark the proposed technique for brick-wall quantum circuits of up to 243 qubits with various depths up to 20 layers.
  arXiv  Detail & Related papers  (2021-12-28T09:05:01Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions. Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
  arXiv  Detail & Related papers  (2021-06-24T20:16:02Z)
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
  We present a constructive algorithm for generating quantum circuits with time-independent depth. We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model. In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
  arXiv  Detail & Related papers  (2021-04-01T19:06:00Z)

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.