pith. sign in

arxiv: 2605.25350 · v1 · pith:XGXHMVQSnew · submitted 2026-05-25 · 💻 cs.DC

An Empirical Evaluation of Quantum-Inspired QUBO Methods for Heterogeneous HPC Workflow Mapping and Scheduling

Aasish Kumar Sharma , Christian Boehme , Julian Kunkel This is my paper

Pith reviewed 2026-06-29 20:56 UTC · model grok-4.3

classification 💻 cs.DC
keywords QUBOHPC schedulingworkflow mappingquantum-inspired optimizationfeasibility analysismakespan optimizationsimulated annealingconstraint satisfaction
0
0 comments X

The pith

QUBO schedulers for heterogeneous HPC workflows lose feasibility beyond 15 tasks while classical solvers stay reliable.

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

The paper conducts a systematic comparison of quantum-inspired QUBO methods against classical solvers for the combinatorial problem of mapping and scheduling workflows on heterogeneous high-performance computing systems under multiple hard constraints. It demonstrates that all approaches correctly recover optimal makespans on small validation cases but that specific QUBO variants experience feasibility collapse as task counts scale from 5 to 20 and when communication costs are activated. The work maps out the penalty values needed to restore feasibility and shows clear size thresholds where single-run simulated annealing and QAOA-inspired schedules fail while MILP, CP-SAT, genetic algorithms, and HEFT continue to succeed. A reader would care because the results delineate concrete regimes in which current quantum-inspired formulations remain impractical for real scheduling workloads.

Core claim

Quantum-inspired QUBO formulations recover the expected optimal makespan on validation instances with 3-4 tasks but exhibit feasibility degradation as constraint interactions intensify and instance sizes grow, with QUBO-SA losing feasibility beyond 15 tasks and the QAOA-inspired variant beyond 10 tasks, while classical solvers remain robust across the full range of 5-20 task synthetic instances under progressive constraint activation and penalty sweeps.

What carries the argument

The unified evaluation pipeline that measures feasibility, makespan, and resource utilization across single-run simulated annealing, multi-attempt annealing, and layered QAOA-inspired QUBO variants under controlled penalty sweeps and progressive constraint activation.

If this is right

  • For workflows exceeding 15 tasks, classical exact or heuristic solvers remain the reliable choice under present QUBO solver capabilities.
  • Communication costs must be handled with particular care in QUBO penalty design because they trigger the sharpest feasibility thresholds.
  • Multi-attempt annealing improves reliability over single-run annealing but does not remove the scaling ceiling.
  • Hybrid classical-quantum strategies are required to push QUBO applicability past the observed 10-15 task boundary.

Where Pith is reading between the lines

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

  • The observed feasibility boundaries may shift if real workflows contain denser or different constraint graphs than the synthetic patterns tested.
  • Improvements in QUBO solver technology or hardware could move the 15-task threshold outward without changes to the formulation itself.
  • The same penalty-sweep methodology could be applied to other mapping problems such as data-center resource allocation or scientific workflow orchestration.

Load-bearing premise

The synthetic scaling instances with 5-20 tasks and their chosen constraint interactions and communication patterns are representative of real heterogeneous HPC workflows.

What would settle it

Running the QUBO-SA formulation on a real heterogeneous HPC workflow containing 16 or more tasks and checking whether any feasible schedule is returned under the moderate-to-strong penalty regimes that succeeded on the synthetic instances.

Figures

Figures reproduced from arXiv: 2605.25350 by Aasish Kumar Sharma, Christian Boehme, Julian Kunkel.

