pith. machine review for the scientific record. sign in

arxiv: 2604.04570 · v3 · submitted 2026-04-06 · 🪐 quant-ph · cs.CC· cs.DM· cs.IT· math-ph· math.IT· math.MP

Recognition: 2 theorem links

· Lean Theorem

Optimal, Qubit-Efficient Quantum Vehicle Routing via Colored-Permutations

Chinonso Onah , Kristel Michielsen
Authors on Pith no claims yet

Pith reviewed 2026-05-10 19:57 UTC · model grok-4.3

classification 🪐 quant-ph cs.CCcs.DMcs.ITmath-phmath.ITmath.MP
keywords quantum vehicle routingcolored permutationscapacitated VRPQAOAqubit-efficient encodingpermutation matrixconstraint enforcement
0
0 comments X

The pith

A colored-permutation encoding solves the capacitated vehicle routing problem using only n squared K binary routing variables and no extra qubits for capacity or load tracking.

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

The paper introduces an encoding in which each of K vehicles is assigned a disjoint partial permutation over customer positions, and the K color layers together form a single complete n by n permutation matrix that assigns every customer to exactly one visit slot. Vehicle capacities are maintained by computing weighted sums of the entries inside each individual color layer instead of maintaining a separate load counter. This removes the extra logical qubits that prior quantum formulations have required for explicit capacity registers or vehicle labels. The construction is built to run inside the Constraint-Enhanced QAOA framework, and the authors report that the resulting end-to-end pipeline recovers the known optimal solutions on standard benchmark instances.

Core claim

The central claim is that the global-position colored-permutation representation uses n squared K binary decision variables arranged as K color layers over a shared permutation structure, enforces capacities by weighted sums taken separately inside each color class, and therefore introduces no explicit load register and no additional logical qubits beyond the routing variables themselves; when combined with the Constraint-Enhanced QAOA manifold the formulation recovers the independently verified optima on standard CVRP test sets.

What carries the argument

The colored-permutation encoding, in which K disjoint partial permutations sum to one full n by n permutation matrix while capacities are enforced by per-color weighted sums.

If this is right

  • The qubit cost of vehicle labels and explicit capacity constraints is removed from the logical-qubit budget.
  • End-to-end runs on standard benchmarks recover the independently verified optimal solutions.
  • The feasibility oracle supplies a polynomial-time decoding and certification routine that can be reused in other quantum or quantum-inspired routing pipelines.
  • The encoding is designed to operate directly inside the Constraint-Enhanced QAOA framework.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same layered-permutation idea could be tested on other assignment or sequencing problems that currently pay a qubit penalty for side constraints.
  • If the weighted-sum enforcement scales without introducing undetected infeasible solutions, hybrid solvers could handle larger logistics instances on near-term hardware.
  • A direct follow-up experiment would be to measure the gap between the encoded objective and the true cost on instances with tight capacity bounds.

Load-bearing premise

The weighted-sum capacity checks inside each color layer, together with the Constraint-Enhanced QAOA manifold, capture every CVRP feasibility constraint without hidden violations or the need for extra qubits in the actual circuit.

What would settle it

A small CVRP instance on which the encoding returns a set of routes that satisfy all per-color weighted-sum constraints yet produce an actual tour whose total demand exceeds a vehicle's capacity when the routes are decoded.

Figures

Figures reproduced from arXiv: 2604.04570 by Chinonso Onah, Kristel Michielsen.

