Real-world optimization problems must undergo a series of transformations before becoming solvable on current quantum hardware. Even for a fixed problem, the number of possible transformation paths-from industry-relevant formulations through binary constrained linear programs (BILPs), to quadratic unconstrained binary optimization (QUBO), and finally to a hardware-executable representation-is remarkably large. Each step introduces free parameters, such as Lagrange multipliers, encoding strategies, slack variables, rounding schemes or algorithmic choices-making brute-force exploration of all paths intractable. In this work, we benchmark a representative subset of these transformation paths using a realworld industrial production planning problem with industry data: the optimization of work allocation in a press shop producing vehicle parts. We focus on QUBO reformulations and algorithmic parameters for both quantum annealing (QA) and the Linear Ramp Quantum Approximate Optimization Algorithm (LR-QAOA). Our goal is to identify a reduced set of effective configurations applicable to similar industrial settings. Our results show that QA on D-Wave hardware consistently produces near-optimal solutions, whereas LR-QAOA on IBM quantum devices struggles to reach comparable performance. Hence, the choice of hardware and solver strategy significantly impacts performance. The problem formulation and especially the penalization strategy determine the solution quality. Most importantly, mathematically-defined penalization strategies are equally successful as hand-picked penalty factors, paving the way for automated QUBO formulation. Moreover, we observe a strong correlation between simulated and quantum annealing performance metrics, offering a scalable proxy for predicting QA behavior on larger problem instances.
Real-world optimization problems must undergo a series of transformations before becoming solvable on current quantum hardware. Even for a fixed problem, the number of possible transformation paths-from industry-relevant formulations through binary constrained linear programs (BILPs), to quadratic unconstrained binary optimization (QUBO), and finally to a hardware-executable representation-is remarkably large. Each step introduces free parameters, such as Lagrange multipliers, encoding strategies, slack variables, rounding schemes or algorithmic choices-making brute-force exploration of all paths intractable. In this work, we benchmark a representative subset of these transformation paths using a realworld industrial production planning problem with industry data: the optimization of work allocation in a press shop producing vehicle parts. We focus on QUBO reformulations and algorithmic parameters for both quantum annealing (QA) and the Linear Ramp Quantum Approximate Optimization Algorithm (LR-QAOA). Our goal is to identify a reduced set of effective configurations applicable to similar industrial settings. Our results show that QA on D-Wave hardware consistently produces near-optimal solutions, whereas LR-QAOA on IBM quantum devices struggles to reach comparable performance. Hence, the choice of hardware and solver strategy significantly impacts performance. The problem formulation and especially the penalization strategy determine the solution quality. Most importantly, mathematically-defined penalization strategies are equally successful as hand-picked penalty factors, paving the way for automated QUBO formulation. Moreover, we observe a strong correlation between simulated and quantum annealing performance metrics, offering a scalable proxy for predicting QA behavior on larger problem instances.
Several optimization solvers inspired by quantum annealing have been recently developed, either running on actual quantum hardware or simulating it on traditional digital computers. Industry and academics look at their potential in solving hard combinatorial optimization problems. Formally, they provide heuristic solutions for Ising models, which are equivalent to quadratic unconstrained binary optimization (QUBO). Constraints on solutions feasibility need to be properly encoded. We experiment on different ways of performing such an encoding. As benchmark we consider the cardinality constrained quadratic knapsack problem (CQKP), a minimal extension of QUBO with one inequality and one equality constraint. We consider different strategies of constraints penalization and variables encoding. We compare three QUBO solvers: quantum annealing on quantum hardware (D-Wave Advantage), probabilistic algorithms on digital hardware and mathematical programming solvers. We analyze their QUBO resolution quality and time, and the persistence values extracted in the quantum annealing sampling process. Our results show that a linear penalization of CQKP inequality improves current best practice. Furthermore, using such a linear penalization, persistence values produced by quantum hardware in a generic way allow to match a specific CQKP metric from literature. They are therefore suitable for general purpose variable fixing in core algorithms for combinatorial optimization.
Quantum Optimization (QO) is emerging as a promising approach to tackle hard combinatorial optimization problems by leveraging the unique computational properties of quantum hardware. In recent years, QO has gained traction in Machine Learning (ML), where problems such as clustering and vector quantization can be naturally expressed as Quadratic Unconstrained Binary Optimization (QUBO) problems. These ML applications often involve complex, high-dimensional data, which directly influences both the structure and scale of the resulting QUBO formulations. However, current quantum devices fall under the category of Noisy Intermediate-Scale Quantum (NISQ) hardware, which imposes significant limitations on qubit counts and small error rates. This dissertation investigates the impact of data complexity and data scale—as encountered in ML settings—on the effectiveness and feasibility of QO on NISQ devices. We propose novel, hardware-aware methods to overcome these challenges. The first part of this thesis focuses on the effect of data complexity for QO. We analyze how problem structure—particularly when QUBO formulations are derived from ML tasks—affects quantum solvability. We identify the spectral gap as a key factor in the success of adiabatic quantum algorithms and provide a theoretical and empirical analysis linking data-induced complexity to optimization performance.To address noise sensitivity and limited precision, we introduce a preprocessing framework based on a principled Branch-and-Bound algorithm that reduces dynamic range while preserving global optima. This improves robustness on both quantum annealers and classical solvers. In the second part, the thesis addresses challenges introduced by data scale. First, we propose a recursive Divide-and-Conquer strategy that breaks down large QUBO problems into tractable subproblems, demonstrated through an application to Bundle Adjustment in 3D scene reconstruction. Second, we introduce a variable and constraint generation method inspired by column generation for Integer Linear Programming, enabling dynamic QUBO size growth. This technique is successfully applied to Multi-Agent Pathfinding, where it scales well on NISQ devices while maintaining compatibility with classical solvers. Finally, we explore QUBO reformulations that reduce problem size through compact encodings and cyclic expansion, enabling the use of quantum hardware for tasks such as FPGA placement in chip design. Across all contributions, the developed algorithms are evaluated both theoretically and empirically, with experiments conducted on real quantum and quantum-inspired hardware. These methods significantly improve solution quality, scalability, and hardware compatibility, paving the way for more effective use of QO in practical settings. While tailored for NISQ era constraints, the results remain relevant for fault-tolerant quantum computing, offering insights into the long-term viability of QO across hardware generations.
Flow Shop Scheduling Problems (FSP) represent a challenging class of combinatorial optimization tasks with significant relevance across diverse domains ranging from manufacturing and logistics to service operations. Recent advances in quantum annealing and quantum-inspired approaches have opened avenues for tackling such problems via Quadratic Unconstrained Binary Optimization models. However, their performance depends strongly on how the problem is encoded as a QUBO. In this study, we perform a comparative evaluation of manually formulated QUBOs versus those automatically produced by the AutoQUBO framework. We test both formulations on D-Wave's hybrid and qbsolv solvers and the InfinityQ solver, exploring the effect of QUBO-solver-specific behaviors and sensitivity, and fine-tuning strategies on the quality of the solution. While carefully crafted manual QUBOs typically yield stronger solution fidelity, they demand greater domain expertise and computational overhead. In contrast, automated approaches greatly expedite modeling at the cost of certain performance trade-offs. We further observe that solver fine-tuning and hardware selection substantially shape outcomes, with certain solvers favoring domain-tailored encodings. These insights demonstrate the necessity of solver-aware QUBO design, offering practical guidance on QUBO construction and solver choice to solve the FSP using quantum and quantum-inspired hardware.
Quantum computing has emerged as a new tool for solving combinatorial optimization problems. Quantum optimization approaches usually operate on the subclass of Quadratic Unconstrained Binary Optimization (QUBO) problems. Many optimization problems can be reformulated in this form, though there are often multiple ways to do so. The choice of formulation can considerably affect the performance of QUBO solvers in practice. In this work, we study QUBO formulations of the Knapsack problem, a canonical example of a problem with inequality constraints. In the standard formulation these constraints are converted into penalty terms, which requires additional slack variables. Here, we investigate three more resource-efficient approaches for formulating the Knapsack as a QUBO. The first two modify the standard formulation, either by deriving a smaller penalty constant or by reducing the number of slack variables. The third approach is a wholly different method, which avoids the use of slack variables entirely. All three approaches increase the probability of finding the optimal solution, both in simulations of the linear ramp Quantum Approximate Optimization Algorithm (LR-QAOA) and on a D-Wave quantum annealer. The slackless method performs best, increasing success probabilities by several orders of magnitude even for relatively small problem sizes.
Abstract Industry 5.0 shifts the focus of manufacturing automation toward human well-being, not just efficiency or output. This means task-allocation systems now have to juggle production targets, ergonomic safety, and what the workforce can realistically handle. Here, we introduce what we call the Ergonomics-Aware Human–Robot Task Allocation (EA-HRTA) problem. Picture it as a complex assignment challenge: for every task, we have to consider execution cost, whether the person or robot has the right skills, the workload each can take on, and the total ergonomic strain humans can safely handle. We turn this challenge into a Quadratic Unconstrained Binary Optimization (QUBO) model, so it runs on both quantum-annealing machines and gate-model quantum computers. We lay out three key contributions: first, we develop a penalty-based QUBO model and show exactly how to set penalty weights so it actually works. Second, we roll out a complete system where the very same QUBO gets sent both to a D-Wave-style simulated-annealing sampler and to our own lightweight, dependency-free QAOA statevector simulator. Finally, we’ve built and open-sourced a benchmarking suite that lets you see how quantum solutions perform next to a quick, greedy heuristic and a full-scale CBC integer programming baseline.. Across 60 runs spanning problem sizes from 9 to 240 binary variables, quantum annealing maintains a 100% constraint-feasibility rate at every scale tested, matching classical baselines closely on small instances (within 2% of the exact optimum at N = 9) but exhibiting a solution-quality gap that widens to roughly 140% at N = 240 under fixed penalty weights and a fixed annealing schedule. QAOA achieves competitive cost values only at the smallest instance tested (N = 9) and loses feasibility entirely by N = 16, consistent with known near-term gate-model scalability limits. We report a warm-start ablation seeding the annealer with the greedy solution, which does not yield a consistent improvement, and use this negative result to motivate an adaptive-penalty and problem-decomposition research direction. Rather than claiming a present-day quantum advantage, this paper contributes a reusable ergonomics-aware QUBO formulation, a transparent and reproducible benchmark methodology for the human-centric manufacturing community, and an honest empirical map of where current quantum optimization methods stand relative to classical practice at realistic shop-floor problem sizes.
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.