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

Computer Engineering and Applications Journal

Quantum mechanical algorithm to solve knapsack problem

Hao Xu, Pla Information

Published Jan 1, 2009• 0 citations
OpenAlex

Abstract

Knapsack problem is one of the NP complete problems.Its computational complexity is O( 2n).This paper presents the quantum mechanical algorithm based on the fixed phase quantum search to solve the knapsack problem,and the algorithm also gets probability of success at least 98% in O((N/M)~(1/2)) quantum mechanical steps( Where M is the number of matches).This quantum algorithm has higher probability of success than the algorithm based on Grover algorithm with multiple matches in the search space.

Related papers

SOLVING THE 0/1-KNAPSACK PROBLEM ON QUANTUM COMPUTER

Jin Hu

The scientists have given various kinds of quantum mechanical algorithms for different kinds of problems in recent years. Because of massive quantum parallelism, quantum computer can solve many problems more efficiently. 0/1 knapsack problem is a typical NPC problem. Its computing complexity is O(2 n ) steps. This paper gives a quantum mechanical algorithm to solve 0/1 knapsack problem, which is based on Grover algorithm and quantum exponential searching algorithm. The algorithm doesn't involve any classical method to improve search efficiency and the solution can be obtained in O(c2 n2 ) steps with a probability of at least 1-12 c.

Chinese Journal of Computers•Jan 1, 1999•1 citation

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 right one. 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.

•Jun 15, 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

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

Quantum-based algorithm and circuit design for bounded Knapsack optimization problem

Wenjun Hou, Marek A. Perkowski

The Knapsack Problem is a prominent problem that is used in resource allocation and cryptography. This paper presents an oracle and a circuit design that verifies solutions to the decision problem form of the Bounded Knapsack Problem. This oracle can be used by Grover Search to solve the optimization problem form of the Bounded Knapsack Problem. This algorithm leverages the quadratic speed-up offered by Grover Search to achieve a quantum algorithm for the Knapsack Problem that shows improvement with regard to classical algorithms. The quantum circuits were designed using the Microsoft Q# Programming Language and verified on its local quantum simulator. The paper also provides analyses of the complexity and gate cost of the proposed oracle. The work in this paper is the first such proposed method for the Knapsack Optimization Problem.

Quantum Information and Computation•Aug 1, 2020•6 citations

Hybrid Quantum Search Algorithm for Solving the Multi-Dimensional Knapsack Problem

Gordon Cui, Rei Sato, Kazuhiro Saito +2 more

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.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•1 citation
Knapsack problem is one of the NP complete problems.Its computational complexity is O( 2n).This paper presents the quantum mechanical algorithm based on the fixed phase quantum search to solve the knapsack problem,and the algorithm also gets probability of success at least 98% in O((N/M)~(1/2)) quantum mechanical steps( Where M is the number of matches).This quantum algorithm has higher probability of success than the algorithm based on Grover algorithm with multiple matches in the search space.
The scientists have given various kinds of quantum mechanical algorithms for different kinds of problems in recent years. Because of massive quantum parallelism, quantum computer can solve many problems more efficiently. 0/1 knapsack problem is a typical NPC problem. Its computing complexity is O(2 n ) steps. This paper gives a quantum mechanical algorithm to solve 0/1 knapsack problem, which is based on Grover algorithm and quantum exponential searching algorithm. The algorithm doesn't involve any classical method to improve search efficiency and the solution can be obtained in O(c2 n2 ) steps with a probability of at least 1-12 c.
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 right one. 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.
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
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.
The Knapsack Problem is a prominent problem that is used in resource allocation and cryptography. This paper presents an oracle and a circuit design that verifies solutions to the decision problem form of the Bounded Knapsack Problem. This oracle can be used by Grover Search to solve the optimization problem form of the Bounded Knapsack Problem. This algorithm leverages the quadratic speed-up offered by Grover Search to achieve a quantum algorithm for the Knapsack Problem that shows improvement with regard to classical algorithms. The quantum circuits were designed using the Microsoft Q# Programming Language and verified on its local quantum simulator. The paper also provides analyses of the complexity and gate cost of the proposed oracle. The work in this paper is the first such proposed method for the Knapsack Optimization Problem.
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.