Curator's Take
AI Commentary
This article showcases a fully integrated hybrid pipeline that plugs quantum annealers and gate‑based QAOA solvers into the cut‑selection stage of Benders decomposition for mixed‑integer linear programs, using a realistic vehicle‑routing benchmark as proof‑of‑concept. By quantifying how little overall runtime the cut‑selection step consumes on modest instances, the authors demonstrate that current quantum hardware does not yet offer a speed advantage for problems of this scale, but they also lay out a clear path for future large‑scale testing once more powerful QPU solvers become available. The work is significant because it moves beyond isolated quantum subroutines toward an end‑to‑end workflow that could eventually accelerate industry‑relevant combinatorial optimization tasks.
— Mark Eatherly
Summary
We demonstrate an end-to-end hybrid quantum-classical optimisation framework based on Benders decomposition, capable of solving mixed-integer linear programming (MILP) problems. The framework builds on a previously presented hybrid quantum-classical end-to-end pipeline based on Multiple Cuts via Multiple Solutions (MCMS) Benders decomposition where the cut selection step was performed on quantum annealing hardware. We extend this with gate-based QAOA implementations for both tensor network emulators and superconducting quantum hardware. The Vehicle Routing Problem (VRP) is used as a representative case study and we run the pipeline end-to-end on 10 permutations of a standardised benchmarking instance (20 customers and 4 vehicles from QOptLib) with a classical solver performing the cut selection step. We find that for our instances, only a small fraction of the compute in classical MCMS Benders decomposition is spent on the cut selection step. For a full hybrid end-to-end assessment, we run the pipeline for a toy problem with MPS-JuliQAOA, a powerful tensor network emulator, to execute QAOA. Here, the majority of the time is spent on the cut selection step, deeming quantum advantage of this framework unlikely at problems of this size. This highlights the need for more large-scale benchmarking research when more powerful (QPU) QUBO solvers are available.