Pith. sign in

REVIEW 2 major objections 6 minor 32 references

At the vehicle-routing sizes tested, cut selection is not the bottleneck in MCMS Benders, so a quantum QAOA step is unlikely to help.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-30 21:32 UTC pith:PUCXO67D

load-bearing objection Honest engineering extension of Paterakis: cut selection is not the classical bottleneck on these VRPs, so this QAOA insertion point looks weak at the sizes they can actually run. the 2 major comments →

arxiv 2607.26771 v1 pith:PUCXO67D submitted 2026-07-29 quant-ph

Hybrid quantum-classical end-to-end pipeline for solving MILPs: a vehicle routing case study

Camille de Valk , Koen Reerink , Siert Sebus , S\'ebastian de Bon This is my paper
classification quant-ph
keywords Benders decompositionHybrid Quantum ComputingQUBOVehicle Routing ProblemQAOAMCMScut selectionMILP
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper builds a full hybrid pipeline that solves mixed-integer linear programs by Benders decomposition, handing the cut-selection step to QAOA on gate-based emulators and hardware. The authors take a standard vehicle-routing benchmark (20 customers, 4 vehicles) and show that, when cut selection is done classically, almost all iteration time goes into solving the master problem; cut selection itself is a small fraction of the work. On smaller toy instances they close the loop with a tensor-network QAOA solver and find the opposite: cut selection then consumes the bulk of wall-clock time and is far slower than a classical MIP solver. The central claim is therefore negative but practical: quantum advantage for this particular cut-selection formulation is unlikely at the problem sizes examined, and only large-scale tests with faster QUBO solvers can decide whether the bottleneck ever moves.

Core claim

For the QOptLib VRP instances examined, classical MCMS Benders spends only a small fraction of each iteration on cut selection (master-problem solving dominates). When the same cut-selection step is performed by QAOA on a toy VRP, that step accounts for roughly 99 percent of wall-clock time, making quantum advantage for the framework unlikely at these sizes.

What carries the argument

HQC-MCMS Benders: multiple candidate solutions per iteration generate a pool of cuts that is reduced by solving a minimum-set-cover QUBO with QAOA; the selected cuts are returned to the classical master problem.

Load-bearing premise

That the relative cost of cut selection versus master and subproblem solves seen at these small sizes will still decide whether cut selection is the right place to put a quantum solver when instances grow.

What would settle it

A scaling study on larger VRPs (or other MILPs) in which cut-selection QUBOs become both large enough that classical solvers slow down and cheap enough on future QUBO hardware that total Benders time drops below a strong classical baseline.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • At the scales tested, accelerating cut selection alone will not speed up MCMS Benders for VRP.
  • End-to-end hybrid pipelines must measure wall-clock share of every stage, not only the quantum subroutine.
  • Set-cover-to-QUBO encoding overhead remains a first-order obstacle even if a fast QUBO oracle appears.
  • Large-scale benchmarking with stronger QUBO solvers is required before claiming advantage for this architecture.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Master-problem growth, not cut selection, is the more promising classical target for speed-ups in multi-cut Benders.
  • Alternative cut-selection encodings (maximum independent set, HUBO) will face the same bottleneck test: they must dominate runtime before a quantum oracle can matter.
  • The negative result is useful as a template for other hybrid MILP claims that have not yet published stage-by-stage timings.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 6 minor

Summary. The manuscript presents an end-to-end hybrid quantum–classical pipeline that embeds QAOA (on tensor-network emulators and IBM superconducting hardware) into the cut-selection step of Multiple-Cuts-via-Multiple-Solutions (MCMS) Benders decomposition for MILPs, extending Paterakis’s annealing-based HQC-MCMS framework. Using the capacitated VRP as a case study, the authors run fully classical MCMS on 10 permutations of a QOptLib instance (20 customers, 4 vehicles) and a hybrid end-to-end pipeline on five random toy VRPs (n=5) with MPS-JuliQAOA. They report that cut selection is a negligible fraction of classical iteration time (master-problem solves dominate; Fig. 3), whereas on the toys ~99.3% of wall-clock time is spent in QAOA cut selection, so quantum advantage for this insertion point is unlikely at the sizes considered. They also demonstrate QAOA sample statistics on a small set-cover instance across three backends (Fig. 5).

