Heterogeneous HPC workflow scheduling under multiple hard constraints poses a challenging combinatorial optimization problem. Classical exact solvers provide optimal solutions but often face scalability limitations, motivating interest in quantum-inspired Quadratic Unconstrained Binary Optimization (QUBO) formulations as alternative optimization paradigms. This work presents a systematic and reproducible empirical evaluation of QUBO-based scheduling methods against established 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, together with hybrid enhancement strategies on both ground-truth validation workflows (3–4 tasks) and synthetic scaling instances (5–20 tasks). All solvers are assessed through a unified evaluation pipeline that explicitly tracks feasibility, makespan, and resource utilization under progressive constraint activation and controlled penalty sweeps. Results show that 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 sensitivity analysis reveals a sharp feasibility threshold for QUBO-SA, where insufficient penalties consistently fail and moderate-to-strong penalties restore feasibility. Scaling experiments delineate the regimes in which classical solvers and heuristics remain robust across all tested sizes, while QUBO-SA loses feasibility beyond 15 tasks and the QAOA-inspired variant beyond 10 tasks. Overall, the study provides a clear empirical characterization of the reliability boundaries of quantum-inspired QUBO formulations for heterogeneous HPC scheduling and identifies the regimes where classical approaches remain preferable under current formulations and solver capabilities.
Heterogeneous HPC workflow scheduling under multiple hard constraints poses a challenging combinatorial optimization problem. Classical exact solvers provide optimal solutions but often face scalability limitations, motivating interest in quantum-inspired Quadratic Unconstrained Binary Optimization (QUBO) formulations as alternative optimization paradigms. This work presents a systematic and reproducible empirical evaluation of QUBO-based scheduling methods against established 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, together with hybrid enhancement strategies on both ground-truth validation workflows (3–4 tasks) and synthetic scaling instances (5–20 tasks). All solvers are assessed through a unified evaluation pipeline that explicitly tracks feasibility, makespan, and resource utilization under progressive constraint activation and controlled penalty sweeps. Results show that 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 sensitivity analysis reveals a sharp feasibility threshold for QUBO-SA, where insufficient penalties consistently fail and moderate-to-strong penalties restore feasibility. Scaling experiments delineate the regimes in which classical solvers and heuristics remain robust across all tested sizes, while QUBO-SA loses feasibility beyond 15 tasks and the QAOA-inspired variant beyond 10 tasks. Overall, the study provides a clear empirical characterization of the reliability boundaries of quantum-inspired QUBO formulations for heterogeneous HPC scheduling and identifies the regimes where classical approaches remain preferable under current formulations and solver capabilities.
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.
This paper investigates several Quadratic Unconstrained Binary optimisation (QUBO) formulations for the parallel machine scheduling problem P m | | C max with the goal of assessing their suitability for quantum annealing and related heuristic optimisation methods. Three QUBO models are constructed, ranging from formulations derived from classical integer and one-hot encodings to a more compact load-balancing based representation. Extensive computational experiments using Simulated Annealing (SA) and Quantum Annealing (QA) reveal substantial differences in scalability and solution quality among the formulations. The alternative load-balanced model consistently yields near-optimal makespans, typically within 1%–3% of the theoretical lower bound, highlighting its stability and effectiveness compared to the more penalty sensitive formulations, whose performance deteriorates for larger instances. Sensitivity analyses further reveal that the appropriate selection of penalty weights and problem-specific parameter tuning significantly influences both solution accuracy and computational effort in QUBO formulations. While current quantum hardware limitations restrict experimentation to small problem sizes, the findings illustrate how compact QUBO designs can better exploit quantum optimisation frameworks. The insights gained in this study provide practical modelling guidelines for future quantum scheduling research and lay the groundwork for extending QUBO-based approaches to more complex scheduling environments. • Three QUBO formulations are compared for identical parallel machine scheduling. • A compact load-balancing QUBO avoids auxiliary variables. • Load balancing yields makespans on average within 1–3%. • Both simulated and quantum annealing produce near-optimal schedules. • Penalty selection and encoding strongly affect scalability and solution quality.
Abstract We benchmark classical, simulated-quantum, hybrid, and direct quantum-annealing workflows on a structured binary control problem formulated as a quadratic unconstrained binary optimization (QUBO) model. The benchmark is motivated by greenhouse heater scheduling, where the horizon (H) denotes the number of hourly binary control decisions, but the focus is on solver behavior for a physically decoded control-QUBO formulation. For the main one-day instance ((H=24)), all solver outputs are decoded back into heater schedules and evaluated using the same simulator-side objective and feasibility criterion. Classical simulated annealing and path-integral simulated quantum annealing produce feasible near-optimal solutions in all repetitions, with best objectives close to the exact optimum. In contrast, the tested D-Wave Leap Hybrid binary quadratic model workflow is less reliable and does not outperform the classical baselines under 15--60 s requested time limits. Direct D-Wave quantum processing unit execution on reduced instances remains feasible in all runs and recovers the exact optimum for (H=10) and (H=12), but the exact-hit rate decreases with increasing horizon. The results do not indicate quantum advantage, but provide a reproducible benchmark for evaluating annealing-based natural and quantum computing workflows on structured control QUBOs. MSC Classification: 90C27 , 90C59 , 81P68 , 93C55
We benchmark current annealing-based optimization workflows on a greenhouse-inspired quadratic unconstrained binary optimization problem for binary heater scheduling, where the horizon H denotes the number of hourly control decisions. For the main one-day instance (H=24), all solver outputs are decoded back into heater schedules and evaluated in the original greenhouse simulator using the same physical objective and feasibility criterion. Classical simulated annealing and path-integral simulated quantum annealing produce feasible near-optimal solutions in all repetitions, with best objectives close to the exact optimum. In contrast, the tested D-Wave Leap Hybrid BQM workflow is less reliable and does not outperform the classical baselines under 15--60~s requested time limits. Direct D-Wave QPU execution on reduced instances remains feasible in all runs and recovers the exact optimum for H=10 and H=12, but the exact-hit rate drops from 5/10 to 2/10 and then to 0/10 at H=14, with substantially higher variance than the classical baselines. The results do not indicate quantum advantage, but provide a reproducible, physically decoded benchmark that exposes the current strengths and limitations of classical, hybrid, and direct quantum annealing workflows on structured control QUBOs.
The calibration of suspension geometry involves highly nonlinear kinematic relationships and leads to challenging optimization landscapes that are difficult to explore efficiently with classical local methods. Quadratic Unconstrained Binary Optimization (QUBO) provides a unified discrete formulation that enables the use of a wide range of metaheuristic solvers, but its practical behavior in realistic engineering-inspired problems remains insufficiently benchmarked. This paper presents a computational benchmarking study of classical, parallel, and hybrid metaheuristic solvers applied to a QUBO-formulated double wishbone suspension geometry problem. A symbolic multi-body kinematic model is constructed and discretized into a large-scale QUBO instance capturing camber and caster tracking objectives across multiple roll conditions. Using a fixed low-resolution binary encoding, we systematically evaluate solver performance in terms of objective value, runtime, and time-to-solution trade-offs. The benchmark includes standard simulated annealing and tabu search, parallel simulated annealing, population-based annealing, bandit-controlled hybrid heuristics, and continuous-relaxation-based ADMM methods with and without annealing refinement. Extensive experiments conducted on a Euro-HPC pre-exascale system demonstrate that parallel and hybrid solvers can achieve substantial reductions in wall-clock time—often exceeding two orders of magnitude—while attaining objective values comparable to classical simulated annealing. The results reveal clear trade-offs between solution quality and computational efficiency, and highlight how solver structure influences performance on large QUBO instances derived from symbolic engineering models. Rather than focusing on final design optimality, this study provides a reproducible reference benchmark and practical insights into solver behavior for QUBO-based engineering optimization problems.
The increasing complexity of industrial scheduling and transport routing problems motivates the study of alternative optimization formulations and computational paradigms. In this work, we study how higher-order unconstrained binary optimization (HUBO) formulations of such problems map onto quantum optimization workflows in both noisy and fault-tolerant regimes. We consider three representative logistics and manufacturing use cases and formulate each as a HUBO problem. This captures process intricacies, such as highly correlated assembly-line scheduling rules, which are difficult to express faithfully with the standard quadratic (QUBO) form, while at the same time reducing the number of binary variables required in the quantum mapping, thus lowering qubit demand. We compare the HUBO formulations with corresponding QUBO encodings, highlighting a key trade-off: while HUBO reduces qubit requirements through compact binary encoding, it introduces higher-order interaction terms that increase circuit depth, limiting feasibility on current quantum hardware. The proposed formulations are validated using classical solvers across several problem instances and benchmark small routing problem instances using bias-field digitized counterdiabatic quantum optimization in classical simulation. We complement these results with a resource and scalability analysis, focusing on the capacitated vehicle routing problem as a representative large-scale industrial use case. Our analysis indicates that while HUBO formulations offer advantages in qubit scaling compared to QUBO encodings, their practical implementation is constrained by gate fidelity, coherence, and circuit depth, making hybrid quantum-classical workflows and early fault-tolerant quantum hardware the most plausible settings for their practical use.