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

International Conference on Machine Learning and Applications

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

Mir Shahriar Emami

Published Jan 1, 2008• 1 citation
Publisher

Abstract

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.

DOI
10.1109/icmla.2008.100

Related papers

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

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

Resource-efficient formulations of the Knapsack problem for quantum computing

Pim van den Heuvel, Vrinda Mehta, Dennis Willsch +2 more

Quantum computing has emerged as a new tool for solving combinatorial optimization problems. Quantum optimization approaches usually operate on the subclass of Quadratic Unconstrained Binary Optimization (QUBO) problems. Many optimization problems can be reformulated in this form, though there are often multiple ways to do so. The choice of formulation can considerably affect the performance of QUBO solvers in practice. In this work, we study QUBO formulations of the Knapsack problem, a canonical example of a problem with inequality constraints. In the standard formulation these constraints are converted into penalty terms, which requires additional slack variables. Here, we investigate three more resource-efficient approaches for formulating the Knapsack as a QUBO. The first two modify the standard formulation, either by deriving a smaller penalty constant or by reducing the number of slack variables. The third approach is a wholly different method, which avoids the use of slack variables entirely. All three approaches increase the probability of finding the optimal solution, both in simulations of the linear ramp Quantum Approximate Optimization Algorithm (LR-QAOA) and on a D-Wave quantum annealer. The slackless method performs best, increasing success probabilities by several orders of magnitude even for relatively small problem sizes.

arXiv:2611.06797•Nov 4, 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

Comparison between New Quantum Approaches for Finding the Minimum or the Maximum of an Unsorted Set of Integers

Mir Shahriar Emami, Mohammad Reza Fattahi, Hossein Keshmiri

The change has already begun. It is not a simple change but a revolution in the sense of speed and its impact. In this paper we are going to discuss on quantum computer as a physical system and discuss on its main weakness and then based on our new approach we have solved a problem for finding the minimum or the maximum of a set of integers which has not been solved based on previous quantum computing approach with time complexity about O(1) and then we evaluate and comprise it with another quantum algorithm with time complexity about 0(1+radic(n)) which also is given by us and as a result we show that if the size of quantum resister is low then our first quantum approach which has lower time complexity is satisfactory and if the size of quantum register is high then as the probability of success of our first approach decreases so our second approach is more convenient.

IEEE/ACIS International Conference on Computer and Information Science (ICIS)•May 1, 2008•3 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
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.
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.
Quantum computing has emerged as a new tool for solving combinatorial optimization problems. Quantum optimization approaches usually operate on the subclass of Quadratic Unconstrained Binary Optimization (QUBO) problems. Many optimization problems can be reformulated in this form, though there are often multiple ways to do so. The choice of formulation can considerably affect the performance of QUBO solvers in practice. In this work, we study QUBO formulations of the Knapsack problem, a canonical example of a problem with inequality constraints. In the standard formulation these constraints are converted into penalty terms, which requires additional slack variables. Here, we investigate three more resource-efficient approaches for formulating the Knapsack as a QUBO. The first two modify the standard formulation, either by deriving a smaller penalty constant or by reducing the number of slack variables. The third approach is a wholly different method, which avoids the use of slack variables entirely. All three approaches increase the probability of finding the optimal solution, both in simulations of the linear ramp Quantum Approximate Optimization Algorithm (LR-QAOA) and on a D-Wave quantum annealer. The slackless method performs best, increasing success probabilities by several orders of magnitude even for relatively small problem sizes.
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
The change has already begun. It is not a simple change but a revolution in the sense of speed and its impact. In this paper we are going to discuss on quantum computer as a physical system and discuss on its main weakness and then based on our new approach we have solved a problem for finding the minimum or the maximum of a set of integers which has not been solved based on previous quantum computing approach with time complexity about O(1) and then we evaluate and comprise it with another quantum algorithm with time complexity about 0(1+radic(n)) which also is given by us and as a result we show that if the size of quantum resister is low then our first quantum approach which has lower time complexity is satisfactory and if the size of quantum register is high then as the probability of success of our first approach decreases so our second approach is more convenient.
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.