Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2108.08805 · IEEE International Conference on Quantum Computing and Engineering (QCE)

Quantum Optimization Heuristics with an Application to Knapsack Problems

Wim van Dam, Karim Eldefrawy, Nicholas Genise, Natalie Parham

Published Oct 1, 2021• 31 citations
arXivHTMLPDF

Abstract

This paper introduces two techniques that make the standard Quantum Approximate Optimization Algorithm (QAOA) more suitable for constrained optimization problems. The first technique describes how to use the outcome of a prior greedy classical algorithm to define an initial quantum state and mixing operation to adjust the quantum optimization algorithm to explore the possible answers around this initial greedy solution. The second technique is used to nudge the quantum exploration to avoid the local minima around the greedy solutions. To analyze the benefits of these two techniques we run the quantum algorithm on known hard instances of the Knapsack Problem using unit depth quantum circuits. The results show that the adjusted quantum optimization heuristics typically perform better than various classical heuristics.

DOI
10.1109/qce52317.2021.00033

Related papers

Constrained Quantum Optimization at Utility Scale: Application to the Knapsack Problem

Naeimeh Mohseni, Julien-Pierre Houle, Ibrahim Shehzad +3 more

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.

quant-pharXiv:2603.00260•Mar 3, 2026•5 citations

Enhancing Knapsack-Based Financial Portfolio Optimization Using Quantum Approximate Optimization Algorithm

Chansreynich Huot, Kimleang Kea, Tae-Kyung Kim +1 more

Portfolio optimization is a primary component of the decision-making process in finance, aiming to tactfully allocate assets to achieve optimal returns while considering various constraints. Herein, we proposed a method that uses the knapsack-based portfolio optimization problem and incorporates the quantum computing capabilities of the quantum walk mixer with the quantum approximate optimization algorithm (QAOA) to address the challenges presented by the NP-hard problem. Additionally, we present the sequential procedure of our suggested approach and demonstrate empirical proof to illustrate the effectiveness of the proposed method in finding the optimal asset allocations across various constraints and asset choices. Moreover, we discuss the effectiveness of the QAOA components in relation to our proposed method. Consequently, our study successfully achieves the approximate ratio of the portfolio optimization technique using a circuit layer of$p\geqslant 3$, compared to the classical best-known solution of the knapsack problem. Our proposed methods potentially contribute to the growing field of quantum finance by offering insights into the potential benefits of employing quantum algorithms for complex optimization tasks in financial portfolio management.

arXiv:2402.07123•IEEE Access•Jan 1, 2024•27 citations

Quantum Tree Generator Improves Qaoa State-of-the-Art for the Knapsack Problem

P G Christiansen, Lennart Binkowski, Debora Ramacciotti +1 more

This paper introduces a novel approach to the Quantum Approximate Optimization Algorithm (QAOA), specifically tailored to the knapsack problem. We combine the recently proposed quantum tree generator as an efficient state preparation circuit for all feasible solutions to the knapsack problem with the framework of Grover-mixer QAOA to form the first representative of Amplitude Amplification-mixer QAOA (AAMQAOA). On hard benchmark sets with up to 20 knapsack items, we demonstrate our method's improved performance over the current state-of-the-art Copula-QAOA. However, for larger instance sizes, both approaches fail to deliver better outcomes than greedily packing items in descending value-to-weight ratio, at least for the considered circuit depths. For sufficiently high circuit depths, however, we can prove that AAM-QAOA will eventually be able to sample the optimal solution.

arXiv:2411.00518•IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•14 citations

Quantum Optimization Algorithms and Application

N. Manglani, Dhruv Solanki, Ankit Das

