Quantum-Assisted Vehicle Routing: Realizing QAOA-based Approach on Gate-Based Quantum Computer

Technical Summary: Quantum-Assisted Vehicle Routing via QAOA on Gate-Based Hardware

Problem Definition
The Vehicle Routing Problem (VRP) is a fundamental NP-hard combinatorial optimization challenge central to logistics and transportation, aiming to minimize costs (distance, time, fuel) while satisfying constraints such as customer visitation, vehicle capacity, and route continuity. Classical algorithms struggle with optimal solutions for even modest-sized instances due to exponential scaling. This work addresses the challenge of mapping VRP onto gate-based quantum computers within the Noisy Intermediate-Scale Quantum (NISQ) regime, specifically focusing on the limitations imposed by circuit depth, qubit connectivity, and hardware noise.

Methodology
The authors propose a hardware-grounded framework integrating the Quantum Approximate Optimization Algorithm (QAOA) with a link-based formulation of the VRP. The methodology proceeds through the following stages:

1. Problem Formulation: The VRP is modeled using directional edge variables ($x_{i,j}$) representing whether a vehicle traverses a link between nodes $i$ and $j$. Unlike time-expanded or route-order formulations, this approach avoids explicit sequencing variables.
2. Constraint Encoding: Critical constraints—flow conservation (each customer visited exactly once), depot entry/exit counts, and subtour elimination—are encoded directly into the cost Hamiltonian ($H_C$) via penalty terms. This transforms the constrained problem into a Quadratic Unconstrained Binary Optimization (QUBO) problem.
3. Hamiltonian Mapping: The QUBO is mapped to an Ising Hamiltonian suitable for QAOA. The cost Hamiltonian consists of Pauli-Z terms ($Z_i$) for linear costs and Pauli-Z interactions ($Z_i Z_j$) for quadratic penalties. A standard mixing Hamiltonian ($H_M = \sum X_i$) is used to explore the solution space.
4. Circuit Implementation: The algorithm is implemented on the IBM Quantum System One (Eagle r3, 127 qubits). The workflow includes:
   • Transpilation: Mapping logical qubits to the physical heavy-hex lattice topology, introducing necessary swap gates.
   • Error Mitigation: Application of dynamic decoupling (to preserve coherence on idle qubits) and Pauli twirling (to convert noise channels into specific signatures).
   • Hybrid Optimization: A classical optimizer (COBYQA) iteratively tunes the variational parameters ($\gamma, \beta$) to minimize the expected cost $\langle \psi | H_C | \psi \rangle$.
5. Experimental Parameters: The study investigates the impact of penalty scaling (specifically setting penalty coefficients to twice the sum of edge weights) and coefficient normalization (bounding Pauli term magnitudes to one) on solution feasibility.

Key Contributions

• Directional Edge-Based Formulation: The authors develop a formulation that embeds flow conservation and subtour elimination directly into the cost Hamiltonian. This approach avoids the high qubit overhead of time-expanded formulations and the factorial complexity of route-order formulations, making it more suitable for near-term devices.
• Full Hardware Pipeline: The work executes the entire pipeline—from problem encoding and Ising mapping to circuit synthesis, transpilation, and execution—on real quantum hardware, rather than relying solely on idealized simulations.
• Empirical Analysis of Bottlenecks: The study quantitatively evaluates how VRP formulations impact qubit count and two-qubit gate depth after transpilation, identifying circuit depth as the primary bottleneck for constrained routing on current superconducting architectures.
• Parameter Sensitivity Insights: The research demonstrates that solution feasibility is critically dependent on penalty parameter selection and Hamiltonian coefficient normalization. Specifically, normalization significantly improves the sampling of feasible solutions for larger instances (4 and 5 nodes) where unnormalized approaches fail.

Results

• Small-Scale Success: For a 3-node, 2-vehicle instance, the QAOA successfully identified the optimal solution (bit-string 111010) with high probability, satisfying all constraints including subtour elimination.
• Scalability Challenges: As problem size increased (e.g., 4-node and 5-node instances), the number of required gates grew exponentially. A 4-node problem required a 14-qubit circuit with over 3,000 gates, taking over two hours to run, yet yielded infeasible solutions. A 5-node problem required a 30-qubit circuit with ~30,000 gates.
• Impact of Normalization: Without coefficient normalization, the algorithm failed to consistently identify optimal routes in the high-probability region for 4 and 5-node instances. With normalization and a penalty multiplier of 1.5–2.0, the feasibility ratio of the top 1,000 sampled bitstrings improved significantly.
• Hardware Limitations: The study confirms that current hardware noise and limited coherence times prevent the execution of deep QAOA circuits required for larger VRP instances. The top 10 sampled states for the 4-node problem were all infeasible without careful parameter tuning.

Significance and Claims
The paper claims significance not as a demonstration of quantum advantage over classical solvers for large-scale VRP, but as a practical, hardware-executed evaluation that clarifies current limitations in the NISQ era. The authors argue that while QAOA can theoretically solve VRP, the rapid growth in circuit complexity (specifically two-qubit gate depth) and noise accumulation currently restricts its application to very small instances.

The study's primary value lies in providing concrete design insights for future quantum optimization:

1. Formulation Choice: Edge-based formulations are currently more feasible than time-expanded or route-order encodings on available hardware due to lower qubit and gate requirements.
2. Parameter Heuristics: Coefficient normalization and specific penalty scaling (approx. 2x sum of edge weights) are essential for recovering feasible solutions on larger instances.
3. Methodological Direction: The work outlines that advancing quantum optimization for VRP requires not just algorithmic improvements but also hardware advancements (higher qubit counts, lower error rates) and hybrid strategies (e.g., transfer learning of parameters, dynamic circuits) to mitigate noise and depth constraints.

The authors conclude that while scalability remains constrained, this work establishes a practical pathway for implementing VRP on quantum hardware and identifies specific methodological directions necessary for future progress in near-term quantum optimization.