Quantum walk-based optimisation for capacitated vehicle routing with homogeneous and heterogeneous fleets

• URL: http://arxiv.org/abs/2606.12856v1
• Date: Thu, 11 Jun 2026 03:39:29 GMT
• Title: Quantum walk-based optimisation for capacitated vehicle routing with homogeneous and heterogeneous fleets
• Abstract summary: The capacitated vehicle routing problem (CVRP) is an appealing candidate for quantum optimisation due to its objective complexity and practical importance.<n>We introduce a quantum walk-based optimisation (QWOA) for the CVRP with a homogeneous or heterogeneous vehicle fleets, addressing this challenge through a continuous-time quantum walk over a product space.<n>Relative to the prior QWOA-based formulation, this approach reduces the per-layer gate complexity from $mathcalO(n3log n)$ to $mathcalO(n2log n)$
• Score: 3.6100252173467537
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The capacitated vehicle routing problem (CVRP) is an appealing candidate for quantum optimisation due to its combinatorial complexity and practical importance. However, the problem's constrained search space poses a challenge for such quantum algorithms. We introduce a quantum walk-based optimisation algorithm (QWOA) for the CVRP with homogeneous or heterogeneous vehicle fleets, addressing this challenge through a continuous-time quantum walk over a product space that coincides with combinatorial structures intrinsic to the CVRP solution space. Relative to the prior QWOA-based formulation, this approach reduces the per-layer gate complexity from $\mathcal{O}(n^{3}\log n)$ to $\mathcal{O}(n^{2}\log n)$ and supports a circuit parameterisation schedule generated by a fixed number of classical parameters. Exact state-vector simulation on instances with up to $n=8$ customers and $K=3$ vehicles demonstrates improved convergence to low-cost solutions using markedly fewer objective function evaluations, with the advantage broadening as problem size increases. These results identify structured product-space walks as a promising tool for optimisation over constrained combinatorial spaces.

Related papers

• Quantum iterative approach to the Traveling Salesman Problem [0.6741942263052466]
  The Traveling Salesman Problem (TSP) is a classical NP-hard problem in optimization, where determining the shortest route among a set of cities becomes computationally prohibitive as the problem size increases.<n>This work explores quantum computing as an alternative approach to address this complexity.<n>Route costs are encoded as quantum phases, enabling QPE to efficiently evaluate them, while Amplitude Amplification, implemented via the Grover-Long algorithm, iteratively refines the solution space toward the optimal route.
  arXiv  Detail & Related papers  (2026-06-10T09:21:15Z)
• Efficient Fourier-Based Linear Combination of Unitaries and Applications in Quantum Optimization [0.7009487789080343]
  We investigate ancilla-free linear combination of unitaries (LCU) as a framework for approximating complex quantum circuits.<n>We show that Fourier-based LCU constructions efficiently decompose broad classes of diagonal and non-diagonal unitaries.
  arXiv  Detail & Related papers  (2026-05-18T18:05:08Z)
• Hybrid Quantum-Classical Optimization Workflows for the Shipment Selection Problem [0.25457638766329743]
  We present a quantum optimization framework for the Shipment Selection Problem (SSP) in electric freight logistics, developed jointly by IonQ and Einride.<n>We formulate the SSP as a Mixed-Integer Quadratic Program, map it to an Isationaling cost Hamiltonian, and solve it using Iterative-QAOA.<n>An end-to-end hybrid workflow integrates Einride's vehicle routing problem solver with IonQ's quantum simulations, enabling evaluation on real, anonymized logistics data spanning up to 130 qubits.
  arXiv  Detail & Related papers  (2026-04-13T17:30:49Z)
• A Scalable Distributed Quantum Optimization Framework via Factor Graph Paradigm [46.08923284345648]
  We introduce a structure-aware framework for distributed quantum optimization.<n>We find that for a search space of size $N$, our framework achieves $O(sqrtN)$ query complexity up to processors and separator dependent factors.<n>We show that structure-aware decomposition delivers a practical path to scalable distributed quantum optimization on quantum networks.
  arXiv  Detail & Related papers  (2026-03-08T15:15:52Z)
• Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
  Variational quantum algorithms (VQA) have emerged as a promising quantum alternative for solving optimization and machine learning problems. In this paper, we experimentally demonstrate the influence of the circuit design on the performance obtained for two classification problems. We also study the degradation of the obtained circuits in the presence of noise when simulating real quantum computers.
  arXiv  Detail & Related papers  (2024-04-17T11:00:12Z)
• Blockwise Stochastic Variance-Reduced Methods with Parallel Speedup for Multi-Block Bilevel Optimization [43.74656748515853]
  Non-stationary multi-block bilevel optimization problems involve $mgg 1$ lower level problems and have important applications in machine learning. We aim to achieve three properties for our algorithm: a) matching the state-of-the-art complexity of standard BO problems with a single block; (b) achieving parallel speedup by sampling $I$ samples for each sampled block per-iteration; and (c) avoiding the computation of the inverse of a high-dimensional Hessian matrix estimator.
  arXiv  Detail & Related papers  (2023-05-30T04:10:11Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  Constrained optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
  arXiv  Detail & Related papers  (2022-11-16T18:59:54Z)
• A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
  We propose a hybrid quantum-classical algorithm for robust fitting. Our core contribution is a novel robust fitting formulation that solves a sequence of integer programs. We present results obtained using an actual quantum computer.
  arXiv  Detail & Related papers  (2022-01-25T05:59:24Z)
• Applying quantum approximate optimization to the heterogeneous vehicle routing problem [0.7503129292751939]
  We investigate the potential use of a quantum computer to find approximate solutions to the heterogeneous vehicle routing problem. We find that the number of qubits needed for this mapping scales quadratically with the number of customers.
  arXiv  Detail & Related papers  (2021-10-13T15:38:25Z)
• Quantum walk-based vehicle routing optimisation [0.0]
  This paper demonstrates the applicability of the Quantum Walk-based optimisation algorithm to the Capacitated Vehicle Routing Problem (CVRP) Efficient algorithms are developedfor the indexing and unindexing of the solution space and for implementing the required alternatingphase-walk unitaries. Results of numerical simulationdemonstrate that the QWOA is capable of producing convergence to near-optimal solutions for arandomly generated 8 location CVRP.
  arXiv  Detail & Related papers  (2021-09-30T08:04:58Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets [47.00474212574662]
  Variational quantum algorithms are believed to be promising for solving computationally hard problems. In this paper, we experimentally investigate the circuit-depth-dependent performance of QAOA applied to exact-cover problem instances. Our results demonstrate that the use of continuous gate sets may be a key component in extending the impact of near-term quantum computers.
  arXiv  Detail & Related papers  (2020-05-11T17:20:51Z)

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.