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 Computing and Network Communications

Quantum Walk based genetic algorithm for 0–1 quadratic knapsack problem

Arish Pitchai, A. V. Reddy, Nickolas Savarimuthu

Published Dec 1, 2015• 4 citations
Publisher

Abstract

This paper proposes a genetic quantum algorithm based on discrete time quantum walk (QWGA) to solve 0-1 quadratic knapsack problem. Genetic Quantum Algorithms makes use of the qubit representation and superposition phenomenon which are the counter-intuitive characteristics of quantum mechanics. Discrete Quantum Walk (DQW) on a hypercube is used in the place of genetic operators like mutation, crossover, etc. Achievement of rapid convergence and avoidance of local optima with the help of the quantum principles is explained in this paper. The possibilities of extending the proposed algorithm to various combinatorial optimization problems is discussed in detail. Superiority of the proposed algorithm over genetic quantum algorithm based on rotation operators is evident from the results.

DOI
10.1109/coconet.2015.7411199

Related papers

Genetic quantum algorithm and its application to combinatorial optimization problem

Kuk-Hyun Han, Jong-Hwan Kim

This paper proposes a novel evolutionary computing method called a genetic quantum algorithm (GQA). GQA is based on the concept and principles of quantum computing such as qubits and superposition of states. Instead of binary, numeric, or symbolic representation, by adopting qubit chromosome as a representation GQA can represent a linear superposition of solutions due to its probabilistic representation. As genetic operators, quantum gates are employed for the search of the best solution. Rapid convergence and good global search capability characterize the performance of GQA. The effectiveness and the applicability of GQA are demonstrated by experimental results on the knapsack problem, which is a well-known combinatorial optimization problem. The results show that GQA is superior to other genetic algorithms using penalty functions, repair methods and decoders.

IEEE Congress on Evolutionary Computation (CEC)•Nov 7, 2002•672 citations

A Quantum Genetic Algorithm to Solve Combinatorial Optimization Problem

Xing-Fu Wang

Based on quantum mutation, a quantum genetic algorithm (QGA) to solve combinatorial optimization problem is proposed.It has good features of genetic quantum algorithm (GQA) and traditional genetic algorithm,which can obtain the best solution with one chromosome in a short time.Comparing experiments have been conducted on a typical combinatorial optimization problem——0/1 knapsack problem.Experimental results have shown that the proposed quantum genetic algorithm is superior to genetic quantum algorithm and traditional genetic algorithm on performance.

Dianzi xuebao•Jan 1, 2004•17 citations

Parallel quantum-inspired genetic algorithm for combinatorial optimization problem

Kuk-Hyun Han, Kui-Hong Park, Ci-Ho Lee +1 more

This paper proposes a new parallel evolutionary algorithm called parallel quantum-inspired genetic algorithm (PQGA). Quantum-inspired genetic algorithm (QGA) is based on the concept and principles of quantum computing such as qubits and superposition of states. Instead of binary, numeric, or symbolic representation, by adopting the qubit chromosome as a representation, QGA can represent a linear superposition of solutions due to its probabilistic representation. QGA is suitable for parallel structures because of rapid convergence and good global search capability. That is, QGA is able to possess the two characteristics of exploration and exploitation simultaneously. The effectiveness and the applicability of PQGA are demonstrated by experimental results on the knapsack problem, which is a well-known combinatorial optimization problem. The results show that PQGA is superior to QGA as well as other conventional genetic algorithms.

IEEE Congress on Evolutionary Computation (CEC)•Nov 13, 2002•193 citations

Higher-order quantum genetic algorithm for 0-1 knapsack problem

Valerii M. Tkachuk, Orysya M. Tkachuk

In order to enhance the effectiveness of the quantum genetic algorithm (QGA), it is proposed to switch to higher-order quantum registers in the quantum chromosome representation. Such representation makes it possible to apply a powerful quantum computations mechanism – quantum state entanglement. In the algorithm implementation, we also use an adaptive quantum gate operator and propose a quantum chromosome recovery technology for solving constrained combinatorial optimization problems. The influence of the quantum register size on the algorithm efficiency has been investigated. The advantages of the suggested approach in comparison with the QGA traditional implementation are demonstrated on the example of multidimensional 0–1 knapsack problem and different levels of input data correlation.

System research and information technologies•Oct 16, 2018•1 citation

A Novel Improved Quantum Genetic Algorithm for Combinatorial Optimization Problems

Xihua Zou

