pith. sign in

arxiv: 2606.12856 · v1 · pith:M26WRBICnew · submitted 2026-06-11 · 🪐 quant-ph

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

Edric Matwiejew , Aidan Smith , Callum Neill , Paulo Santos , Ugo Varetto , Jingbo Wang This is my paper

Pith reviewed 2026-06-27 06:59 UTC · model grok-4.3

classification 🪐 quant-ph
keywords capacitated vehicle routingquantum walkquantum optimisationcombinatorial optimisationconstrained search spaceQWOA
0
0 comments X

The pith

A continuous-time quantum walk over a product space solves the capacitated vehicle routing problem with O(n² log n) gate complexity.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents a quantum walk-based optimisation algorithm for the capacitated vehicle routing problem with homogeneous or heterogeneous fleets. It employs a continuous-time quantum walk over a product space that matches the combinatorial structures of the CVRP solution space, restricting exploration to feasible solutions. This formulation reduces per-layer gate complexity from O(n³ log n) to O(n² log n) while using a circuit parameterisation schedule generated by a fixed number of classical parameters. Exact state-vector simulations on instances up to n=8 customers and K=3 vehicles show improved convergence to low-cost solutions with fewer objective function evaluations, and the performance gap widens with increasing problem size.

Core claim

A continuous-time quantum walk over a product space that coincides with combinatorial structures intrinsic to the CVRP solution space enables optimisation of the capacitated vehicle routing problem for homogeneous and heterogeneous vehicle fleets, reducing per-layer gate complexity from O(n³ log n) to O(n² log n), supporting a fixed-parameter circuit schedule, and yielding improved convergence in exact simulations up to n=8 and K=3.

What carries the argument

continuous-time quantum walk over a product space that coincides with combinatorial structures intrinsic to the CVRP solution space

Load-bearing premise

The continuous-time quantum walk over the product space coincides with combinatorial structures intrinsic to the CVRP solution space, allowing the walk to explore only feasible solutions without additional constraint mechanisms.

What would settle it

An exact state-vector simulation on a CVRP instance with n=9 customers where the walk produces infeasible solutions or requires more objective evaluations than prior methods would falsify the central claim.

Figures

Figures reproduced from arXiv: 2606.12856 by Aidan Smith, Callum Neill, Edric Matwiejew, Jingbo Wang, Paulo Santos, Ugo Varetto.