Significance. The contribution is primarily empirical and infrastructural: a working, publicly coded end-to-end bridge from MCMS Benders to gate-based QAOA solvers, plus a clear, modestly scoped negative result on bottleneck location. That honesty is valuable for the hybrid-optimisation community; the paper does not over-claim asymptotic advantage and explicitly flags the need for larger-scale tests once stronger QUBO oracles exist. Reproducible code, standardised QOptLib instances, and multi-backend QAOA runs are concrete strengths. Significance is incremental rather than transformative, but appropriate for a methods/applications venue.

major comments (2)
  1. [§V-A, Fig. 3; §VI] §V-A / Fig. 3 and §VI: The central classical claim (cut selection is a negligible fraction of iteration time) rests on Cbc with sequential extraction of multiple feasible master solutions. The authors note that commercial solvers can extract multiple solutions far more cheaply, which would further shrink the relative cost of cut selection and strengthen, not weaken, their conclusion. Still, a short quantitative sensitivity check—or at least a clearer statement that the reported MP times are an upper bound on the classical bottleneck—would make the load-bearing timing comparison more robust before readers generalise beyond open-source solvers.
  2. [§V-B; Abstract] §V-B and Abstract: The hybrid end-to-end assessment (and the 99.3% cut-selection share) is performed only on n=5 toys with p=1 MPS-JuliQAOA. The wording “quantum advantage of this framework unlikely at problems of this size” is therefore well-supported for the toys but is easy to misread as applying to the QOptLib scale. A single clarifying sentence that separates the classical bottleneck profile (n=20) from the hybrid runtime profile (n=5) would prevent over-extrapolation while preserving the paper’s careful stance.
minor comments (6)
  1. [Fig. 4] Fig. 4 caption writes “HQC-MCMC Benders” instead of “HQC-MCMS Benders”.
  2. [Table I] Table I header “QOptLib MCMS Toy HQC-MCMS” is hard to parse; a two-column layout (Classical QOptLib | Hybrid toy) would be clearer.
  3. [§V-A, Eq. (14)] Eq. (14) defines the optimality gap with an “∞ else” branch that is never plotted; a brief note on how unbounded cases are handled in Fig. 2 would help.
  4. [§V-C, Fig. 5] Fig. 5: most QAOA samples are infeasible set covers. The text already mentions post-selection of the lowest-cost valid cover; stating the acceptance rate (or number of shots needed to obtain one valid cover) would make the practical overhead transparent.
  5. [References] References [14] and [15] have 2026 dates; confirm they are citable or mark as preprints consistently with the rest of the bibliography.
  6. [Title page / passim] Minor typography: “1st Camille de Valk” style author block and occasional missing spaces around citations could be cleaned for camera-ready.

Circularity Check

0 steps flagged

No significant circularity: empirical pipeline timings and gaps are measured outputs, not quantities forced by definition or self-citation.

full rationale

This is an engineering/empirical paper that implements HQC-MCMS Benders with QAOA cut selection and reports wall-clock shares and optimality gaps on VRP instances. The central claims (cut selection is a small fraction of classical MCMS iteration time on QOptLib n=20; ~99.3% of toy HQC-MCMS time is spent in MPS-JuliQAOA cut selection, so advantage is unlikely at these sizes) are direct measurements from Figures 2–5 and §V, not predictions derived from fitted parameters or from defining the target in terms of the input. Dependence on Paterakis [1] is ordinary prior-art reuse of the MCMS/set-cover-as-QUBO framing by a different author group; it does not load-bear a uniqueness claim or force the timing results. QAOA parameter tuning (COBYLA) is internal to each cut-selection call and is not used to define the optimality-gap metric. No self-definitional loop, fitted-input-as-prediction, self-citation uniqueness import, or renaming of a known result appears in the derivation chain. Score 0 is appropriate.

Axiom & Free-Parameter Ledger

5 free parameters · 5 axioms · 0 invented entities

Load-bearing content is standard OR + standard QAOA engineering. No new physical entities. Free parameters are ordinary solver/QAOA knobs. Domain assumptions are classical Benders correctness, the heuristic that min-set-cover over candidate cuts is a useful selection proxy, and the QUBO penalty encoding of coverage constraints (inherited from [1]).

