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

Chinese Journal of Computers

SOLVING THE 0/1-KNAPSACK PROBLEM ON QUANTUM COMPUTER

Jin Hu

Published Jan 1, 1999• 1 citation
OpenAlex

Abstract

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.

Related papers

Quantum mechanical algorithm to solve knapsack problem

Hao Xu, Pla Information

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.

Computer Engineering and Applications Journal•Jan 1, 2009•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

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-Search-Based Algorithm for the 0-1 Knapsack Problem

K. A. Stepanenko

Abstract The knapsack problem is an important example of a combinatorial optimization problem with a wide range of applications in direct practical applications. In this article, the author considers the classical version of the problem (0-1 knapsack) and proposes a quantum algorithm for solving it based on a hybrid approach that combines the Grover quantum search algorithm with the procedure for finding the Durr–Hoyer minimum. The paper presents an analysis of the computational complexity of the proposed algorithm, and in addition to theoretical analysis, the article contains an explicit description of the quantum circuit implementing the proposed algorithm.

Russian Microelectronics•Dec 1, 2025•0 citations
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 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.
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 The knapsack problem is an important example of a combinatorial optimization problem with a wide range of applications in direct practical applications. In this article, the author considers the classical version of the problem (0-1 knapsack) and proposes a quantum algorithm for solving it based on a hybrid approach that combines the Grover quantum search algorithm with the procedure for finding the Durr–Hoyer minimum. The paper presents an analysis of the computational complexity of the proposed algorithm, and in addition to theoretical analysis, the article contains an explicit description of the quantum circuit implementing the proposed algorithm.