# Quantum Circuit Synthesis Using Fuzzy-Logic-Assisted Genetic Algorithms
However, executing quantum algorithms on physical devices remains a challenge. Quantum algorithms, once developed, need to be converted into a _quantum circuit_ compatible with the target device on which it will be executed. This is because physical devices typically support a limited number of _gates_, and all circuits executed on them must be expressed using only these gates. The process of converting an input quantum algorithm to a machine's _native basis gate-set_, is termed _quantum compilation_ or _quantum circuit synthesis_. Circuit synthesis is also subject to additional constraints. In a given quantum device, multi-qubit gates may only be applicable between a limited set of qubits [5], determined by the connectivity or _topology_ of the qubits. Thus, _routing_ and _mapping_ of logical qubits between physical qubits on the machine may be required. Since routing is typically achieved using gates during execution, it becomes desirable to optimize routing to minimize gate overhead. Moreover, current generation _Noisy Intermediate-Scale Quantum_ (NISQ) [6] devices are very susceptible to environmental _noise_. The state of qubits can rapidly become corrupted, in a process called _decoherence_[7; 8], causing errors in any running computation. Thus, circuits need to be designed with sufficiently short execution times, measured by circuit _depth_, to ensure acceptable fidelity of results. In addition, the application of gates, particularly multi-qubit gates such as CNOT, can also introduce errors [9]. Therefore, it is beneficial to have circuits with as few gates as possible. The process of synthesizing a circuit for a target machine, while accounting for the machine-dependent constraints mentioned above, can be shown to be a computationally difficult problem and in some cases intractable [10]. Analytical methods are, therefore, unsuitable in the general case for all but the smallest qubit counts. Practical state-of-the-art optimizing compilers that seek to address these constraints attempt to produce _approximate_ results, often using heuristics-based techniques, in order to generate circuits optimized for NISQ device constraints at the cost of some compilation error [11]. However, one key challenge approximate compilers face when synthesizing quantum circuits for NISQ devices is that the imposed constraints can be in conflict with each other. For example, better approximations may be achieved with longer circuits, increasing risk of decoherence, while shorter depth targets reduce flexibility for the compiler, making it difficult to achieve compilation error targets. To address this challenge, in this work, we model quantum circuit synthesis for NISQ devices as a _multi-objective optimization_ (MOO) problem and propose a _genetic-algorithm-_based (GA) [12; 13] synthesis technique. In particular, we leverage the Non-dominated Sorting Genetic Algorithm variant II (NSGA-II) [14], a MOO-specific GA, for the simultaneous optimization of approximation error, circuit depth and number of CNOT gates in synthesized circuits. GAs are a class of gradient-free optimization techniques inspired by the process of _natural selection_ and known for their guaranteed convergence [15], ability to escape local minima and inherent parallelization potential. We also propose a runtime parameter adaptation mechanism leveraging _fuzzy logic_[16] to improve GA efficiency. Fuzzy logic enables us to formulate the GA runtime parameter update mechanism using sophisticated linguistically defined variables and relationships, with the ability to tune how these are interpreted. Our contributions in this work can be summarized as follows:  
1. Propose a GA-based quantum circuit synthesis algorithm which synthesizes machine-compatible circuits from a given unitary. 2. Leverage existing MOO techniques to optimize multiple synthesis objectives simultaneously, minimizing approximation error, circuit depth and number of gates, specifically multi-qubit gates such as CNOTs. 3.