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.
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.
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.
To increase efficiency in automotive manufacturing, newly produced vehicles can move autonomously from the production line to the distribution area. This requires an optimal placement of sensors to ensure full coverage while minimizing the number of sensors used. The underlying optimization problem poses a computational challenge due to its large-scale nature. Currently, classical solvers rely on heuristics, often yielding nonoptimal solutions for large instances, resulting in suboptimal sensor distributions and increased operational costs. We explore quantum computing methods that may outperform classical heuristics in the future. We implemented quantum annealing with D-Wave, transforming the problem into a quadratic unconstrained binary optimization formulation with one-hot and binary encoding. Hyperparameters like the penalty terms and the annealing time are optimized and the results are compared with default parameter settings. Our results demonstrate that quantum annealing is capable of solving instances derived from real-world scenarios. Through the use of decomposition techniques, we are able to scale the problem size further, bringing it closer to practical, industrial applicability. Through this work, we provide key insights into the importance of quantum annealing parametrization, demonstrating how quantum computing could contribute to cost-efficient, large-scale optimization problems once the hardware matures.