QUANTUM EVOLUTIONARY ALGORITHM FOR QUANTUM CIRCUIT SYNTHESIS

Abstract

Quantum computing area has a lot research attention due to opportunities that possessing such device could provide. For example, quantum computers could deliver new insights to previously unsolvable problems. The reason for that is higher parallel capabilities of such devices. In addition, since quantum computers are naturally reversible, no heat dissipation occurs during computation [21]. This property could serve as a viable solution to the problem that computer chip production industry faces. Moreover, since the chip manufacturing industry reaches nanometer scale of size of elements, the effects that could cause unexpected information behavior in classical paradigm are part of the technology of quantum devices [31, 14]. Considering possible benefits that could be achieved by quantum computing devices, the new areas of Quantum Information Theory, Quantum Cryptography, Quantum Algorithms and Logic Design and many others emerged at the end of the twentieth century [31]. These areas are concentrating their efforts on solving problems of designing communication protocols, ensuring the security of the new systems, constructing appropriate algorithms. Computers that could be advancing in finding solutions in problems listed above require quantum circuits that have optimal structure and could implement error correction. This is the main motivation for this thesis work to explore the problem of circuit design. The approach that we investigate is circuit construction by the means of Quantum Evolutionary Algorithms. We propose a version of an algorithm that accounts with specificity and constraints of quantum paradigm. We use its Graphic Processing Unit (GPU) accelerated classical implementation to evaluate the behavior and performance of the proposed algorithm. Later we discuss additional complexity introduced by accounting with these constraints. We support our ideas with results of synthesis of small circuits and compare the performance with classical genetic algorithm on similar task.