Figure 2
Figure 2. Figure 2: Boxplots of QUBO-SA penalty sensitivity. [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Penalty sensitivity of QUBO-SA on the Medium [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Scaling behavior across 5-20 tasks. Top: feasibility rate as a function of problem size. Bottom: makespan gap relative to CP-SAT for feasible solutions only. Classical solvers remain robust across all scales, while QUBO variants exhibit feasibility degradation as problem size increases. both lower feasibility and higher solution quality variance at larger problem sizes. Overall, these results show that qua… view at source ↗
Figure 5
Figure 5. Figure 5: Scaling behavior across 5 to 20 tasks (3 instances per scale). [PITH_FULL_IMAGE:figures/full_fig_p009_5.png] view at source ↗
read the original abstract

Heterogeneous HPC workflow scheduling under multiple hard constraints poses a challenging combinatorial optimization problem. Classical exact solvers guarantee optimality but face scalability limits, motivating interest in quantum-inspired Quadratic Unconstrained Binary Optimization (QUBO) as an alternative optimization paradigm. This work presents a systematic empirical evaluation of QUBO-based scheduling methods against classical baselines including MILP, CP-SAT, GA, and HEFT. We evaluate three QUBO variants, single-run simulated annealing, multi-attempt annealing, and a layered QAOA-inspired schedule, with hybrid enhancement strategies on validation workflows (3-4 tasks) and synthetic scaling instances (5-20 tasks). All solvers are assessed through a unified pipeline tracking feasibility, makespan, and resource utilization under progressive constraint activation and controlled penalty sweeps. All approaches recover the expected optimal makespan on validation instances, confirming formulation correctness. However, feasibility degradation emerges for specific QUBO variants as constraint interactions intensify, particularly when communication costs are introduced. Penalty analysis reveals a sharp feasibility threshold for QUBO-SA, where insufficient penalties consistently fail and moderate-to-strong penalties restore feasibility. Scaling experiments show that classical solvers remain robust across all tested sizes, while QUBO-SA loses feasibility beyond 15 tasks and the QAOA-inspired variant beyond 10 tasks. The study provides a clear empirical characterization of the reliability boundaries of quantum-inspired QUBO formulations for HPC scheduling and identifies regimes where classical approaches remain preferable under current solver capabilities.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper presents an empirical evaluation of three QUBO variants (single-run simulated annealing, multi-attempt annealing, and a layered QAOA-inspired schedule) for heterogeneous HPC workflow mapping and scheduling under hard constraints, comparing them to classical baselines (MILP, CP-SAT, GA, HEFT) on validation instances (3-4 tasks) and synthetic scaling instances (5-20 tasks). It reports that all methods recover expected optimal makespan on validation instances but that QUBO-SA loses feasibility beyond 15 tasks and the QAOA-inspired variant beyond 10 tasks while classical solvers remain robust, thereby characterizing reliability boundaries and regimes favoring classical approaches.

Significance. If the observed feasibility thresholds hold on the tested instances, the work supplies a concrete empirical map of current practical limits for quantum-inspired QUBO formulations in constrained scheduling, which could usefully guide selection between solver families in HPC settings.

major comments (1)
  1. [Abstract] Abstract: the scaling experiments and the claim to identify 'reliability boundaries' and 'regimes where classical approaches remain preferable' rest exclusively on synthetic instances of 5-20 tasks, yet no details are supplied on instance generation procedure, task-graph structure, constraint densities, communication patterns, or any comparison against real HPC workflow traces. This directly undermines the load-bearing generalization from the reported thresholds (QUBO-SA beyond 15 tasks, QAOA beyond 10) to heterogeneous HPC workflows.
minor comments (2)
  1. [Abstract] Abstract: no error bars, variance measures, or number of independent runs are reported for the feasibility and makespan results.
  2. [Abstract] Abstract: exact numerical values of the penalty coefficients used in the sweeps are not stated, hindering reproducibility.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for highlighting the need for greater transparency in the abstract and experimental description. We will revise the manuscript accordingly while preserving the core empirical findings on the tested instances.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the scaling experiments and the claim to identify 'reliability boundaries' and 'regimes where classical approaches remain preferable' rest exclusively on synthetic instances of 5-20 tasks, yet no details are supplied on instance generation procedure, task-graph structure, constraint densities, communication patterns, or any comparison against real HPC workflow traces. This directly undermines the load-bearing generalization from the reported thresholds (QUBO-SA beyond 15 tasks, QAOA beyond 10) to heterogeneous HPC workflows.

    Authors: We agree that the abstract and main text should supply explicit details on the synthetic instance generation to support reproducibility and to avoid over-generalization. In the revised version we will: (1) expand the abstract to state that all scaling results derive from synthetically generated DAGs with 5–20 tasks; (2) add a new subsection describing the generation procedure, including how task-graph topologies, communication volumes, constraint densities, and penalty terms were constructed; and (3) qualify all claims about “reliability boundaries” and “regimes where classical approaches remain preferable” to refer specifically to the controlled synthetic instances examined. The study deliberately employs synthetic benchmarks to isolate scaling behavior under progressive constraint activation—an accepted methodology when the goal is to map feasibility thresholds rather than to benchmark against production traces. We therefore do not claim, and will not claim, direct applicability to arbitrary real HPC workflows. These changes directly address the referee’s concern about load-bearing generalization. revision: yes

Circularity Check

0 steps flagged

No circularity: pure empirical comparison with no derivation chain

full rationale

The paper is an empirical study that runs multiple solvers (QUBO-SA, QAOA-inspired, MILP, CP-SAT, GA, HEFT) on validation (3-4 task) and synthetic scaling (5-20 task) instances, reporting observed feasibility, makespan, and utilization under varying penalties and constraints. No equations, uniqueness theorems, ansatzes, or predictions are derived; all results are direct measurements against external classical baselines. The abstract and described methodology contain no self-referential definitions, fitted parameters renamed as predictions, or load-bearing self-citations that reduce the central claims to inputs by construction. The work is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The central empirical claims rest on the assumption that the QUBO encoding faithfully captures the scheduling constraints and that the synthetic instances adequately sample real constraint interactions; no new entities are postulated.

free parameters (1)
  • penalty coefficients
    Values swept across a range to locate the feasibility threshold for QUBO-SA; not fitted to a target result but explored experimentally.
axioms (1)
  • domain assumption The QUBO formulation correctly encodes all hard constraints of the heterogeneous HPC scheduling problem.
    Invoked when mapping the workflow mapping and scheduling problem to QUBO; confirmed only on the small validation set.

pith-pipeline@v0.9.1-grok · 5799 in / 1296 out tokens · 35083 ms · 2026-06-29T20:56:26.821204+00:00 · methodology

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

14 extracted references · 14 canonical work pages · 1 internal anchor

  1. [1]

    Performance-effective and low-complexity task scheduling for heterogeneous computing,

    H. Topcuoglu, S. Hariri, and M.-Y . Wu, “Performance-effective and low-complexity task scheduling for heterogeneous computing,”IEEE transactions on parallel and distributed systems, vol. 13, no. 3, pp. 260–274, 2002. [Online]. Available: https://doi.org/10.1109/71.993206

    work page doi:10.1109/71.993206 2002

  2. [2]

    Ibm ilog cp optimizer for scheduling: 20+ years of scheduling with constraints at ibm/ilog,

    P. Laborie, J. Rogerie, P. Shaw, and P. Vil ´ım, “Ibm ilog cp optimizer for scheduling: 20+ years of scheduling with constraints at ibm/ilog,” Constraints, vol. 23, no. 2, pp. 210–250, 2018. [Online]. Available: https://doi.org/10.1007/s10601-018-9281-x

    work page doi:10.1007/s10601-018-9281-x 2018

  3. [3]

    A tutorial on formulating and using qubo models,

    F. Glover, G. Kochenberger, and Y . Du, “A tutorial on formulating and using qubo models,”arXiv preprint arXiv:1811.11538, 2018. [Online]. Available: https://doi.org/10.48550/arXiv.1811.11538

    work page doi:10.48550/arxiv.1811.11538 2018

  4. [4]

    A Quantum Approximate Optimization Algorithm

    E. Farhi, J. Goldstone, and S. Gutmann, “A quantum approximate optimization algorithm,”arXiv preprint arXiv:1411.4028, 2014. [Online]. Available: https://doi.org/10.48550/arXiv.1411.4028

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.1411.4028 2014

  5. [5]

    Adiabatic quantum computation,

    T. Albash and D. A. Lidar, “Adiabatic quantum computation,”Reviews of Modern Physics, vol. 90, no. 1, p. 015002, 2018. [Online]. Available: https://doi.org/10.1103/RevModPhys.90.015002

    work page doi:10.1103/revmodphys.90.015002 2018

  6. [6]

    Drozdowski,Scheduling for parallel processing

    M. Drozdowski,Scheduling for parallel processing. Springer, 2009, vol. 18. [Online]. Available: https://doi.org/10.1007/978-1-84882-310-5

    work page doi:10.1007/978-1-84882-310-5 2009

  7. [7]

    Scheduling scientific workflow applications with deadline and budget constraints using genetic algorithms,

    J. Yu and R. Buyya, “Scheduling scientific workflow applications with deadline and budget constraints using genetic algorithms,”Scientific Programming, vol. 14, no. 3-4, pp. 217–230, 2006. [Online]. Available: https://doi.org/10.1155/2006/271608

    work page doi:10.1155/2006/271608 2006

  8. [8]

    Observation of topological phenomena in a programmable lattice of 1,800 qubits,

    A. D. King, J. Carrasquilla, J. Raymond, I. Ozfidan, E. Andriyash, A. Berkley, M. Reis, T. Lanting, R. Harris, F. Altomareet al., “Observation of topological phenomena in a programmable lattice of 1,800 qubits,”Nature, vol. 560, no. 7719, pp. 456–460, 2018. [Online]. Available: https://doi.org/10.1038/s41586-018-0410-x

    work page doi:10.1038/s41586-018-0410-x 2018

  9. [9]

    From the quantum approximate optimization algorithm to a quantum alternating operator ansatz,

    S. Hadfield, Z. Wang, B. O’gorman, E. G. Rieffel, D. Venturelli, and R. Biswas, “From the quantum approximate optimization algorithm to a quantum alternating operator ansatz,”Algorithms, vol. 12, no. 2, p. 34, 2019. [Online]. Available: https://doi.org/10.3390/a12020034

    work page doi:10.3390/a12020034 2019

  10. [10]

    Solving boolean satisfiability problems with the quantum approximate optimization algorithm,

    S. Boulebnane and A. Montanaro, “Solving boolean satisfiability problems with the quantum approximate optimization algorithm,” PRX Quantum, vol. 5, no. 3, p. 030348, 2024. [Online]. Available: https://doi.org/10.1103/PRXQuantum.5.030348

    work page doi:10.1103/prxquantum.5.030348 2024

  11. [11]

    Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem,

    R. Shaydulin, C. Li, S. Chakrabarti, M. DeCross, D. Herman, N. Kumar, J. Larson, D. Lykov, P. Minssen, Y . Sunet al., “Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem,”Science Advances, vol. 10, no. 22, p. eadm6761, 2024. [Online]. Available: https://doi.org/10.1126/sciadv.adm6761

    work page doi:10.1126/sciadv.adm6761 2024

  12. [12]

    Quantum approximate multi-objective optimization,

    A. Kotil, E. Pelofske, S. Riedm ¨uller, D. J. Egger, S. Eidenbenz, T. Koch, and S. Woerner, “Quantum approximate multi-objective optimization,”Nature Computational Science, pp. 1–10, 2025. [Online]. Available: https://doi.org/10.1038/s43588-025-00873-y

    work page doi:10.1038/s43588-025-00873-y 2025

  13. [13]

    A novel approach for solving constrained optimization problems with the quantum approximate optimization algorithm,

    B. Mete, “A novel approach for solving constrained optimization problems with the quantum approximate optimization algorithm,” M.Sc. Thesis, Technical University of Munich, Munich, Germany, May 2023. [Online]. Available: https://mediatum.ub.tum.de/doc/1661426/

    work page arXiv 2023

  14. [14]

    Grapheon RL: A Graph Neural Network and Reinforcement Learning Framework for Constraint and Data-Aware Workflow Mapping and Scheduling in Heterogeneous HPC Systems,

    A. K. Sharma, C. Boehme, P. Gelß, R. Yahyapour, and J. Kunkel, “Workflow-driven modeling for the compute continuum: An optimization approach to automated system and workload scheduling,” in2025 IEEE 49th Annual Computers, Software, and Applications Conference (COMPSAC). IEEE Xplore, 2025, pp. 2170–2177. [Online]. Available: https://doi.org/10.1109/COMPSAC...

    work page doi:10.1109/compsac65507.2025.00343 2025