Based on quantum genetic algorithm(QGA),a novel improved quantum genetic algorithm(NIQGA)to solve combinatorial optimization problem is proposed.To make full use of interference and entanglement characteristics of quantum state,dynamic step length in adjustment of angle of quantum gate,quantum crossover operation and quantum mutation operation are introduced,therefore high efficiency for optimization is achieved.Two typical combinatorial optimization problems—0/1 knapsack problem and route selection problem,are adopted to confirm the performance of NIQGA.Experimental results show that compared with GA and QGA,NIQGA is characterized by fast convergence rate and excellent capability on global optimization,especially better performance for combinatorial optimization problem with less correlation of genes.

Dianzi xuebao•Jan 1, 2007•15 citations

Quantum Differential Evolution Algorithm for Quadratic Knapsack Problem

LU Wen-lin

A quantum differential evolution is proposed for discrete optimization.The population diversity is increased by superposition characteristic. Based on the idea of catastrophe theory, the algorithm uses mutation operation to avoid falling into local optimum. The algorithm has stronger global optimization capability .The results of experiments on quadratic knapsack problem and comparison with other algorithms show that the algorithm is feasible and effective.

Microcomputer Information•Jan 1, 2010•0 citations
This paper proposes a genetic quantum algorithm based on discrete time quantum walk (QWGA) to solve 0-1 quadratic knapsack problem. Genetic Quantum Algorithms makes use of the qubit representation and superposition phenomenon which are the counter-intuitive characteristics of quantum mechanics. Discrete Quantum Walk (DQW) on a hypercube is used in the place of genetic operators like mutation, crossover, etc. Achievement of rapid convergence and avoidance of local optima with the help of the quantum principles is explained in this paper. The possibilities of extending the proposed algorithm to various combinatorial optimization problems is discussed in detail. Superiority of the proposed algorithm over genetic quantum algorithm based on rotation operators is evident from the results.
This paper proposes a novel evolutionary computing method called a genetic quantum algorithm (GQA). GQA is based on the concept and principles of quantum computing such as qubits and superposition of states. Instead of binary, numeric, or symbolic representation, by adopting qubit chromosome as a representation GQA can represent a linear superposition of solutions due to its probabilistic representation. As genetic operators, quantum gates are employed for the search of the best solution. Rapid convergence and good global search capability characterize the performance of GQA. The effectiveness and the applicability of GQA are demonstrated by experimental results on the knapsack problem, which is a well-known combinatorial optimization problem. The results show that GQA is superior to other genetic algorithms using penalty functions, repair methods and decoders.
Based on quantum mutation, a quantum genetic algorithm (QGA) to solve combinatorial optimization problem is proposed.It has good features of genetic quantum algorithm (GQA) and traditional genetic algorithm,which can obtain the best solution with one chromosome in a short time.Comparing experiments have been conducted on a typical combinatorial optimization problem——0/1 knapsack problem.Experimental results have shown that the proposed quantum genetic algorithm is superior to genetic quantum algorithm and traditional genetic algorithm on performance.
This paper proposes a new parallel evolutionary algorithm called parallel quantum-inspired genetic algorithm (PQGA). Quantum-inspired genetic algorithm (QGA) is based on the concept and principles of quantum computing such as qubits and superposition of states. Instead of binary, numeric, or symbolic representation, by adopting the qubit chromosome as a representation, QGA can represent a linear superposition of solutions due to its probabilistic representation. QGA is suitable for parallel structures because of rapid convergence and good global search capability. That is, QGA is able to possess the two characteristics of exploration and exploitation simultaneously. The effectiveness and the applicability of PQGA are demonstrated by experimental results on the knapsack problem, which is a well-known combinatorial optimization problem. The results show that PQGA is superior to QGA as well as other conventional genetic algorithms.
In order to enhance the effectiveness of the quantum genetic algorithm (QGA), it is proposed to switch to higher-order quantum registers in the quantum chromosome representation. Such representation makes it possible to apply a powerful quantum computations mechanism – quantum state entanglement. In the algorithm implementation, we also use an adaptive quantum gate operator and propose a quantum chromosome recovery technology for solving constrained combinatorial optimization problems. The influence of the quantum register size on the algorithm efficiency has been investigated. The advantages of the suggested approach in comparison with the QGA traditional implementation are demonstrated on the example of multidimensional 0–1 knapsack problem and different levels of input data correlation.
Based on quantum genetic algorithm(QGA),a novel improved quantum genetic algorithm(NIQGA)to solve combinatorial optimization problem is proposed.To make full use of interference and entanglement characteristics of quantum state,dynamic step length in adjustment of angle of quantum gate,quantum crossover operation and quantum mutation operation are introduced,therefore high efficiency for optimization is achieved.Two typical combinatorial optimization problems—0/1 knapsack problem and route selection problem,are adopted to confirm the performance of NIQGA.Experimental results show that compared with GA and QGA,NIQGA is characterized by fast convergence rate and excellent capability on global optimization,especially better performance for combinatorial optimization problem with less correlation of genes.