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

Communications in computer and information science

Solving the 0-1 Knapsack Problem with Polynomial-Time Quantum Algorithm

Hongying Liu, Shuzhi Nie

Published Jan 1, 2012• 0 citations
Publisher
DOI
10.1007/978-3-642-31968-6_45

Related papers

Solving Quadratic Knapsack Problem with Biased Quantum State Optimization Algorithm

Huy Phuc Nguyen Ha, Viết Hùng Nguyễn, Anh Son Ta

Lecture notes in computer science•Jan 1, 2024•1 citation

Quantum algorithm analysis of knapsack problem

Lü Xin, Feng Denggu

Beijing Hangkong Hangtian Daxue xuebao•Nov 30, 2004•0 citations

Benchmarking Quantum Optimization Algorithms for the 0–1 Knapsack Problem Using Qiskit

Kampa Lavanya, T. Surekha, J. David Sukeerthi Kumar +2 more

Lecture notes in networks and systems•Sep 2, 2026•0 citations

Improved Quantum Genetic Algorithm on Multilevel Quantum Systems for 0-1 Knapsack Problem

Valerii M. Tkachuk, Mykola Kozlenko

Lecture notes on data engineering and communications technologies•Jan 1, 2022•0 citations

An Angle-expressed Quantum Evolutionary Algorithm for Quadratic Knapsack Problem

Hao Li

Abstract The quadratic knapsack problem(QKP) is a typical combinatorial optimization problem. It is arisen in many optimization fields, but there exist no pseudo-polynomial time algorithm to solve it. In this paper, we propose an angle-expressed quantum evolutionary algorithm to solve QKP. In this algorithm, the qubits are expressed in the angle and initialized according to the value densities of their corresponding items, the rotation angle of Q-gate is determined through an analytical formula, and Hε gate is used to prevent from premature convergence. For infeasible solution, a dynamic value density is introduced to choose item to be selected or dropped. Finally, experiment demonstrates the effectiveness of the algorithm.

IOP Conference Series Materials Science and Engineering•Oct 1, 2019•2 citations

Optimization on a Novel Quantum Greedy Approach Based on Learning Strategy for Zero and One Knapsack Problem and Evaluation

Mir Shahriar Emami

Now a days probabilistic approach can be a convenient solution for solving many of the problems especially the problems with high time complexity like as knapsack problem. In this paper I present a new quantum computation approach based on learning strategy and greedy approach for solving the zero and one knapsack problem with polynomial time complexity about O (n) and as a result of evaluation of my presented approach I show that the probability of success of the given approach is low based on disentangled quantum registers and without learning the past observations. Nevertheless I show that how learning approach can significantly increases the probability of success of the given quantum greedy method. Also as an another result of evaluation of the presented approach I show that if the standard deviation of the items increases, the probability of success of the given new learning approach increases too.

International Conference on Machine Learning and Applications•Jan 1, 2008•1 citation
Abstract The quadratic knapsack problem(QKP) is a typical combinatorial optimization problem. It is arisen in many optimization fields, but there exist no pseudo-polynomial time algorithm to solve it. In this paper, we propose an angle-expressed quantum evolutionary algorithm to solve QKP. In this algorithm, the qubits are expressed in the angle and initialized according to the value densities of their corresponding items, the rotation angle of Q-gate is determined through an analytical formula, and Hε gate is used to prevent from premature convergence. For infeasible solution, a dynamic value density is introduced to choose item to be selected or dropped. Finally, experiment demonstrates the effectiveness of the algorithm.
Now a days probabilistic approach can be a convenient solution for solving many of the problems especially the problems with high time complexity like as knapsack problem. In this paper I present a new quantum computation approach based on learning strategy and greedy approach for solving the zero and one knapsack problem with polynomial time complexity about O (n) and as a result of evaluation of my presented approach I show that the probability of success of the given approach is low based on disentangled quantum registers and without learning the past observations. Nevertheless I show that how learning approach can significantly increases the probability of success of the given quantum greedy method. Also as an another result of evaluation of the presented approach I show that if the standard deviation of the items increases, the probability of success of the given new learning approach increases too.