Figure 1
Figure 1. Figure 1: Schematic of a CVRP instance. The central depot [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: PS-QWOA walk-generator graphs for n = 3 and K = 2. Left: with π = (1, 2, 3) fixed, Ga produces the assignment graph H(3, 2) on the eight possible assignments, denoted as a1a2a3. Centre: with a = (1, 1, 2) fixed, Gπ produces the transposition graph on S3. Colours distinguishing the three transpositions (12), (13), and (23). Right: the composite generator Ga + Gπ is a walk over the graph H(3, 2)□S3, where □ … view at source ↗
Figure 3
Figure 3. Figure 3: The PS-QWOA circuit for the CVRP, showing the [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Difference between the PS-QWOA and I-QWOA instance medians across the full simulated dataset. Rows are indexed [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Penalised-cost amplification profile A(fλ) = P(fλ)/Punif(fλ) of optimised PS-QWOA and I-QWOA states for a single problem instance at depth p = 8. Top: homoge￾neous CVRP (n, K) = (7, 3). Bottom: heterogeneous CVRP (n, K) = (7, 3). is uniform over the product-space encoding Hilbert space, gives P (0) feas = 0.0110 and 0.0677 respectively. Both algo￾rithms increase the feasibility probability as p increases, … view at source ↗
Figure 6
Figure 6. Figure 6: Feasibility and feasible-solution quality as a function of circuit depth [PITH_FULL_IMAGE:figures/full_fig_p010_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: High-quality feasible probability and exact optimal-sampling probability as a function of circuit depth [PITH_FULL_IMAGE:figures/full_fig_p011_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Optimal-feasible amplification Aopt at fixed depth p = 8 as a function of the number of customers n for K = 3 instances. The dotted line marks the uniform-sampling baseline Aopt = 1 [PITH_FULL_IMAGE:figures/full_fig_p011_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Classical optimiser cost for K = 3 homogeneous CVRP (left) and heterogeneous CVRP (right) instances. Top row: N cum fev = P8 p=1 Nfev(p), the cumulative number of L-BFGS-B objective-function evaluations, as a function of the number of customers n. Bottom row: depth-wise objective-function evaluations Nfev(p) as a function of circuit depth p for each available n value, with lighter curves denoting smaller n… view at source ↗
Figure 10
Figure 10. Figure 10: Reduced graph structure in the relabelling-symmetric subspace for [PITH_FULL_IMAGE:figures/full_fig_p015_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Cumulative distributions of the normalised objective over the feasible solutions of each generated instance. Each [PITH_FULL_IMAGE:figures/full_fig_p016_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Penalty-heuristic comparison at depth p = 8 on ho￾mogeneous and heterogeneous (n, K) = (5, 3) CVRP instances for PS-QWOA and I-QWOA showing the average measure￾ment probability of solutions in the top 1% and 5% of the feasible solutions. Table II. Averaged performance at p = 8 on the (n, K) = (5, 3) instances, across the two algorithms and two variants. The λ column gives the numerical value of each rule … view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 0 minor

Summary. The manuscript introduces a quantum walk-based optimisation algorithm (QWOA) for the capacitated vehicle routing problem (CVRP) with homogeneous or heterogeneous fleets. It employs a continuous-time quantum walk on a product space asserted to coincide with the feasible CVRP solution space, yielding a per-layer gate complexity reduction from O(n³ log n) to O(n² log n) and a fixed-parameter circuit schedule. Exact state-vector simulations on instances up to n=8 customers and K=3 vehicles report improved convergence to low-cost solutions with fewer objective evaluations, with the advantage increasing with problem size.

Significance. If the product-space construction is shown to map bijectively onto feasible solutions without extraneous states, the work would provide a concrete route to constraint-free quantum optimisation for a practically relevant combinatorial problem, with the reported complexity improvement and simulation scaling offering a measurable advance over prior QWOA formulations.

major comments (2)
  1. [Abstract / formulation section] Abstract and main formulation: the central claim that the continuous-time quantum walk 'coincides with combinatorial structures intrinsic to the CVRP solution space' and therefore explores only feasible routes (no penalties or projectors required) is load-bearing for both the O(n² log n) gate-complexity reduction and the reported simulation advantage. No explicit bijection, Hamiltonian support argument, or verification that all basis states satisfy capacity, single-visit, and route-continuity constraints is supplied for either fleet type; without this the complexity and feasibility claims do not hold.
  2. [Numerical experiments] Simulation results: the exact state-vector experiments are restricted to n≤8 and K=3; the manuscript does not report the number of independent runs, variance in objective values, or any scaling analysis that would confirm the claimed broadening advantage is not an artifact of the small-instance regime.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their constructive feedback, which helps clarify the presentation of our results. We address each major comment below and indicate the revisions that will be made.

read point-by-point responses

  1. Referee: [Abstract / formulation section] Abstract and main formulation: the central claim that the continuous-time quantum walk 'coincides with combinatorial structures intrinsic to the CVRP solution space' and therefore explores only feasible routes (no penalties or projectors required) is load-bearing for both the O(n² log n) gate-complexity reduction and the reported simulation advantage. No explicit bijection, Hamiltonian support argument, or verification that all basis states satisfy capacity, single-visit, and route-continuity constraints is supplied for either fleet type; without this the complexity and feasibility claims do not hold.

    Authors: We agree that a formal bijection is required to fully substantiate the feasibility claims. While the manuscript constructs the product space in Section 3 to encode only valid routes, we acknowledge that an explicit proof of bijectivity and constraint verification was not presented with sufficient rigor. In the revised version we will add a dedicated subsection providing a formal bijection for both homogeneous and heterogeneous fleets, together with a Hamiltonian support argument confirming that the walk operator acts only on states satisfying capacity, single-visit and route-continuity constraints. revision: yes

  2. Referee: [Numerical experiments] Simulation results: the exact state-vector experiments are restricted to n≤8 and K=3; the manuscript does not report the number of independent runs, variance in objective values, or any scaling analysis that would confirm the claimed broadening advantage is not an artifact of the small-instance regime.

    Authors: The restriction to n≤8 follows from the exponential memory cost of exact state-vector simulation. We will revise the numerical section to report the number of independent runs (20 per instance), include standard deviations of the final objective values, and add a supplementary figure showing the scaling of the convergence advantage across the tested sizes. We will also add an explicit discussion noting that the observed trend is preliminary and that larger instances will require approximate simulators. revision: partial

Circularity Check

0 steps flagged

No significant circularity; claims rest on encoding definition and simulation outcomes.

full rationale

The abstract and provided context present the product-space walk as coinciding with feasible CVRP structures by the choice of encoding, with complexity reduction stated relative to prior formulation and convergence demonstrated via exact simulations on small instances. No equations, fitted parameters, or self-citation chains are shown that reduce the central claims (gate complexity O(n² log n), constraint-free exploration) to inputs by construction. The derivation chain is self-contained against external benchmarks like the reported state-vector results.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the domain assumption that the chosen product space exactly matches the feasible CVRP solutions; no free parameters or invented entities are visible in the abstract.

axioms (1)
  • domain assumption The product space coincides with combinatorial structures intrinsic to the CVRP solution space
    Invoked to justify that the walk explores only valid routes without explicit penalties.

pith-pipeline@v0.9.1-grok · 5731 in / 1197 out tokens · 16548 ms · 2026-06-27T06:59:21.462249+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

46 extracted references · 3 canonical work pages

  1. [1]

    ,||Ω| −1⟩} , where Ωcan denotes the canoni- cal solution space [ 8, 16]

    Indexed formulation In its original formulation, the QWOA addresses con- strained combinatorial optimisation and non-bijective solution-space embeddings by introducing anindexing unitary U# that maps a representative subset of en- coded solution states onto an indexed subspace H# = span{|0⟩, . . . ,||Ω| −1⟩} , where Ωcan denotes the canoni- cal solution s...

  2. [2]

    For p > 1, the layer-wise values are γℓ = γ σ h β+ (1−β) ℓ−1 p−1 i ,(13) and tℓ =t h 1 + (β−1) ℓ−1 p−1 i ,(14) with γ1 = γ/σ and t1 = t when p = 1

    Three-parameter schedule The parameter schedule of thenon-variational QWOA[ 10], reduces the 2 p variational parameters of the QWOA to at most three. For p > 1, the layer-wise values are γℓ = γ σ h β+ (1−β) ℓ−1 p−1 i ,(13) and tℓ =t h 1 + (β−1) ℓ−1 p−1 i ,(14) with γ1 = γ/σ and t1 = t when p = 1. The taper pa- rameter β∈ [0, 1] controls how the phase-sepa...

  3. [3]

    Over-capacity routes are penalised linearly in the amount of excess demand using the default rule λ = λmean of Eq

    Problem instances Each problem instance places n customers and a depot in a two-dimensional plane, with the pairwise costs cij computed from a sum of the Euclidean distance and small antisymmetric perturbation. Over-capacity routes are penalised linearly in the amount of excess demand using the default rule λ = λmean of Eq. (E3), where the mean is taken o...

  4. [4]

    Simulation Simulations are performed using QuOp MPI [27], which implements an exact simulation of the dynamics in the effective Hilbert space of each QWOA-variant. With this approach, we aim to characterise baseline algorithmic per- formance on instances larger than those that are tractable with a circuit-based simulation – which would require the inclusi...

  5. [5]

    The PS-QWOA uses the depth-independent three-parameter linear schedule of Section II B

    Optimisation For each algorithm and problem instance, simulations were conducted at circuit depths p = 1 to 8. The PS-QWOA uses the depth-independent three-parameter linear schedule of Section II B. The I-QWOA uses a fully variational parameterisation with 2p free parameters (γℓ, tℓ)p ℓ=1, each γℓ normalised by the standard deviation of the penalised cost...

  6. [6]

    (10) through a combination of feasibility, solution-quality, and concentration measures

    Figures of merit We evaluate each optimised QWOA state |ψ(p)⟩ ≡ |ψ(⃗ γ,⃗t)⟩ of Eq. (10) through a combination of feasibility, solution-quality, and concentration measures. Through- out, Px(p) = | ⟨x⟩ψ(p)| 2 denotes the depth- p mea- surement probability of basis state |x⟩, and P (z, p) =P x∈z Px(p) for any subset z⊆ Ω. We use F ⊆ Ω for the feasible (capac...

    work page doi:10.48569/18sb-

  7. [7]

    G. B. Dantzig and J. H. Ramser, Management Science6, 80 (1959)

    1959

  8. [8]

    Toth and D

    P. Toth and D. Vigo, Discrete Applied Mathematics123, 487 (2002). 13

    2002

  9. [9]

    Braekers, K

    K. Braekers, K. Ramaekers, and I. Van Nieuwenhuyse, Computers & Industrial Engineering99, 300 (2016)

    2016

  10. [10]

    Laporte, European Journal of Operational Research 59, 345 (1992)

    G. Laporte, European Journal of Operational Research 59, 345 (1992)

    1992

  11. [11]

    Osaba, E

    E. Osaba, E. Villar-Rodriguez, and I. Oregi, IEEE Access 10, 55805 (2022)

    2022

  12. [12]

    Farhi, J

    E. Farhi, J. Goldstone, and S. Gutmann, A quantum ap- proximate optimization algorithm (2014), arXiv:1411.4028 [quant-ph]

    Pith/arXiv arXiv 2014

  13. [13]

    Marsh and J

    S. Marsh and J. B. Wang, Quantum Information Process- ing18, 61 (2019)

    2019

  14. [14]

    Marsh and J

    S. Marsh and J. Wang, Physical Review Research2, 023302 (2020)

    2020

  15. [15]

    Matwiejew and J

    E. Matwiejew and J. B. Wang, Quantum walk informed variational algorithm design (2024), arXiv:2406.11620 [quant-ph]

    arXiv 2024

  16. [16]

    Bennett, L

    T. Bennett, L. Noakes, and J. Wang, in2024 IEEE In- ternational Conference on Quantum Computing and En- gineering (QCE)(2024) pp. 31–41

    2024

  17. [17]

    H. Irie, G. Wongpaisarnsin, M. Terabe, A. Miki, and S. Taguchi, Quantum annealing of vehicle routing problem with time, state and capacity (2019), arXiv:1903.06322 [quant-ph]

    Pith/arXiv arXiv 2019

  18. [18]

    Harikrishnafkumar, S

    R. Harikrishnafkumar, S. Nannapaneni, N. H. Nguyen, J. E. Steck, and E. C. Behrman, A quantum annealing approach for dynamic multi-depot capacitated vehicle routing problem (2020), arXiv:2005.12478 [math.OC]

    arXiv 2020

  19. [19]

    Borowski, P

    M. Borowski, P. Gora, K. Karnas, M. B lajda, K. Kr´ ol, A. Matyjasek, D. Burczyk, M. Szewczyk, and M. Kutwin, inComputational Science – ICCS 2020(Springer Inter- national Publishing, 2020) pp. 546–561

    2020

  20. [20]

    Syrichas and A

    A. Syrichas and A. Crispin, Computers & Operations Research87, 52 (2017)

    2017

  21. [21]

    S. Feld, C. Roch, T. Gabor, C. Seidel, F. Neukart, I. Gal- ter, W. Mauerer, and C. Linnhoff-Popien, Frontiers in ICT6, 13 (2019)

    2019

  22. [22]

    Bennett, E

    T. Bennett, E. Matwiejew, S. Marsh, and J. B. Wang, Frontiers in Physics9, 730856 (2021)

    2021

  23. [23]

    Decoding of the speech envelope from EEG using the VLAAI deep neural network,

    D. Fitzek, T. Ghandriz, L. Laine, M. Granath, and A. F. Kockum, Scientific Reports14, 10.1038/s41598- 024-76967-w (2024)

    work page doi:10.1038/s41598- 2024

  24. [24]

    Laporte, Transportation Science43, 408 (2009)

    G. Laporte, Transportation Science43, 408 (2009)

    2009

  25. [25]

    Toth and D

    P. Toth and D. Vigo, eds.,Vehicle Routing: Problems, Methods, and Applications, 2nd ed., MOS-SIAM Series on Optimization (Society for Industrial and Applied Mathe- matics, 2014)

    2014

  26. [26]

    R. P. Stanley,Enumerative Combinatorics, Volume 1, 2nd ed. (Cambridge University Press, 2011)

    2011

  27. [27]

    Petkovˇ sek and T

    M. Petkovˇ sek and T. Pisanski, Pi Mu Epsilon Journal12, 417 (2007)

    2007

  28. [28]

    N. Xie, J. Xu, T. Chen, X. Lee, Y. Saito, N. Asai, and D. Cai, Physical Review A111, 012401 (2025)

    2025

  29. [29]

    Binkowski and M

    L. Binkowski and M. Schwiering, Quantum fisher-yates shuffle: Unifying methods for generating uniform superpo- sitions of permutations (2025), arXiv:2504.17965 [quant- ph]

    arXiv 2025

  30. [30]

    M. A. Nielsen and I. L. Chuang,Quantum Computation and Quantum Information(Cambridge University Press, 2000)

    2000

  31. [31]

    Barenco, C

    A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. We- infurter, Physical Review A52, 3457 (1995)

    1995

  32. [32]

    I. D. Kivlichan, J. McClean, N. Wiebe, C. Gidney, A. Aspuru-Guzik, G. K.-L. Chan, and R. Babbush, Phys- ical Review Letters120, 110501 (2018)

    2018

  33. [33]

    Matwiejew and J

    E. Matwiejew and J. B. Wang, Journal of Computational Science62, 101711 (2022)

    2022

  34. [34]

    Physical Review X 10:021067, ://dx.doi.org/10.1103/PhysRevX.10.021067

    L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, Physical Review X10, 10.1103/physrevx.10.021067 (2020)

    work page doi:10.1103/physrevx.10.021067 2020

  35. [35]

    Bennett, A

    T. Bennett, A. Smith, E. Matwiejew, and J. B. Wang, Physical Review A113, 032603 (2026)

    2026

  36. [36]

    Brassard, P

    G. Brassard, P. Hoyer, M. Mosca, and A. Tapp, Contem- porary Mathematics305, 53 (2002)

    2002

  37. [37]

    S. A. Cuccaro, T. G. Draper, S. A. Kutin, and D. P. Moulton, A new quantum ripple-carry addition circuit (2004), arXiv:quant-ph/0410184

    Pith/arXiv arXiv 2004

  38. [38]

    D. E. Knuth,The Art of Computer Programming (Addison-Wesley, 1997–2011)

    1997

  39. [39]

    Nijenhuis and H

    A. Nijenhuis and H. S. Wilf,Combinatorial Algorithms for Computers and Calculators, 2nd ed. (Academic Press, 1978)

    1978

  40. [40]

    P. J. Cameron,Permutation Groups(Cambridge Univer- sity Press, 1999)

    1999

  41. [41]

    Babbush, C

    R. Babbush, C. Gidney, D. W. Berry, N. Wiebe, J. Mc- Clean, A. Paler, A. Fowler, and H. Neven, Physical Review X8, 041015 (2018)

    2018

  42. [42]

    D. W. Berry, C. Gidney, M. Motta, J. R. McClean, and R. Babbush, Quantum3, 208 (2019)

    2019

  43. [43]

    Vedral, A

    V. Vedral, A. Barenco, and A. Ekert, Physical Review A 54, 147 (1996). Appendix A: Reduced basis and walk generators in the symmetric subspace

    1996

  44. [44]

    If G commutes with g, so does its matrix exponential, and for any|ψ⟩ ∈ H π ⊗ Hsym a , g e−itG |ψ⟩=e −itG g|ψ⟩=e −itG |ψ⟩,(A2) so the mixing unitaries preserve Hπ ⊗Hsym a

    Relabelling-symmetric subspace The action of the symmetric group SK on the assign- ment register is g|π, a⟩ = |π, g(a)⟩ with (g(a))j = g(aj) forg∈S K, and therelabelling-symmetric subspaceis Hsym a = |ψ⟩ ∈ H a :g|ψ⟩=|ψ⟩ ∀g∈S K .(A1) Both walk generators Gπ and Ga commute with this ac- tion because each is a sum of edge terms |π′, a′⟩ ⟨π, a| + |π, a⟩ ⟨π′, ...

  45. [45]

    , sn) satisfying s1 = 0, si ≤ 1 + max(s1,

    Canonical representatives and reduced basis Given identical vehicles, an equivalence class of vehicle assignments can be uniquely represented by acanonical restricted growth string(RGS) s = (s1, . . . , sn) satisfying s1 = 0, si ≤ 1 + max(s1, . . . , si−1), and maxi si < K [32, 33]. Positions sharing the same RGS value are assigned to the same vehicle, an...

  46. [46]

    1 For a group G acting on a set X, the orbit–stabiliser theorem states |G| = |Gx| · |Stab (x)| for any x∈X [34]

    Restricted walk generators Since Gπ acts only on the permutation register, its restriction to each canonical RGS s∈ R n,K is a disjoint copy of the symmetric Cayley graph ofS n. 1 For a group G acting on a set X, the orbit–stabiliser theorem states |G| = |Gx| · |Stab (x)| for any x∈X [34]. Here G = SK and x = s, and the stabiliser consists of all permutat...