Combinatorial optimization problems play a central role in computer science and real-world decision-making, as they aim to find the optimal solution from a large set of possibilities. Among these, the Knapsack Problem is a fundamental example with many practical applications. The Quantum Approximate Optimization Algorithm (QAOA) is a quantum-classical hybrid approach designed to address such problems. However, existing simulation approaches for QAOA applied to the Knapsack Problem do not scale well because they fail to exploit the problem's structural properties. To overcome these limitations, this study exploits the entangling characteristics of circuits in the Knapsack Problem and develops an optimized solver tailored to this setting. The key technical contributions include an entanglement-free circuit simulation method that reduces complexity from exponential to linear for non-entangling circuits, enabling 24,000x speedups for QAOA ansatz circuit simulations, and a two-phase parameter selection strategy that enhances the efficiency of finding optimal Knapsack solutions. Our solver extends the scalability of QAOA simulations from the previous limit of approximately 10 qubits to 100 qubits within a system memory of 256 GB. It achieves performance gains of over 100,000x for solving Knapsack Problems while maintaining high solution quality.
Combinatorial optimization problems play a central role in computer science and real-world decision-making, as they aim to find the optimal solution from a large set of possibilities. Among these, the Knapsack Problem is a fundamental example with many practical applications. The Quantum Approximate Optimization Algorithm (QAOA) is a quantum-classical hybrid approach designed to address such problems. However, existing simulation approaches for QAOA applied to the Knapsack Problem do not scale well because they fail to exploit the problem's structural properties. To overcome these limitations, this study exploits the entangling characteristics of circuits in the Knapsack Problem and develops an optimized solver tailored to this setting. The key technical contributions include an entanglement-free circuit simulation method that reduces complexity from exponential to linear for non-entangling circuits, enabling 24,000x speedups for QAOA ansatz circuit simulations, and a two-phase parameter selection strategy that enhances the efficiency of finding optimal Knapsack solutions. Our solver extends the scalability of QAOA simulations from the previous limit of approximately 10 qubits to 100 qubits within a system memory of 256 GB. It achieves performance gains of over 100,000x for solving Knapsack Problems while maintaining high solution quality.
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.
The solution of large-scale combinatorial optimization problems, which are exorbitantly complex and resource-consuming, is one of the most significant challenges that computing systems face. Traditional algorithms often provide suboptimal results when confronted with bigger issues. This research aims to bring attention to these problems by introducing the Extending Quantum Approximate Optimization Algorithm (EQAOA) framework, which improves scalability, parameter optimization, and error resilience. Fundamental to the EQAOA methodology is repeatedly optimizing solution states via adaptive-depth, parameter-tuned quantum circuits. EQAOA also employs the method of converting combinatorial problems into cost Hamiltonians. Similar problems are shown in the Max-Cut and Graph Coloring programs. The experiments were conducted on several benchmark circumstances using real NISQ hardware and quantum simulators. The enhanced EQAOA outperforms baseline versions in terms of convergence time and solution quality. The efficient integration of dynamic circuit depth with hybrid classical-quantum parameter approaches applied to increasingly complicated problem scenarios and yielded good results. According to the study's findings, applying the proposed QAOA extension to practical combinatorial contexts yields a quantum advantage. The future of this field is bright, with researchers aiming to improve its interaction with traditional optimizers and extend its usage to other practical optimization areas.
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.
Constrained combinatorial optimization problems are challenging for quantum computing, particularly at utility-relevant scales and on near-term hardware. At the same time, these problems are of practical significance in industry; for example, the Unit Commitment (UC) problem in energy systems involves complex operational constraints. To address this challenge, we apply copula-QAOA (cop-QAOA), a hardware-efficient approach for constrained optimization to a single-period UC that can be reduced to a one-dimensional knapsack. Cop-QAOA biases the quantum state toward feasible solutions using constant-depth mixers and appropriately biased initial states. We implement our benchmark on problem instances that are confirmed to be hard for classical solvers such as Gurobi. Our results show that cop-QAOA often finds solutions better than a lazy greedy baseline and very close to, and in some instances surpasses, those obtained by Gurobi, with only a few QAOA rounds. This work presents the largest successful demonstration of the knapsack problem on IBM Quantum hardware using up to 150 qubits, and more generally, the largest demonstration of constrained combinatorial optimization where constraints are enforced via shallow mixers.
The Multi-Knapsack Problem (MKP) is a fundamental challenge in operations research and combinatorial optimization. Quantum computing introduces new possibilities for solving MKP using Quadratic Unconstrained Binary Optimization (QUBO) models. However, a key challenge in QUBO formulations is the selection of penalty parameters, which directly influence solution feasibility and algorithm performance. In this work, we develop QUBO formulations for two MKP variants—the Multidimensional Knapsack Problem (MDKP) and the Multiple Knapsack Problem (MUKP)—and provide an algebraic characterization of their penalty parameters. We systematically evaluate their impact through quantum simulation experiments and compare the performance of the two leading quantum optimization approaches: Quantum Approximate Optimization Algorithm (QAOA) and quantum annealing, alongside a state-of-the-art classical solver. Our results indicate that while classical solvers remain superior, careful tuning of penalty parameters has a strong impact on quantum optimization outcomes. QAOA is highly sensitive to parameter choices, whereas quantum annealing produces more stable results on small to mid-sized instances. Further, our results reveal that MDKP instances can maintain feasibility at penalty values below theoretical bounds, while MUKP instances show greater sensitivity to penalty reductions. Finally, we outline directions for future research in solving MKP, including adaptive penalty parameter tuning, hybrid quantum-classical approaches, and practical optimization strategies for QAOA, as well as real-hardware evaluations.
Hybrid Quantum–Classical Optimization combines the advantages of quantum computing and classical optimization to address complex combinatorial optimization problems. The Quantum Approximate Optimization Algorithm (QAOA), as an outstanding Variational Quantum Algorithm (VQA), shows great potential in solving combinatorial optimization problems. Classical optimization methods play a crucial role in tuning the parameters of quantum circuits, affecting the algorithm’s convergence speed and solution quality. This paper designs and simulates QAOA circuits based on the Qiskit framework, focusing on comparing the performance of three classical optimizers— Adaptive Moment Estimation (Adam), Constrained Optimization BY Linear Approximations (COBYLA), and Simultaneous Perturbation Stochastic Approximation (SPSA)—in parameter optimization. Adam and SPSA perform more stably in deeper circuits, making them suitable for high-dimensional parameter spaces, whereas COBYLA tends to get trapped in local optima and exhibits greater fluctuations under limited iterations. The results further highlight the importance of classical optimizer selection and hyperparameter tuning in enhancing the performance of hybrid quantum–classical optimization algorithms.