Figure 1
Figure 1. Figure 1: Global-position CE-QAOA with 3 blocks, each of size nK = 4 wires. The diagonal entangler e −iγℓHC spans all 3 · 4 wires (green), while the mixers U (j) M (βℓ) (orange) act independently within each block j. Three layers (ℓ = 1, 2, 3) are shown. 2 Kernelizing Vehicle Routing Problem 2.1 Encoding All Valid Routes as Coloured Permutations Setup. We adopt the global-position encoding throughout. Let n be the n… view at source ↗
Figure 2
Figure 2. Figure 2: Encoded anticoncentration and design baseline. Each panel shows the empirical histogram of feasible outcomes from a depth-p = 1 CE–QAOA run on a CVRP instance, using shots S = Θ(n 3 ) per grid point. The dashed line is the encoded design baseline 1/D with D = (nK) n. Peaks far above 1/D and the successful identification of the optimum support the anticoncentration guarantees. 3 A hybrid quantum–classical r… view at source ↗
Figure 3
Figure 3. Figure 3: Comparison of qubit counts for two binary global-position encodings across representative [PITH_FULL_IMAGE:figures/full_fig_p020_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Colored decomposition: P = P (1) + P (2) with disjoint supports. B CVRP Examples: from locations to colored permutations B.1 Example A: 4 locations 2 Vehicles Consider a routing problem with 4 locations, 2 vehicles. ⇒ n = 3 customers with K = 2 vehicles. We have n = 3 blocks and local alphabet size nK = 3 · 2 = 6. Total binary variables/qubits n 2K = 18. Use the same distance construction as above. Assume … view at source ↗
read the original abstract

We formulate a global-position colored-permutation encoding for the capacitated vehicle routing problem. Each of the $K$ vehicles selects a disjoint partial permutation, and the sum of these $K$ color layers forms a full $n\times n$ permutation matrix that assigns every customer to exactly one visit position. This representation uses $n^2K$ binary decision variables arranged as $K$ color layers over a common permutation structure, while vehicle capacities are enforced by weighted sums over the entries of each color class, requiring no explicit load register and hence no extra logical qubits beyond the routing variables. In contrast, many prior quantum encodings introduce an explicit capacity or load representation with additional qubits. Our construction is designed to exploit the Constraint-Enhanced QAOA framework together with its encoded-manifold analyses. Building on a requirements-based view of quantum utility in CVRP, we develop a routing optimization formulation that directly targets one of the main near-term bottlenecks, namely the additional logical-qubit cost of vehicle labels and explicit capacity constraints. Our proposal shows strong algorithmic performance in addition to qubit efficiency. On a standard benchmark suite, our end-to-end pipeline recovers the independently verified optima. The feasibility oracle may also be of independent interest as a reusable polynomial-time decoding and certification primitive for quantum and quantum-inspired routing pipelines.

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 / 2 minor

Summary. The manuscript proposes a global-position colored-permutation encoding for the capacitated vehicle routing problem (CVRP). Each of K vehicles is assigned a disjoint partial permutation such that the sum of the K color layers yields a full n×n permutation matrix assigning every customer to exactly one visit position. The formulation uses exactly n²K binary decision variables with capacities enforced via weighted sums over entries in each color class, requiring no explicit load register or extra logical qubits. The encoding is designed to integrate with the Constraint-Enhanced QAOA framework and its manifold analyses; the end-to-end pipeline is reported to recover independently verified optima on standard benchmarks, and a polynomial-time feasibility oracle is introduced as a reusable primitive.

Significance. If the encoding is shown to capture all CVRP feasibility constraints without hidden violations and the performance claims are substantiated with explicit data, the result would offer a meaningful reduction in logical-qubit overhead for quantum routing problems relative to encodings that introduce separate capacity registers. The reusable feasibility oracle could serve as a general certification tool for both quantum and quantum-inspired pipelines. The work directly targets a documented near-term bottleneck in qubit-efficient CVRP formulations.

major comments (2)
  1. [Abstract] Abstract: the central performance claim that 'our end-to-end pipeline recovers the independently verified optima' is load-bearing yet unsupported by any benchmark table, error analysis, or explicit comparison data in the provided formulation; without these the assertion cannot be evaluated.
  2. [Encoding description] Encoding and capacity section: the claim that weighted-sum capacity enforcement within each color layer together with the Constraint-Enhanced QAOA manifold captures all CVRP constraints (routing, capacity, and visit uniqueness) without hidden violations or extra qubits rests on an unproven assertion; a concrete verification argument or small-instance exhaustive check is required to confirm the weakest assumption.
minor comments (2)
  1. [Abstract] The notation for the K color layers and the summation to a permutation matrix would benefit from an explicit small-n example (e.g., n=3, K=2) with the corresponding binary matrix shown.
  2. [Introduction] Prior quantum CVRP encodings that use explicit load registers should be cited with quantitative qubit counts for direct comparison.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback. We address each major comment below with clarifications and planned revisions to strengthen the manuscript.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central performance claim that 'our end-to-end pipeline recovers the independently verified optima' is load-bearing yet unsupported by any benchmark table, error analysis, or explicit comparison data in the provided formulation; without these the assertion cannot be evaluated.

    Authors: The results section presents benchmark outcomes on standard CVRP instances, reporting recovery of independently verified optima along with solution quality metrics. To make this claim directly evaluable from the abstract, we will revise the abstract to include a concise reference to the benchmark suite and performance, and ensure an explicit summary table with error analysis appears prominently in the main text. revision: yes

  2. Referee: [Encoding description] Encoding and capacity section: the claim that weighted-sum capacity enforcement within each color layer together with the Constraint-Enhanced QAOA manifold captures all CVRP constraints (routing, capacity, and visit uniqueness) without hidden violations or extra qubits rests on an unproven assertion; a concrete verification argument or small-instance exhaustive check is required to confirm the weakest assumption.

    Authors: The encoding section establishes that the permutation-matrix property enforces visit uniqueness, the disjoint color layers assign vehicles, and weighted sums enforce capacities without extra qubits, with the Constraint-Enhanced QAOA restricting to the feasible manifold. We will add a dedicated verification subsection containing a small-instance exhaustive enumeration (e.g., n=3, K=2) that confirms the encoded set matches exactly the feasible CVRP solutions with no hidden violations. revision: yes

Circularity Check

0 steps flagged

No significant circularity; encoding and performance claims are self-contained

full rationale

The paper directly defines a colored-permutation encoding for CVRP via disjoint partial permutations whose layers sum to a permutation matrix, with capacities enforced by per-color weighted sums on the n²K routing variables. This construction is presented as an explicit formulation rather than derived from or equivalent to fitted parameters, prior self-citations, or ansatzes. Benchmark recovery of independently verified optima supplies external validation outside the encoding's definitions. No equations reduce claims to inputs by construction, and the Constraint-Enhanced QAOA reference functions as a target framework rather than a load-bearing self-referential premise.

Axiom & Free-Parameter Ledger

2 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard properties of permutation matrices and the assumption that weighted sums suffice for capacity constraints; no new physical entities are postulated. Review is abstract-only so ledger entries are inferred at high level.

free parameters (2)
  • K (number of vehicles)
    Problem instance parameter that determines the number of color layers and total variables n²K.
  • n (number of customers)
    Problem size that sets the dimension of the permutation matrix.
axioms (2)
  • standard math A sum of K disjoint partial permutations forms a valid full permutation matrix that assigns each customer to exactly one position.
    Invoked to guarantee that every customer is visited exactly once.
  • domain assumption Weighted sums of entries within each color layer correctly enforce vehicle capacity limits.
    Central modeling choice that replaces explicit load registers.

pith-pipeline@v0.9.0 · 5545 in / 1469 out tokens · 89854 ms · 2026-05-10T19:57:33.563700+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages · 2 internal anchors

  1. [1]

    QOPTLib: a Quantum-Computing-Oriented Benchmark for Combinatorial Optimisation Problems

    Eneko Osaba and Erika Villar-Rodríguez. “QOPTLib: a Quantum-Computing-Oriented Benchmark for Combinatorial Optimisation Problems”. In:Proc.Quantum Tech. 2024. 2024

    work page 2024

  2. [2]

    AHybridSolutionMethodfortheCapacitatedVehicleRouting Problem Using a Quantum Annealer

    SebastianFeldetal.“AHybridSolutionMethodfortheCapacitatedVehicleRouting Problem Using a Quantum Annealer”. In:arXiv preprint arXiv:1811.07403(2018). doi: 10.48550/arXiv.1811.07403. arXiv:1811.07403 [quant-ph].url:https:// arxiv.org/abs/1811.07403

    work page doi:10.48550/arxiv.1811.07403 2018

  3. [3]

    Palackal, B

    L. Palackal et al. “Quantum-Assisted Solution Paths for the Capacitated Vehicle Routing Problem”. In:arXiv preprint arXiv:2304.09629(2023). doi: 10.48550/arXiv.2304.09629. arXiv:2304 . 09629 [quant-ph].url: https://arxiv.org/abs/2304.09629

    work page doi:10.48550/arxiv.2304.09629 2023

  4. [4]

    Christopher D. B. Bentley et al.Quantum computing for transport optimization

    work page

  5. [5]

    arXiv:2206.07313 [quant-ph].url:https://arxiv.org/abs/2206.07313

    work page arXiv

  6. [6]

    A Feasibility-Preserved Quantum Approximate Solver for the Capacitated Vehicle Routing Problem

    Ningyi Xie et al. “A Feasibility-Preserved Quantum Approximate Solver for the Capacitated Vehicle Routing Problem”. In:Quantum Information Processing23 (2024), p. 291.doi: 10.1007/s11128-024-04497-5

    work page doi:10.1007/s11128-024-04497-5 2024

  7. [7]

    Chinonso Onah, Roman Firt, and Kristel Michielsen.Empirical Quantum Advantage in Constrained Optimization from Encoded Unitary Designs. 2026. arXiv:2511 . 14296 [cs.ET].url:https://arxiv.org/abs/2511.14296

    work page arXiv 2026

  8. [8]

    Chinonso Onah and Kristel Michielsen.Fundamental Limitations of QAOA on Con- strained Problems and a Route to Exponential Enhancement. 2025. arXiv:2511 . 17259 [quant-ph].url:https://arxiv.org/abs/2511.17259

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  9. [9]

    Chinonso Onah and Kristel Michielsen.Finite-Depth, Finite-Shot Guarantees for Constrained Quantum Optimization via Fejér Filtering. 2026. arXiv:2603.01809 [quant-ph].url:https://arxiv.org/abs/2603.01809

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  10. [10]

    arXiv preprint arXiv:2509.11469

    Chinonso Onah and Kristel Michielsen.Requirements for Quantum Advantage and Quantum Utility in the Capacitated Vehicle Routing Problem. 2025.doi: 10.48550/arXiv.2509.11469. arXiv:2509.11469 [quant-ph]

    work page doi:10.48550/arxiv.2509.11469 2025

  11. [11]

    Zenodo, 2026.doi: 10.5281/zenodo.18798145

    Chinonso Onah.Data and Implementation: Optimal, Qubit-Efficient Quantum Vehi- cle Routing via Colored Permutations. Zenodo, 2026.doi: 10.5281/zenodo.18798145. url:https://doi.org/10.5281/zenodo.18798145

    work page doi:10.5281/zenodo.18798145 2026

  12. [12]

    Solving Vehicle Routing Problem Using Quantum Approximate Optimization Algorithm

    Utkarsh Azad et al. “Solving Vehicle Routing Problem Using Quantum Approximate Optimization Algorithm”. In:IEEE Transactions on Intelligent Transportation Sys- tems24.7 (2023), pp. 7564–7573.doi: 10.1109/TITS.2022.3172241

    work page doi:10.1109/tits.2022.3172241 2023

  13. [13]

    Quantum- assisted vehicle routing: Realizing qaoa-based approach on gate-based quantum computer,

    Talha Azfar et al.Quantum-Assisted Vehicle Routing: Realizing QAOA-Based Ap- proach on Gate-Based Quantum Computer. arXiv preprint. 2025. arXiv:2505.01614 [quant-ph]

    work page arXiv 2025

  14. [14]

    Applying Quantum Approximate Optimization to the Hetero- geneous Vehicle Routing Problem

    David Fitzek et al. “Applying Quantum Approximate Optimization to the Hetero- geneous Vehicle Routing Problem”. In:Scientific Reports14.1 (2024), p. 25415.doi: 10.1038/s41598-024-76967-w

    work page doi:10.1038/s41598-024-76967-w 2024

  15. [15]

    From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz

    Stuart Hadfield et al. “From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz”. In:Algorithms12.2 (2019), p. 34.doi: 10.3390/a12020034. 37

    work page doi:10.3390/a12020034 2019

  16. [16]

    Constraint Preserving Mixers for the Quantum Approximate Optimization Algorithm

    Franz G. Fuchs and Ruben Pariente Bassa. “Constraint Preserving Mixers for the Quantum Approximate Optimization Algorithm”. In:Algorithms15.6 (2022), p. 202. doi: 10.3390/a15060202

    work page doi:10.3390/a15060202 2022

  17. [17]

    Symmetries and dimension reduction in quantum approximate optimization algorithm.arXiv preprint arXiv:2309.13787, 2023

    B. Tsvelikhovskiy, I. Safro, and Y. Alexeev. “Symmetries and Dimension Reduction in Quantum Approximate Optimization Algorithm”. Version 2. In:arXiv preprint arXiv:2309.13787(2023). arXiv:2309.13787 [quant-ph].url:https://arxiv. org/abs/2309.13787

    work page arXiv 2023

  18. [18]

    On the Co-Design of Quantum Software and Hardware

    Gushu Li, Yufei Ding, and Yuan Xie. “On the Co-Design of Quantum Software and Hardware”. In:ICCAD ’21: IEEE/ACM International Conference on Computer- Aided Design. 2021.doi: 10.1145/3477206.3477464

    work page doi:10.1145/3477206.3477464 2021

  19. [19]

    Ayrton et al.Qiskit: An Open-source Framework for Quantum Computing

    M. Ayrton et al.Qiskit: An Open-source Framework for Quantum Computing. Ver- sion 0.47. 2023.url:https://qiskit.org

    work page 2023

  20. [20]

    Vidal,Efficient classical simulation of slightly entangled quantum computations, Phys

    Guifré Vidal. “Efficient Classical Simulation of Slightly Entangled Quantum Computations”. In:Phys. Rev. Lett.91.14 (2003), p. 147902.doi: 10.1103/PhysRevLett.91.147902

    work page doi:10.1103/physrevlett.91.147902 2003

  21. [21]

    2026.url:https: //www.gurobi.com

    Gurobi Optimization, LLC.Gurobi Optimizer Reference Manual. 2026.url:https: //www.gurobi.com

    work page 2026

  22. [22]

    Mathematical Programming 183(1):483--523, doi: 10.1007/s10107-020-01523-z

    Artur Pessoa et al. “A Generic Exact Solver for Vehicle Routing and Related Problems”. In:Mathematical Programming183.1–2 (2020), pp. 483–523.doi: 10.1007/s10107-020-01523-z

    work page doi:10.1007/s10107-020-01523-z 2020

  23. [23]

    A Unified Solution Framework for Multi-Attribute Vehicle Routing Problems

    Thibaut Vidal et al. “A Unified Solution Framework for Multi-Attribute Vehicle Routing Problems”. In:European Journal of Operational Research234.3 (2014), pp. 658–673.doi: 10.1016/j.ejor.2013.09.045

    work page doi:10.1016/j.ejor.2013.09.045 2014

  24. [24]

    Accessed: 2026-04-04

    DIMACS.12th DIMACS Implementation Challenge: CVRP Track.https://dimacs .rutgers.edu/files/1815/9845/6740/CVRP_Competition_Rules.pdf. Accessed: 2026-04-04. 2021

    work page 2026

  25. [25]

    Accessed: 2026-04-04

    CVRPLIB.All Instances.https://galgos.inf.puc-rio.br/cvrplib/en/instan ces. Accessed: 2026-04-04. 2026

    work page 2026

  26. [26]

    The Piecewise Constant Mumford and Shah Model: Mathematical Analysis

    Bruce L. Golden et al. “The Impact of Metaheuristics on Solving the Vehicle Routing Problem: Algorithms, Problem Sets, and Computational Results”. In:Fleet Man- agement and Logistics. Ed. by Teodor Gabriel Crainic and Gilbert Laporte. Boston, MA: Springer US, 1998, pp. 33–56.isbn: 978-1-4615-5755-5.doi: 10.1007/978-1- 4615-5755-5_2.url:https://doi.org/10....

    work page doi:10.1007/978-1- 1998

  27. [27]

    Paolo Toth and Daniele Vigo, eds.Vehicle Routing: Problems, Methods, and Applications. 2nd ed. MOS-SIAM Series on Optimization 18. SIAM, 2014.doi: 10.1137/1.9781611973594

    work page doi:10.1137/1.9781611973594 2014

  28. [28]

    Exact Branch-Price-and-Cut Algorithms for Vehicle Routing

    Luciano Costa, Claudio Contardo, and Guy Desaulniers. “Exact Branch-Price-and-Cut Algorithms for Vehicle Routing”. In:Transportation Science 53.4 (2019), pp. 946–985.doi: 10.1287/trsc.2018.0878. 38

    work page doi:10.1287/trsc.2018.0878 2019