QAOA Vehicle Routing — military logistics benchmark

Direct reproduction of the state-of-the-art gate-based QAOA vehicle routing benchmark — same qubit count, same optimum, air-gapped execution.

Azfar, Raisuddin, Ke, Holguín-Veras (2025) — gate-based QAOA VRP on IBM EaglearXiv

QAOA Vehicle Routing — military logistics benchmark

Top-10 sampled bitstrings from the trained QAOA circuit at 10,000 shots. Paper's classically-verified optimum |111010⟩ (encoding depot → node 1 → depot and depot → node 2 → depot) dominates at 28.8% — 18.4× the uniform-random baseline. Second-place state trails at 4.9%. Clean mode discrimination, direct reproduction of Azfar et al. Fig. 6.

28.8%

Sampling frequency of paper's optimum route |111010⟩ — 18.4× uniform-random baseline

[ overview ]

What this reproduces & why it matters

The Vehicle Routing Problem (VRP) is the canonical formulation for a huge family of DoD-relevant optimization problems: convoy routing under threat-graph constraints, aerial refueling tanker scheduling, resupply routing to forward-deployed units, ground-vehicle mission tasking under fuel/time budgets, and UAV mission planning.

Establishing that Qubital's QAOA pipeline reproduces the state-of-the-art academic VRP result — on the same qubit count, sampling the same optimal route at high frequency — is the direct prerequisite for extending to classified constrained-routing use cases in AFRL / AFLCMC / TRANSCOM logistics C2 workflows.

[ verified results ]

Every number below is [PASS]-checked in source.

verified

Sampling frequency of paper's optimum 10,000 shots, statevector	28.8%
Enrichment over uniform-random baseline baseline = 2⁻⁶ ≈ 1.56%	18.4×
Second-place state frequency clean mode discrimination	4.9%
Qubits matches paper's link-based encoding	6
QAOA depth 4 variational parameters	p = 2
COBYQA iterations to convergence ~4 min wall-clock local vs. ~14 min paper on IBM Eagle	~230

[ method ]

How it's built

3-node, 2-vehicle VRP with node 0 as depot (link-based encoding, 6 directed edges → 6 qubits). Cost Hamiltonian: 13 Pauli terms (6 single-Z + 7 Z⊗Z), derived algebraically from the paper's QUBO (Eq. 11) under Qiskit's x=(1-Z)/2 convention. QAOA at depth p=2 (4 parameters: γ₀, β₀, γ₁, β₁), standard X⊗ⁿ mixer, initial γ=π, β=π/2, COBYQA optimizer.

Our derivation caught a notational subtlety in the paper's Eq. 12: the Z-index labels are inverted relative to the mapping table under Qiskit's little-endian convention. The derived Hamiltonian's classical ground state is bitstring 010111 (Qiskit LE) = 111010 (paper convention) with energy +132.11, exactly matching the paper's classically-verified optimal route cost.

[ figures ]

Physics visuals

QAOA COBYQA optimization convergence — COBYQA trust-region exploration (purple, noisy) with best-so-far ⟨H_C⟩ (cyan) flatlining at −943. Classical ground state at −2220.59 shown for reference. For finite QAOA depth p the expected ⟨H_C⟩ is bounded above the ground — sampling probability is the operational metric, not raw energy.

Qubit and gate scaling vs VRP problem size — Qubit count scales O(N²) with the link-based encoding: 3-node = 6q, 4-node = 14q, 5-node = 30q. But 2-qubit gate count explodes exponentially on the log-scale axis. This is why the paper's 4-node experiment ran 2+ hours with all top-10 states infeasible; 5-node was outright intractable on IBM Eagle.

[ mitigation ]

What Qubital's ZNE buys you here

Baseline reproduction uses noiseless statevector sampling — paper's IBM Eagle run used dynamical decoupling + Pauli twirling for error suppression, no zero-noise extrapolation. Adding Richardson ZNE + PEC to the VRP QAOA pipeline is scoped as Phase I extension work, matching the mitigation layer Qubital ships on chemistry runs.

[ references ]

Papers & sources

Azfar, T., Raisuddin, O. M., Ke, R., Holguín-Veras, J. (2025). "Quantum-Assisted Vehicle Routing: Realizing QAOA-based Approach on Gate-Based Quantum Computer."
arXivThe reproduction target
Farhi, E., Goldstone, J., Gutmann, S. (2014). "A Quantum Approximate Optimization Algorithm."
arXiv
Ragodos, R. et al. (2025). "Hierarchical QAOA for the Vehicle Routing Problem via Clustered Decomposition."
arXivPath forward for Phase II scaling

[ what's next ]

Roadmap for this showcase

roadmap

Add ZNE mitigation to the QAOA loop (paper didn't) — replicates Qubital's chemistry mitigation stack for combinatorial problems
4-node instance with constraint-preserving XY-mixer + warm-start, attempting to beat the paper's 4-node infeasibility failure mode
Defense-specific graph structures: notional threat-corridor convoy routing, tanker-track scheduling on realistic USAF topology
Hierarchical decomposition (Ragodos 2025) for instances larger than 12 qubits

[ request access ]

Want to run this yourself?

The physics-showcases repo is currently private, protecting IP pre-revenue. Physicists, quantum-industry contacts, and investors: reach out and I'll set up a technical walkthrough, call, or Loom.

Request a walkthrough

Showcase #7

BH VQE — toward UHTC materials chemistry

Showcase #9

XY Model — quantum simulation of magnetic materials