The semiconductor supply chain gives rise to many complex, large and heavily constrained combinatorial optimization problems. We derive simpler problems from these complex formulations and analyze quantum algorithms for their solution. We study two main regimes: variational algorithms derived from the Quantum Approximate Optimization Algorithm (QAOA) and quantum search algorithms based on Grover’s search algorithm and Amplitude Amplification. In the first case, the main challenge lies in integrating problem constraints into the QAOA framework, which was originally devised for unconstrained problems such as MaxCut. The canonical method of adding penalty terms to the objective leads to an undesirable inflation of the energy spectrum. Instead, we examine alternative problem encodings as well as constraint-preserving mixing operators, which are designed to limit the quantum algorithm to the subspace of feasible states. We make explicit suggestions for a wide selection of problems. In the second case, we operate under the premise that any quantum search protocol for combinatorial optimization must use tailored initial states– otherwise the square root speedup of quantum search is not enough to offset the exponential size of the search space in a combinatorial optimization problem. Consequently, we examine state preparation routines for a wide range or problems. The main devices lie in preparing superpositions of only feasible states and superpositions which are centered around a reference solution. We present a benchmarking technique, in an exact and an approximate version, which allows us to generate performance metrics for our algorithms based on quantum search. We use the benchmarking tools to carry out numerical studies for a selection of problems. We conclude that our variational methods tailored to constrained problems while technically sound– lead to deep quantum circuits which are not suitable for the NISQ machines which QAOA was originally developed for. Our conclusion for optimization algorithms based on quantum search is more optimisitic. Their compatability with classical optimization principles, such as neighborhood search, gives rise to promising further research directions. Advanced benchmarking techniques allow us to test these algorithms independently of quantum hardware developments.
The semiconductor supply chain gives rise to many complex, large and heavily constrained combinatorial optimization problems. We derive simpler problems from these complex formulations and analyze quantum algorithms for their solution. We study two main regimes: variational algorithms derived from the Quantum Approximate Optimization Algorithm (QAOA) and quantum search algorithms based on Grover’s search algorithm and Amplitude Amplification. In the first case, the main challenge lies in integrating problem constraints into the QAOA framework, which was originally devised for unconstrained problems such as MaxCut. The canonical method of adding penalty terms to the objective leads to an undesirable inflation of the energy spectrum. Instead, we examine alternative problem encodings as well as constraint-preserving mixing operators, which are designed to limit the quantum algorithm to the subspace of feasible states. We make explicit suggestions for a wide selection of problems. In the second case, we operate under the premise that any quantum search protocol for combinatorial optimization must use tailored initial states– otherwise the square root speedup of quantum search is not enough to offset the exponential size of the search space in a combinatorial optimization problem. Consequently, we examine state preparation routines for a wide range or problems. The main devices lie in preparing superpositions of only feasible states and superpositions which are centered around a reference solution. We present a benchmarking technique, in an exact and an approximate version, which allows us to generate performance metrics for our algorithms based on quantum search. We use the benchmarking tools to carry out numerical studies for a selection of problems. We conclude that our variational methods tailored to constrained problems while technically sound– lead to deep quantum circuits which are not suitable for the NISQ machines which QAOA was originally developed for. Our conclusion for optimization algorithms based on quantum search is more optimisitic. Their compatability with classical optimization principles, such as neighborhood search, gives rise to promising further research directions. Advanced benchmarking techniques allow us to test these algorithms independently of quantum hardware developments.
Combinatorial Optimization problems play an important role in various domains such as logis- tics, life science or the financial sector. As their complexity in general grows exponentially with their problem size, finding the optimal solution classically becomes infeasible very fast. This raises the central question of whether quantum computers are in principle suitable for solving combinatorial optimization problems better and faster than classical computers. In order to find answers to that question, one needs to study quantum algorithms designed for those problems under ideal conditions (i.e., simulations, which are however limited due to exponential scaling) to investigate their potential, but one also needs real quantum hardware to test its viability and evaluate whether practical advantages are reasonable. In this regard, we consider variational quantum algorithms, especially the Quantum Approximate Optimization Algorithm (QAOA) consisting of a problem and a mixer Hamiltonian with freely selectable parameters, originally proposed as variational hybrid ansatz with classical optimization. This algorithm structure of- fers flexible and relatively shallow circuits, which makes it suitable for current NISQ hardware. However, optimizing the variational circuit parameters can be an NP-hard problem at worst. In this thesis, we study different versions of QAOA, especially with a focus on limitations, perfor- mance and potential advantages opposite classical methods. The first part of the thesis concerns the investigation of various aspects regarding the imple- mentation of the variational QAOA protocol such as: the incorporation of a problem constraint either by adding a suitable penalty term of by choosing a suitable mixer (that restricts the search space), the scaling of the problem Hamiltonian in comparison to the mixer Hamiltonian, the choice of the initial values for the classical optimization of the circuit parameters, and finally the choice of the function to be minimized (i.e., CVaR vs. expectation value). We apply this proto- col to both the portfolio optimization and the feature selection and evaluate the performance. In order to improve QAOA, we consider the warm-start QAOA for different problem instances and analyze its improved performance with regard to involved quantum effects. For this purpose, we propose a classical pre-processing method and demonstrate that the warm-start results can be reproduced or even exceeded by this method. The second part addresses the issue that the standard variational form requires a high number of circuit parameters that have to be optimized at a sufficiently large depth, which is a major limitationforachievingpotentialscalingadvantagescomparedtoclassicalmethods. Toovercome this limitation, we investigate and further develop fixed schedules for QAOA, which only rely on two free parameters. We start with introducing the continuous adiabatic theorem as it motivates the form of QAOA and show its limitations, which we address by applying a discrete version of the theorem. With our findings, a new version of QAOA based on linear-ramps (LR-QAOA) is introduced and further developed. In order to derive suitable parameter values for this schedule, we propose a method based on extrapolation from smaller towards larger problem sizes. With our results obtained on a noiseless emulator, we evaluate the quantum runtime scaling and discuss whether a scaling advantage can be achieved compared to classical methods.
Optimization problems are pervasive across various domains, including logistics, finance, machine learning, and operations research. Quantum computing has emerged as a promising frontier to address these challenges, offering potential speedups for certain classes of optimization tasks. This paper explores the development and application of quantum algorithms, such as the Quantum Approximate Optimization Algorithm (QAOA), Variational Quantum Eigensolver (VQE), and Grover’s search algorithm, tailored for optimization. Recent advancements in hardware, hybrid quantum-classical approaches, and variational techniques have enabled practical implementations on Noisy Intermediate-Scale Quantum (NISQ) devices. Challenges such as noise, scalability, and performance limitations are also discussed. Through theoretical analysis and case studies, this work demonstrates how quantum computing can complement classical methods, paving the way for breakthroughs in solving complex optimization problems.
Combinatorial optimization problems play a vital role in computer science and engineering, with applications in logistics, network design, finance, and resource allocation. However, many of these problems are NP-hard, making them computationally expensive to solve using classical optimization techniques, especially for large-scale instances. In recent years, quantum computing has emerged as a promising paradigm capable of addressing these limitations by leveraging quantum mechanical principles such as superposition and entanglement. This study investigates the application of quantum computing for solving combinatorial optimization problems, with a focus on algorithm design, complexity analysis, and real-world applicability. The research primarily employs the Quantum Approximate Optimization Algorithm (QAOA) and Grover's search algorithm to solve representative problems such as Max-Cut and the Knapsack problem. The performance of these algorithms is evaluated using key metrics including accuracy, execution time, and approximation ratio, and is compared with classical optimization techniques. The results demonstrate that QAOA is capable of generating near-optimal solutions, achieving accuracy levels of up to 93% for small problem instances. However, the study also highlights the challenges associated with current quantum systems, including noise, limited qubit availability, and increased execution time. Comparative analysis reveals that while classical methods remain more efficient for small-scale problems, quantum algorithms show significant potential for scalability and handling complex optimization tasks. The findings suggest that hybrid quantum-classical approaches offer a practical solution in the current Noisy Intermediate-Scale Quantum (NISQ) era. The study concludes that although quantum computing is still evolving, it holds strong potential for transforming combinatorial optimization in the future.
Combinatorial optimisation constitutes a central class of computational problems with broad relevance across science and industry, combining foundational theoretical interest with significant real-world impact. Many problems of practical importance admit concise mathematical formulations, yet resist efficient classical solution methods due to their NP-hard structure. Quantum computing offers several algorithmic paradigms that promise structural speedups for such problems. Most quantum and hybrid frameworks fall into one of the following three categories: algorithms based on continuous adiabatic evolution, such as quantum annealing; circuit-based variational quantum algorithms; circuit-based approaches based on Grover's algorithm. These three algorithmic families are conceptualised for different kinds and generations of quantum architectures, often studied in isolation from each other and from preexisting sophisticated classical methods. This thesis develops a unified, predominantly circuit-based treatment of quantum algorithms for combinatorial optimisation, with a particular focus on principled design transfers between near-term parametric algorithms and far-term fault-tolerant approaches. Starting from the Boolean circuit model, reversible and quantum circuit formulations are derived that allow for precise size and depth analysis of classical control logic, reversible embeddings, and quantum realisations of Boolean and pseudo-Boolean functions. These constructions form a common backbone for optimisation algorithms based on adiabatic evolution, variational principles, and amplitude amplification. Adiabatic quantum computation is analysed within this circuit framework, leading to explicit convergence conditions and resource bounds for discretised adiabatic evolutions driven by pseudo-Boolean cost functions of bounded degree. Variational quantum algorithms are then revisited with an emphasis on feasibility-preserving operations and mixing families. In this context, a novel class of exhaustive variational quantum algorithms is introduced, characterised by finite parameterisations that provably reach optimal solutions. These constructions naturally induce state-preparation routines that guarantee to generate superpositions of all feasible solutions. Finally, Grover’s algorithm and its generalisations are studied as optimisation methods, highlighting their structural dependence on feasible-state preparation and their conceptual proximity to variational and adiabatic approaches. By establishing explicit design transfer principles between these paradigms, this thesis provides a unified perspective on quantum optimisation algorithms, accompanied by concrete circuit constructions and quantitative resource analyses.
Quantum computing is a rapidly growing field, promising computational advancements with significant impact on real-world and industrial applications. These areas include cryptography, financial systems, material and drug discovery. They also cover combinatorial optimization, which is the focus of this thesis. For combinatorial optimization problems, researchers have spent several decades extending the capabilities of quantum algorithms for both near-term and far-term quantum hardware. Because current devices comprise too few qubits (quantum bits) and noisy gates (qubit operations prone to errors), potential quantum advantage must be assessed using theoretical and numerical frameworks. Despite the existence of many quantum algorithms, such as Grover’s algorithm and Quantum Branch-and-Bound (QB&B), which provide asymptotic speedups, we lack evidence of a practical quantum speedup on realistic problem instances. Recent benchmarking efforts show that several far-term algorithms with asymptotic advantage still cannot achieve practical quantum advantage under realistic conditions. This thesis comprises three advancements. First, it develops a new type of state preparation tailored to constraint optimization problems. This enables a Grover-based heuristic we call Constraint-oriented biased quantum search (CBQS). Second, it introduces benchmarking methods that compare the quantum search with state-of-the-art classical algorithms on large instances. These methods indicate that the proposed quantum algorithm can achieve a practical quantum advantage. For some cases, logical gate times of just 10−6s with about 19,000 logical qubits are enough to match classical runtime. Third, it presents a quantum circuit backend (software that processes quantum circuits) designed for speed at the cost of suboptimal circuit design. This backend outperforms a wide range of existing software packages in both speed and memory consumption, demonstrated by Quantum Fourier Transformation (QFT) circuits of up to 2000 qubits. Overall, this work points the way toward full-stack quantum advantage while underscoring the need for further research on topics such as quantum error correction.
In this work, we review quantum approaches to combinatorial optimization, with the aim of bridging theoretical developments and industrial relevance. We first survey the main families of quantum algorithms, including Quantum Annealing, the Quantum Approximate Optimization Algorithm (QAOA), Quantum Reinforcement Learning (QRL), and Quantum Generative Modeling (QGM). We then examine the problem classes where quantum technologies currently show evidence of quantum advantage, drawing on established benchmarking initiatives such as QOBLIB, QUARK, QASMBench, and QED-C. These problem classes are subsequently mapped to representative industrial domains, including logistics, finance, and telecommunications. Our analysis indicates that quantum annealing currently exhibits the highest level of operational maturity, while QAOA shows promising potential on NISQ-era hardware. In contrast, QRL and QGM emerge as longer-term research directions with significant potential for future industrial impact.