New coding scheme to compile circuits for Quantum Approximate Optimization Algorithm by genetic evolution

Compiling quantum circuits on target quantum hardware architectures is one of the key issues in the development of quantum algorithms, and the related problem is known as the Quantum Circuit Compilation Problem (QCCP). This paper presents a genetic algorithm for solving QCCP instances for Quantum Approximate Optimization Algorithms (QAOA). In particular, such instances represent quantum circuits for the resolution of both MaxCut and Graph-Coloring combinatorial problems. The presented algorithm represents a significant improvement over an already existing genetic algorithm called Decomposition Based Genetic Algorithm (DBGA), and is characterized by a completely new coding scheme that allows to reduce the number of SWAP gates introduced in the decoding step, consequently reducing the circuit depth. After providing a description of the problem, this paper presents the newly produced genetic algorithm (termed DBGA-X) in detail, especially focusing on the new coding/decoding scheme. Subsequently, a set of results will be presented that demonstrate the superior performance of the new method compared with the results obtained from recent literature against the same benchmark. In addition, new benchmarks characterized by larger quantum architectures and by a higher number of compilation passes are proposed in this paper, to the aim of testing the scalability of the proposed method in more realistic scenarios.& COPY; 2023 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).