A novel quantum evolutionary algorithm for quadratic Knapsack problem

The Quadratic Knapsack Problem (QKP) deals with maximizing a quadratic objective function subject to given constraints on the capacity of the Knapsack. We assume all coefficients to be non-negative and all variables to be binary. Solution to QKP generalizes the problem of finding whether a graph contains a clique of given size. We propose in this paper a Novel Quantum Evolutionary Algorithm (NQEA) for QKPs. These algorithms are general enough and can be used for similar subsection of problems. We report in this paper solutions which lie in less than 1% of the optimal solutions. We also show that our algorithm is scalable to much larger problem sizes and is capable of exploiting the search space to its maximum.