free parameters (5)
  • QAOA depth p = 1 or 3
    Chosen as p∈{1,3} for demos; affects sample quality and runtime but is not fitted to claim a universal optimum.
  • MPS bond dimension χ = 64
    Emulator accuracy/cost knob set to 64 for both tensor-network backends.
  • QAOA shots and COBYLA budget = 1000 shots; ≤1000 COBYLA iters
    1000 shots; COBYLA ρ_beg=π/2, max 1000 iterations—hand-chosen experimental settings.
  • Number of subproblems per MCMS iteration = 2–64 (classical); 5 (toy)
    Swept over {2,4,16,64} classically and 5 for toy hybrid; controls cut-pool size and iteration cost.
  • Time and iteration limits = 1.5h/2500; 4h/1000
    1.5 h / 2500 iters (benchmark), 4 h / 1000 iters (toy)—administrative cutoffs that shape reported gaps.
axioms (5)
  • standard math Classical Benders decomposition with optimality/feasibility cuts from dual subproblems converges to the MILP optimum when cuts are valid and the master is solved to optimality.
    Invoked throughout §II-A and the pipeline; standard OR theory [10],[16].
  • domain assumption Selecting a minimum set of cuts that cover infeasible master solutions (min set cover on matrix M) is a useful proxy for ‘informative’ cut selection in multi-cut Benders.
    §III-A formulation (11)–(13); inherited from Paterakis [1] and multi-cut heuristics [22]; not proved optimal for convergence rate.
  • domain assumption Coverage constraints can be moved into a QUBO objective via penalties so that low-energy samples (after filtering) yield valid covers.
    §III-B; authors note QAOA is unconstrained and they filter feasible covers from shots—standard but lossy encoding.
  • standard math VRP MILP with MTZ subtour-elimination (4)–(10) correctly models the capacitated VRP instance class used.
    §II-B; classical formulation [23].
  • domain assumption Open-source solvers Cbc and HiGHS return sufficiently accurate master solutions and dual extreme rays for cut generation in these experiments.
    §IV and Table I; practical solver trust, not a theorem.

pith-pipeline@v1.2.0-daily-grok45 · 15183 in / 3695 out tokens · 67522 ms · 2026-07-30T21:32:51.744717+00:00 · methodology

0 comments
read the original abstract

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.

Figures

Figures reproduced from arXiv: 2607.26771 by Camille de Valk, Koen Reerink, S\'ebastian de Bon, Siert Sebus.

