Explaining the Implicit Parallelism of Genetic Algorithm and Computational Complexity by Quantum Theory

摘要

Superposition principle of quantum theory is introduced in this paper. The genetic algorithm has been described by quantum superposition theory. It implies genetic algorithm is essentially a kind of quantum algorithm in the classical computer on the reduced order to achieve. It through genetic manipulation to input superposition states data into classical computer. In the evolutionary process, a lot of implicit modes have been measured, so as to realize the parallel search and processing in the model space. It is implicit parallelism of genetic algorithm. The quantum theory can also be used to analyze the problem’s computational complexity. Quantum superposition theory and entropy are used to get the problem’s lower bound of computational complexity. Using this method the problem’s lower bound of computational complexity is only decided by itself. It is independent of the algorithm’s details.