8 January 2024 in Data Science for Transportation
10 September 2026 in Scientific Reports
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.
5 January 2026 in Research Square
The Quantum Approximate Optimization Algorithm (QAOA) is known to struggle on near-term hardware due to constraint handling, parameter search overhead, and tight depth limits. We address this with a hardware-aware co-design: a linear-ramp parameter schedule paired with a Linear-Chain (LC) ansatz that restricts $ZZ$ interactions to nearest neighbors, lowering swaps and depth. We benchmark Linear-Ramp LC-QAOA against standard QAOA, Two-Step QAOA, and Grover-Mixer QAOA on small VRP instances across ideal simulation, Aer simulation, and IBM Eagle/Heron runs, measuring feasibility, solution quality, and hardware efficiency. Linear-ramp improves convergence and feasibility; LC reduces two-qubit gates and boosts noise robustness. Grover-Mixer and Two-Step can aid constraints in theory but are hampered in practice by deeper circuits. On hardware, overall feasibility remains $<1$\%, yet LC-QAOA with $XpXm$ dynamical decoupling more than doubles feasibility and recovers the optimum in several trials. We also show efficient scaling, including a larger case with ramp-initialized LC-QAOA plus CVaR. The results underscore hardware-aligned ansätze and structured schedules as a promising path.