Figure 1
Figure 1. Figure 1: A visual overview of our framework, which is adapted from Paterakis [1]. It employs the HQC-MCMS Benders decomposition algorithm, delegating [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Optimality gap, see Equation (14), over iterations for 10 permutations of one VRP from QOptLib [2]. The gap decreases as the algorithm converges, [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Timings of different parts of the end-to-end optimisation pipeline over iterations for 10 permutations of one VRP from QOptLib [2]. The solid line [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Convergence of our HQC-MCMS Benders solver for 5 random toy [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Examples of sample frequencies from a QAOA circuit for different [PITH_FULL_IMAGE:figures/full_fig_p006_5.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

32 extracted references · 4 linked inside Pith

  1. [1]

    Hybrid quantum-classical multi- cut benders approach with a power system applica- tion,

    N. G. Paterakis, “Hybrid quantum-classical multi- cut benders approach with a power system applica- tion,”Computers & Chemical Engineering, vol. 172, p. 108 161, 2023

    2023

  2. [2]

    Qoptlib: A quan- tum computing oriented benchmark for combinatorial optimization problems,

    E. Osaba and E. Villar-Rodriguez, “Qoptlib: A quan- tum computing oriented benchmark for combinatorial optimization problems,” inBenchmarks and Hybrid Algorithms in Optimization and Applications, Springer, 2023, pp. 49–63

    2023

  3. [3]

    Quantum computing in logistics and supply chain management an overview,

    F. Phillipson, “Quantum computing in logistics and supply chain management an overview,”arXiv preprint arXiv:2402.17520, 2024

    Pith/arXiv arXiv 2024

  4. [4]

    A quantum approximate optimization algorithm,

    E. Farhi et al., “A quantum approximate optimization algorithm,”arXiv preprint arXiv:1411.4028, 2014

    Pith/arXiv arXiv 2014

  5. [5]

    Quantum information processing with su- perconducting circuits: A review,

    G. Wendin, “Quantum information processing with su- perconducting circuits: A review,”Reports on Progress in Physics, vol. 80, no. 10, p. 106 001, 2017

    2017

  6. [6]

    The theory of variational hybrid quantum-classical algorithms,

    J. R. McClean et al., “The theory of variational hybrid quantum-classical algorithms,”New Journal of Physics, vol. 18, no. 2, p. 023 023, 2016

    2016

  7. [7]

    Advancements in superconducting quantum computing,

    Y .-Y . Jiang et al., “Advancements in superconducting quantum computing,”National Science Review, vol. 12, no. 8, nwaf246, 2025

    2025

  8. [8]

    The unexpected power of linear programming: An updated collection of surprising ap- plications,

    B. Golden et al., “The unexpected power of linear programming: An updated collection of surprising ap- plications,”Annals of Operations Research, vol. 343, no. 2, pp. 573–605, 2024

    2024

  9. [9]

    Mixed integer pro- gramming: Analyzing 12 years of progress,

    T. Achterberg and R. Wunderling, “Mixed integer pro- gramming: Analyzing 12 years of progress,” inFacets of combinatorial optimization: Festschrift for martin gr¨otschel, Springer, 2013, pp. 449–481

    2013

  10. [10]

    Partitioning procedures for solving mixed- variables programming problems,

    J. Benders, “Partitioning procedures for solving mixed- variables programming problems,”Numer. math, vol. 4, no. 1, pp. 238–252, 1962

    1962

  11. [11]

    Hybrid quantum benders’ decompo- sition for mixed-integer linear programming,

    Z. Zhao et al., “Hybrid quantum benders’ decompo- sition for mixed-integer linear programming,” in2022 IEEE Wireless Communications and Networking Con- ference (WCNC), IEEE, 2022, pp. 2536–2540

    2022

  12. [12]

    Mixed-integer linear programming solver using benders decomposition assisted by a neutral-atom quantum processor,

    M. Y . Naghmouchi and W. d. S. Coelho, “Mixed-integer linear programming solver using benders decomposition assisted by a neutral-atom quantum processor,”Physical Review A, vol. 110, no. 1, p. 012 434, 2024

    2024

  13. [13]

    A hybrid quantum–classical algorithm for mixed-integer optimization in power systems,

    P. Ellinas et al., “A hybrid quantum–classical algorithm for mixed-integer optimization in power systems,”Elec- tric Power Systems Research, vol. 235, p. 110 835, 2024

    2024

  14. [14]

    Accelerating extended benders decomposition with quantum-classical hybrid solver,

    T. Yoshihara and M. Ohzeki, “Accelerating extended benders decomposition with quantum-classical hybrid solver,”Journal of the Physical Society of Japan, vol. 95, no. 3, p. 033 001, 2026

    2026

  15. [15]

    Performance enhancing of hybrid quantum-classical benders approach for milp optimization,

    S. L ´opez-Ba˜nos et al., “Performance enhancing of hybrid quantum-classical benders approach for milp optimization,”arXiv preprint arXiv:2601.14024, 2026

    Pith/arXiv arXiv 2026

  16. [16]

    The benders decomposition algorithm: A literature review,

    R. Rahmaniani et al., “The benders decomposition algorithm: A literature review,”European Journal of Operational Research, vol. 259, no. 3, pp. 801–817, 2017

    2017

  17. [17]

    Quantum annealing applications, challenges and limitations for optimisation problems compared to classical solvers — scientific reports,

    F. A. Quinton et al., “Quantum annealing applications, challenges and limitations for optimisation problems compared to classical solvers — scientific reports,” en, Scientific Reports, vol. 15, no. 1, p. 12 733, Apr. 2025, ISSN: 2045-2322

    2025

  18. [18]

    Non-zero noise extrapolation: Accurately simulating noisy quantum circuits with ten- sor networks,

    A. P. Thompson et al., “Non-zero noise extrapolation: Accurately simulating noisy quantum circuits with ten- sor networks,”arXiv preprint arXiv:2501.13237, 2025. [19]Ava — fermioniq, en

    arXiv 2025

  19. [20]

    Javadi-Abhari et al.,Quantum computing with Qiskit, 2024

    A. Javadi-Abhari et al.,Quantum computing with Qiskit, 2024

    2024

  20. [21]

    Vehicle routing problems over time: A survey,

    A. Mor and M. G. Speranza, “Vehicle routing problems over time: A survey,”Annals of Operations Research, vol. 314, no. 1, pp. 255–275, 2022

    2022

  21. [22]

    Accelerating ben- ders decomposition: Multiple cuts via multiple solu- tions,

    N. Beheshti Asl and S. MirHassani, “Accelerating ben- ders decomposition: Multiple cuts via multiple solu- tions,”Journal of Combinatorial Optimization, vol. 37, no. 3, pp. 806–826, 2019

    2019

  22. [23]

    Integer programming formulation of traveling salesman problems,

    C. E. Miller et al., “Integer programming formulation of traveling salesman problems,”Journal of the ACM (JACM), vol. 7, no. 4, pp. 326–329, 1960

    1960

  23. [24]

    A review on quantum approximate op- timization algorithm and its variants,

    K. Blekos et al., “A review on quantum approximate op- timization algorithm and its variants,”Physics Reports, vol. 1068, pp. 1–66, Jun. 2024,ISSN: 03701573

    2024

  24. [25]

    Feeney et al.,Mps-juliqaoa: User-friendly, scalable mps-based simulation for quantum optimization, 2025

    S. Feeney et al.,Mps-juliqaoa: User-friendly, scalable mps-based simulation for quantum optimization, 2025

    2025

  25. [26]

    Efficient tensor network simulation of ibm’s largest quantum processors,

    S. Patra et al., “Efficient tensor network simulation of ibm’s largest quantum processors,”Phys. Rev. Res., vol. 6, p. 013 326, 1 Mar. 2024

    2024

  26. [27]

    Forrest et al.,Coin-or/cbc: Release releases/2.10.13, version releases/2.10.13, Mar

    J. Forrest et al.,Coin-or/cbc: Release releases/2.10.13, version releases/2.10.13, Mar. 2026

    2026

  27. [28]

    Parallelizing the dual re- vised simplex method,

    Q. Huangfu and J. A. J. Hall, “Parallelizing the dual re- vised simplex method,” en,Mathematical Programming Computation, vol. 10, no. 1, pp. 119–142, Mar. 2018, ISSN: 1867-2949, 1867-2957

    2018

  28. [29]

    S. G. Johnson,The NLopt nonlinear-optimization pack- age, https://github.com/stevengj/nlopt, 2007

    2007

  29. [30]

    Towards robust benchmarking of quantum optimization algorithms,

    D. Bucher et al., “Towards robust benchmarking of quantum optimization algorithms,” in2024 IEEE In- ternational Conference on Quantum Computing and Engineering (QCE), vol. 03, Sep. 2024, pp. 159–170

    2024

  30. [31]

    Ebadi et al.,Quantum Optimization of Max- imum Independent Set using Rydberg Atom Ar- rays, en, arXiv:2202.09372 [cond-mat, physics:physics, physics:quant-ph], Feb

    S. Ebadi et al.,Quantum Optimization of Max- imum Independent Set using Rydberg Atom Ar- rays, en, arXiv:2202.09372 [cond-mat, physics:physics, physics:quant-ph], Feb. 2022

    Pith/arXiv arXiv 2022

  31. [32]

    Bias-field digitized counterdiabatic quantum algorithm for higher-order binary optimiza- tion,

    S. V . Romero et al., “Bias-field digitized counterdiabatic quantum algorithm for higher-order binary optimiza- tion,” en,Communications Physics, vol. 8, no. 1, p. 348, Aug. 2025,ISSN: 2399-3650

    2025

  32. [33]

    C. Q. de Valk,Hqc mcms benders, https://github.com/ camilledevalk/hqc-mcms-benders, 2026

    2026