Quantum Model for CVRPTW

Imran Meghazi, Éric Bourreau · arXiv:2605.18393 · cross submission 2026-05-19 · score 8/10

Abstract

This paper proposes a quantum algorithm for the capacitated vehicle routing problem with time windows (CVRPTW) based on Grover Search framework. This problem is often faced by Postal services in the context of package delivery or other time-sensitive operations. We provide an implementation on gate based quantum computer of a model inspired by classical route first, cluster second technique. The quantum paradigm allows to overcome suboptimality inherent property of this decomposition. In the current NISQ (Noisy Intermediate-Scale Quantum) era, the most important limitation is the number of available qubits which makes time windows and capacity constraints hard to tackle. We introduce a qubit-efficient split-inspired modeling which adds only a linear number of decision qubits to standard quantum formulations for Traveling Salesman Problem (TSP).

Executive summary

This paper proposes the first Grover-Adaptive-Search-based oracle formulation for the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW). Rather than encoding subtour membership directly (the standard QUBO route-based approach, which has exponentially many decision variables), the authors adapt the classical route-first / cluster-second "split" procedure (Beasley 1983): encode a giant tour P plus a length-n binary register y of "start a new vehicle here" decisions, and Grover-search over (P, y) pairs. This adds only n decision qubits over a standard quantum TSP formulation. The contribution is conceptually adjacent to Yuan's Y4 (Grover + ADMM for cardinality-constrained binary optimization), with the difference that this paper's constraints are richer (capacity + time windows) and there is no ADMM-style hybrid loop or ε-approximation guarantee.

Main contribution

A qubit-efficient oracle-based CVRPTW formulation with explicit comparator subcircuits (Cuccaro et al. ripple-carry adder + Zhu et al. F-gate conditional encoder), full Grover Adaptive Search algorithm (§3, Algorithm 1), and a space-complexity analysis showing total qubit requirement O(n² + n log n + 6n + n log d_max + n log t_max + log w_max). The 147-qubit estimate for a 6-customer instance is the most concrete FT-era CVRPTW resource estimate published to date.

Key theorems / algorithms

Algorithm 1 (Grover Search CVRPTW): Adapts Dürr–Høyer Grover Adaptive Search for the capacitated vehicle routing problem with time windows. Uses a position-based encoding of the giant tour and a "split-inspired" linear-overhead modelling that adds only n decision qubits on top of standard TSP quantum formulations.
Capacity-constraint subcircuit (§3.1.2, Figure circ:capa): Implementation using ripple-carry adder components plus a conditional encoder (F gate from Zhu et al. 2022). Each cumulative load c_i is computed and tested against C_max with a single ancilla qubit.
Time-window constraint subcircuit (§3.1.3, Figure circ:time): Structurally similar to the capacity circuit but with an additional max(a_{Pi}, t_{i-1} + T) computation for the earliest-allowed-delivery vs travel-time comparison.
Space complexity (§3.2): Total qubit requirement is O(n² + n log n + 6n + n log d_max + n log t_max + log w_max). Of these, only n log n + n are decision qubits — the O(n²) dominant term is for ensuring tour validity (n(n-1)/2 pairwise inequality checks).
Empirical estimate: A 6-customer example with C_max = 5 and 8 time windows requires at least 147 qubits to encode.
Iteration count: Grover loop runs O(√(2^(n log n + n))) iterations, which dominates time complexity. Adaptive thresholding via the standard Dürr–Høyer protocol gives expected polynomial query complexity in n.

Detailed walkthrough

This is a method-direct match to Yuan's Y4 (Grover + ADMM for cardinality-constrained binary optimization), applied to a different but related combinatorial scope (CVRPTW). The method skeleton is Grover Adaptive Search of Dürr and Høyer (1999), adapted with a problem-specific oracle for the CVRPTW feasibility constraints.

The CVRPTW (Capacitated Vehicle Routing Problem with Time Windows) generalizes TSP with two hard constraints: per-vehicle capacity (sum of demands in a subtour ≤ C_max) and customer-specific time windows [a_i, b_i]. The classical state of the art relies on column generation over route-based formulations. Existing quantum approaches are either QUBO-based route formulations (route count grows exponentially with n) or time-expanded formulations (very large decision-variable count). The authors propose the first oracle-based formulation of CVRPTW, building on Beasley's classical route-first / cluster-second "split" procedure.

The encoding strategy (§2.3) is the key idea. Rather than encoding subtour membership directly, they encode a giant tour P (permutation of all n customers visited consecutively from the depot) and a length-n binary vector y, where y_i = 1 indicates "start a new vehicle subtour at position i". The classical split procedure constructs an auxiliary graph H on which finding a min-cost path from node 0 to n gives the optimal split. The quantum modelling lifts this: y is a quantum register, and Grover searches over (P, y) pairs.