Optimization problems are fundamental across various scientific and industrial domains, from logistics and finance to machine learning and drug discovery. Classical optimization algorithms, such as gradient-based methods and heuristic approaches, often struggle with issues like slow convergence, getting trapped in local minima, and inefficiency in handling high-dimensional or combinatorial problems. Applying the concepts of quantum optimization with quantum mechanics algorithms presents viable substitutes with the potential for speedups and better solution quality. Among the significant quantum optimization techniques investigated in this paper are Grover's Search Algorithm, Variational Quantum Eigensolver (VQE), Quantum Annealing, and the Quantum Approximate Optimization Algorithm (QAOA). QAOA is designed for combinatorial optimization problems, blending quantum and classical techniques to approximate optimal solutions. VQE, widely used in quantum chemistry, employs a hybrid quantum-classical approach to determine ground-state energies efficiently. Grover's algorithm fastens up searching databases, indirectly aiding optimization tasks. Quantum annealing, implemented by systems like D-Wave, solves optimization problems by exploiting quantum tunneling to escape local minima. Despite their advantages, these quantum approaches face challenges, including hardware limitations, noise in quantum systems, and scalability concerns. However, these algorithms are expected to be essential in solving complicated optimization problems that are currently intractable by classical approaches when quantum technology develops.

Wiley eBooks•Oct 30, 2026•0 citations

A Quantum Global Optimization Algorithm: Application to the Knapsack Problem

Mohamed Yassine Cherif, Wided Lejouad Chaari, Olfa Belkahla Driss

Abstract Solving combinatorial optimization problems represents a challenge for researchers, especially hard NP-complete problems that are commonly handled through heuristic methods providing approximate solutions. The emergence of quantum computing, which enables performing parallel computation, raises hope for solving such problems within a reasonable time frame. This paper proposes a quantum global optimization algorithm for solving combinatorial optimization problems with improved performance and runtime approaching Grover’s optimal time of quantum search. The algorithm determines the global optimum of the objective function defining the addressed problem using an enhanced application of Grover’s search by simultaneously exploring all comparison cases of possible solutions without requiring iterative operations, unlike previous approaches, which affect performance and runtime. The paper also introduces a version of the proposed algorithm for solving the knapsack problem, along with its execution results and a comparison with other competing algorithms.

•Jan 12, 2026•0 citations

A Quantum Global Optimization Algorithm: Application to the Knapsack Problem

Mohamed Yassine Cherif, Wided Lejouad Chaari, Olfa Belkahla Driss

Abstract Solving combinatorial optimization problems represents a challenge for researchers, especially hard NP-complete problems that are commonly handled through heuristic methods providing approximate solutions. The emergence of quantum computing, which enables performing parallel computation, raises hope for solving such problems within a reasonable time frame. This paper proposes a quantum global optimization algorithm to solve combinatorial optimization problems intended to provide an improved performance. The proposed algorithm aims to amplify the probability of selecting the global optimum of the objective function defining the addressed problem using a specific variant of Grover’s search based on simultaneously exploring all comparison cases of possible solutions to recognize the global optimum. The paper also includes the study of precision and runtime of the presented concept and introduces a version of the proposed algorithm addressing the knapsack problem, along with its execution results and a comparison with other competing algorithms

