Data and Implementation: Optimal, Qubit-Efficient Quantum Vehicle Routing via Colored Permutations

Zenodo (CERN European Organization for Nuclear Research)

Abstract

We formulate capacitated vehicle routing as a colored permutation problem: each of the K vehicles selects a disjoint partial permutation, and the sum of these K submatrices forms a full n × n permutation matrix that assigns everycustomer to exactly one visit position. This representation requires no explicit load register (and hence no extra qubits) beyondthe routing variables. In contrast, prior quantum encodings introduce an explicit capacity/load representation with O(Q) or O(log Q) additional qubits for capacity Q [1, 2]. Our construction is designed to satisfy the kernel requirement of the Constraint-Enhanced QAOA (CE-QAOA) framework [3], making the resulting VRP instances compatible with its feasibility- and finite-shot guarantees [4, 5]. On the full benchmark suite of [6], our p = 1 CE–QAOA implementation recovers the certified optimum for every instance, without decomposition. All results are fully reproducible from the companion artifact archive in Ref. [7].

Authors 1

1. Chinonso Onah corresponding Aachen

   RWTH Aachen University · Volkswagen Group (Germany)

   Affiliation as printed

   Volkswagen Group (Germany)

   RWTH Aachen University