Improving QAOA feasibility and hardware performance for vehicle routing via linear chain and ramp schedules

The Quantum Approximate Optimization Algorithm (QAOA) is difficult to deploy on near-term hardware for constrained routing problems because feasibility constraints produce dense interaction graphs, deep transpiled circuits, and costly parameter search. We study this challenge for Vehicle Routing Problem (VRP) instances using a hardware-aware QAOA workflow that combines linear-ramp parameter initialization, Conditional Value-at-Risk (CVaR) optimization, and a Linear-Chain QAOA (LC-QAOA) surrogate that retains local ZZ interactions to reduce two-qubit depth. A matched full-QAOA versus LC-QAOA feasibility comparison is performed for 4-node instances, while the 5- and 6-node experiments characterize circuit executability and low-probability optimum recovery at the tested depths. In 4-node hardware runs, LC-QAOA increases mean feasible-sample probability from 0.182% to 0.917% and mean optimum-sample probability from 0.045% to 0.239%, giving approximately \(5\times\) improvement over full QAOA. At 6 nodes, a full-QAOA circuit at \(p=1\) already has large transpiled two-qubit depth, while LC-QAOA remains executable and samples CPLEX-certified optima in selected hardware runs at depths p =10–13, albeit with low optimum probability. Overall, the results identify LC-QAOA as a hardware-efficient surrogate heuristic that trades Hamiltonian completeness for lower depth and improved feasible-solution sampling on noisy quantum hardware.