High Speed Genetic Algorithms in Quantum Logic Synthesis: Low Level Parallelization vs. Representation?
Martin Lukac, Michitaka Kameyama, Michael Miller and Marek Perkowski
This paper focuses on the high speed Evolutionary Algorithms (EA) for the synthesis of Quantum circuits. We present a comparative study in the Evolutionary Quantum Logic Synthesis (EQLS) using different circuits representation. In EQLS, circuits are synthesized in large number while the Evolutionary Algorithm searches for a potential solution. The speed of translating the genotype (encoded binary strings) to the phenotype (circuits) depends on how fast is the creation of the circuit functional representation and how fast this representation can be evaluated to determine its function. We present the comparison between an efficient representation of the synthesized quantum circuit as Quantum Multi-Valued Decision Diagram (QMDD) and a low level parallelized evaluation method using hardware accelerated matrix manipulation. We compare the circuit representation’s computation speed as well as the used computational resources on various steps of the overall design of the circuit. As it is shown in the experiments, each approach has its advantages and limitations, and an appropriate choice of each of them yields better results for a subset of the Quantum Logic synthesis (QLS) problems.
Keywords: Evolutionary Quantum Logic Synthesis, Parallel GA, Matrix Computation Acceleration