•Mar 23, 2026•0 citations
This paper introduces two techniques that make the standard Quantum Approximate Optimization Algorithm (QAOA) more suitable for constrained optimization problems. The first technique describes how to use the outcome of a prior greedy classical algorithm to define an initial quantum state and mixing operation to adjust the quantum optimization algorithm to explore the possible answers around this initial greedy solution. The second technique is used to nudge the quantum exploration to avoid the local minima around the greedy solutions. To analyze the benefits of these two techniques we run the quantum algorithm on known hard instances of the Knapsack Problem using unit depth quantum circuits. The results show that the adjusted quantum optimization heuristics typically perform better than various classical heuristics.
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.
Portfolio optimization is a primary component of the decision-making process in finance, aiming to tactfully allocate assets to achieve optimal returns while considering various constraints. Herein, we proposed a method that uses the knapsack-based portfolio optimization problem and incorporates the quantum computing capabilities of the quantum walk mixer with the quantum approximate optimization algorithm (QAOA) to address the challenges presented by the NP-hard problem. Additionally, we present the sequential procedure of our suggested approach and demonstrate empirical proof to illustrate the effectiveness of the proposed method in finding the optimal asset allocations across various constraints and asset choices. Moreover, we discuss the effectiveness of the QAOA components in relation to our proposed method. Consequently, our study successfully achieves the approximate ratio of the portfolio optimization technique using a circuit layer ofp⩾3p\geqslant 3p⩾3, compared to the classical best-known solution of the knapsack problem. Our proposed methods potentially contribute to the growing field of quantum finance by offering insights into the potential benefits of employing quantum algorithms for complex optimization tasks in financial portfolio management.
This paper introduces a novel approach to the Quantum Approximate Optimization Algorithm (QAOA), specifically tailored to the knapsack problem. We combine the recently proposed quantum tree generator as an efficient state preparation circuit for all feasible solutions to the knapsack problem with the framework of Grover-mixer QAOA to form the first representative of Amplitude Amplification-mixer QAOA (AAMQAOA). On hard benchmark sets with up to 20 knapsack items, we demonstrate our method's improved performance over the current state-of-the-art Copula-QAOA. However, for larger instance sizes, both approaches fail to deliver better outcomes than greedily packing items in descending value-to-weight ratio, at least for the considered circuit depths. For sufficiently high circuit depths, however, we can prove that AAM-QAOA will eventually be able to sample the optimal solution.
Optimization problems are fundamental across various scientific and industrial domains, from logistics and finance to machine learning and drug discovery. Classical optimization algorithms, such as gradient-based methods and heuristic approaches, often struggle with issues like slow convergence, getting trapped in local minima, and inefficiency in handling high-dimensional or combinatorial problems. Applying the concepts of quantum optimization with quantum mechanics algorithms presents viable substitutes with the potential for speedups and better solution quality. Among the significant quantum optimization techniques investigated in this paper are Grover's Search Algorithm, Variational Quantum Eigensolver (VQE), Quantum Annealing, and the Quantum Approximate Optimization Algorithm (QAOA). QAOA is designed for combinatorial optimization problems, blending quantum and classical techniques to approximate optimal solutions. VQE, widely used in quantum chemistry, employs a hybrid quantum-classical approach to determine ground-state energies efficiently. Grover's algorithm fastens up searching databases, indirectly aiding optimization tasks. Quantum annealing, implemented by systems like D-Wave, solves optimization problems by exploiting quantum tunneling to escape local minima. Despite their advantages, these quantum approaches face challenges, including hardware limitations, noise in quantum systems, and scalability concerns. However, these algorithms are expected to be essential in solving complicated optimization problems that are currently intractable by classical approaches when quantum technology develops.
Abstract Solving combinatorial optimization problems represents a challenge for researchers, especially hard NP-complete problems that are commonly handled through heuristic methods providing approximate solutions. The emergence of quantum computing, which enables performing parallel computation, raises hope for solving such problems within a reasonable time frame. This paper proposes a quantum global optimization algorithm for solving combinatorial optimization problems with improved performance and runtime approaching Grover’s optimal time of quantum search. The algorithm determines the global optimum of the objective function defining the addressed problem using an enhanced application of Grover’s search by simultaneously exploring all comparison cases of possible solutions without requiring iterative operations, unlike previous approaches, which affect performance and runtime. The paper also introduces a version of the proposed algorithm for solving the knapsack problem, along with its execution results and a comparison with other competing algorithms.
Abstract Solving combinatorial optimization problems represents a challenge for researchers, especially hard NP-complete problems that are commonly handled through heuristic methods providing approximate solutions. The emergence of quantum computing, which enables performing parallel computation, raises hope for solving such problems within a reasonable time frame. This paper proposes a quantum global optimization algorithm to solve combinatorial optimization problems intended to provide an improved performance. The proposed algorithm aims to amplify the probability of selecting the global optimum of the objective function defining the addressed problem using a specific variant of Grover’s search based on simultaneously exploring all comparison cases of possible solutions to recognize the global optimum. The paper also includes the study of precision and runtime of the presented concept and introduces a version of the proposed algorithm addressing the knapsack problem, along with its execution results and a comparison with other competing algorithms