Solving combinatorial optimization problems is a promising application area for quantum algorithms in real-world scenarios. In this work, we extend the “Quantum Tree Generator” (QTG), previously proposed for the 0-1 Knapsack Problem, to the 0-1 Quadratic Knapsack Problem (QKP) and the Multidimensional Knapsack Problem (MDKP). The QTG constructs a superposition of all feasible solutions for a given instance and can therefore be utilized as a promising state preparation routine within amplitude amplification to produce high-quality solutions. Previously, QTG-based search was tested on the 0-1 Knapsack Problem, where it demonstrated the potential for practical quantum advantage, once quantum computers with a few hundred logical and fully connected qubits are available. Here, we evaluate the algorithm's performance on QKP and MDKP against the classical solver Gurobi. To facilitate large-scale evaluations, we employ an advanced benchmarking technique that enables runtime predictions for instances with up to 2000 variables for QKP and up to 1500 variables and 100 constraints for MDKP. Our results indicate that QTG-based search can produce high-quality solutions with competitive runtimes for QKP. However, its performance declines for MDKP, highlighting the challenges quantum algorithms face when tackling highly constrained optimization problems.
Solving combinatorial optimization problems is a promising application area for quantum algorithms in real-world scenarios. In this work, we extend the “Quantum Tree Generator” (QTG), previously proposed for the 0-1 Knapsack Problem, to the 0-1 Quadratic Knapsack Problem (QKP) and the Multidimensional Knapsack Problem (MDKP). The QTG constructs a superposition of all feasible solutions for a given instance and can therefore be utilized as a promising state preparation routine within amplitude amplification to produce high-quality solutions. Previously, QTG-based search was tested on the 0-1 Knapsack Problem, where it demonstrated the potential for practical quantum advantage, once quantum computers with a few hundred logical and fully connected qubits are available. Here, we evaluate the algorithm's performance on QKP and MDKP against the classical solver Gurobi. To facilitate large-scale evaluations, we employ an advanced benchmarking technique that enables runtime predictions for instances with up to 2000 variables for QKP and up to 1500 variables and 100 constraints for MDKP. Our results indicate that QTG-based search can produce high-quality solutions with competitive runtimes for QKP. However, its performance declines for MDKP, highlighting the challenges quantum algorithms face when tackling highly constrained optimization problems.
We present two novel contributions for achieving and assessing quantum advantage in solving difficult optimisation problems, both in theory and foreseeable practice. (1) We introduce the “Quantum Tree Generator” to generate in superposition all feasible solutions of a given 0-1 knapsack instance; combined with amplitude amplification, this identifies optimal solutions. Assuming fully connected logical qubits and comparable quantum clock speed, QTG offers perspectives for runtimes competitive to classical state-of-the-art knapsack solvers for instances with only 100 variables. (2) By introducing a new technique that exploits logging data from a classical solver, we can predict the runtime of our method way beyond the range of existing quantum platforms and simulators, for benchmark instances with up to 600 variables. Under the given assumptions, we demonstrate the QTG’s potential practical quantum advantage for such instances, indicating the promise of an effective approach for hard combinatorial optimisation problems.
Abstract We present two novel contributions for achieving and assessing quantum advantage in solving difficult optimisation problems, both in theory and foreseeable practice. (1) We introduce the “Quantum Tree Generator” to generate in superposition all feasible solutions of a given 0-1 knapsack instance; combined with amplitude amplification, this identifies optimal solutions. Assuming fully connected logical qubits and comparable quantum clock speed, QTG offers perspectives for runtimes competitive to classical state-of-the-art knapsack solvers for instances with only 100 variables. (2) By introducing a new technique that exploits logging data from a classical solver, we can predict the runtime of our method way beyond the range of existing quantum platforms and simulators, for benchmark instances with up to 600 variables. Under the given assumptions, we demonstrate the QTG’s potential practical quantum advantage for such instances, indicating the promise of an effective approach for hard combinatorial optimisation problems.
The Multi-Dimensional Knapsack Problem (MDKP) is a strongly NP-Hard combinatorial optimization problem that extends the Knapsack Problem (KP) to multiple constraints. While effective heuristic classical MDKP algorithms have been studied, there remains no optimal exact classical algorithm and only few contributions using quantum algorithms exist. In this study, we leverage Grover's search and pre-processing techniques to propose an iterative quantum search algorithm and circuit design that integrates classical adjustments to the oracle, progressively refining solutions until optimal. Evaluations show that our method reduces depth, width, iterations, and runtime.
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.
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.
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.