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

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, 20260 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 JournalJan 1, 20090 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, 20260 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, 20083 citations

Quantum Optimization Heuristics with an Application to Knapsack Problems

Wim van Dam, Karim Eldefrawy, Nicholas Genise +1 more

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.

arXiv:2108.08805IEEE International Conference on Quantum Computing and Engineering (QCE)Oct 1, 202126 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, 20260 citations