Algorithm 1 implements the oracle. Inside the Grover iterate, the algorithm walks through the tour P sequentially, computing cumulative load c_i and arrival time t_i conditionally on y_i (if y_i = 1, reset the accumulator to depot; otherwise add the next edge's load / travel time). At each step it tests c_i ≤ C_max and t_i ≤ b_{Pi}. After the walk, it checks all distinctness constraints AD = ⋀_{i

The implementation details (§3) are the substantive contribution. The capacity comparator uses a single ancilla qubit and components from Cuccaro et al.'s ripple-carry adder (2004). The conditional encoder (F gate from Zhu et al. 2022) superposes demand values onto a quantum register indexed by P_i. The time-window circuit reuses these building blocks plus a max() comparator. Both circuits are explicitly drawn in quantikz (Figures 2 and 3 in the paper — not extractable to PNG because they are TikZ inline rather than included PDF/PNG figures).

The space complexity analysis (§3.2) is the most quantitatively useful part. The total qubit budget is O(n² + n log n + 6n + n log d_max + n log t_max + log w_max). The n² term dominates and comes from the n(n-1)/2 pairwise distinctness checks. The authors note that only n log n + n are "decision qubits" — the rest are workspace. For a 6-customer example with C_max = 5 and 8 time window slots, the total is 147 qubits. This is well beyond current NISQ scale but useful for fault-tolerant resource estimation.

The paper does not run hardware experiments. There is no comparison against Y4's complexity bound O(√(C(n,k)/M)) rotations because the feasible space here is more structured (CVRPTW with side constraints rather than fixed-cardinality binary). But the method is directly comparable in spirit: structured Grover search over feasible space, with a problem-specific oracle constructed from arithmetic comparators. A natural extension would be to combine the authors' qubit-efficient split-inspired modelling with Y4's ADMM-style classical-quantum hybrid loop, plugging in ε-approximation guarantees for the cost threshold.

The paper is short (12 pages, LNCS format) and reads as a conference contribution. The contribution is the encoding + oracle construction, not a complexity proof. For Yuan, the most useful aspect is the comparator subcircuit design — directly reusable for any future Y4 extension to multi-constraint feasible spaces.

Figures

No figures extracted from source (all figures are inline TikZ / quantikz circuits that require running LaTeX to render — not auto-convertible).

Citations to Yuan's papers

No direct citation to any of Y1–Y6 found in bibliography.

Overlap with Y1–Y6

Y4 (Grover + ADMM for cardinality-constrained BO): Strongest method overlap. Both use Grover Adaptive Search over a structured feasible space encoded by problem-specific oracles. Y4's contribution is the ε-approximation guarantees and the ADMM classical-quantum hybrid wrapper; this paper's contribution is the qubit-efficient split-inspired modelling and the explicit comparator subcircuits. The two are complementary: this paper's encoding + Y4's hybrid loop would yield a Grover+ADMM CVRPTW solver with provable ε-approximation.
Y2 (quasi-binary encoding for QAOA portfolio): Loose method overlap — both papers use qubit-efficient encodings for variables with bounded ranges (Y2's quasi-binary uses ~2 log₂(U−L+1) qubits per variable; this paper uses log d_max for cumulative load and log t_max for arrival time). Both encodings respect hard constraints structurally rather than via penalties. Worth flagging for any future encoding-comparison work.
Y1 (warm-started QAOA): Tangential — different algorithm family (Grover vs. QAOA) but shared design pattern of using classical structure (Y1: prior optimization round; this paper: classical split procedure) to inform the quantum loop.
Y3 (DGMVP QAOA portfolio): Tangential — same NISQ-era constrained combinatorial optimization scope, different algorithm family.

Recommended action for Yuan

Read deeper: The comparator + conditional-encoder subcircuit designs (§3.1) are reusable building blocks for any future Y4 extension to multi-constraint feasible spaces. Worth saving as a reference.
Adapt method: A natural Y4 follow-up is "Grover Adaptive Search for cardinality-constrained portfolio with side constraints (sector limits, turnover budgets)". This paper's split-inspired qubit-efficient modelling is the right starting framework for that extension.
Discuss with collaborators: If Yuan or co-authors are considering applied quantum optimization for logistics scope (vehicle routing, scheduling), this paper is the current state of the oracle-based formulation. The 147-qubit estimate for a 6-customer instance is a useful FT-era resource-estimation anchor.