# Quantum Circuit Synthesis Using Fuzzy-Logic-Assisted Genetic Algorithms
## 4 Materials and Methods
### Parallelization and Acceleration of GA  
Typically, the fitness function evaluation of individual chromosomes is the most computationally expensive step in a GA. However, since population members can generally be evaluated independently, the fitness evaluation step is also _embarrassingly parallel_. This also means that the workload, i.e., the population size can be scaled proportionally with available computational resources. In our work, we leverage the parallel nature of GAs and utilize the Python multiprocessing library [81] to distribute chromosomes to separate cores/processes for evaluation, and collect them back for further processing. This method scales linearly with the number of available cores and, thus, bigger population sizes can be evaluated efficiently given more computational resources. However, it is worth mentioning that if the subroutines for function evaluation utilize multiple cores/processes themselves, then the one-to-one ratio of cores to chromosomes will not be guaranteed. Moreover, the communication overhead becomes significant in the cases of larger population size and higher number of cores, and must be accounted for.  
The fitness evaluation of a chromosome requires running three subroutines: depth calculation, computation of number of CNOTs, and approximation error calculation. Performance profiling reveals that the last subroutine is the most computationally intensive since it involves free parameter tuning using the BFGS-based numerical optimizer. This optimizer repeatedly calls the approximation error function, until the desired accuracy and convergence conditions are achieved. Calculating the approximation error itself involves three main steps: (a) decoding the chromosome into the equivalent quantum circuit, (b) obtaining the equivalent unitary of the circuit and (c) calculating the approximation error using the formula in (3). Upon deeper investigation, it was discovered that the second step, obtaining a unitary from a circuit, was the biggest performance bottleneck.  
To optimize the first step, we leverage the symbolic variable feature of the IBM Qiskit circuit objects. Specifically, we use symbolic variables for any free parameters in the parameterized gates and cache the circuit decoded from the chromosome. Thus, instead of regenerating the circuit with parameters applied in each iteration, just the free parameter values are supplied before converting to unitary.  
To address the next two steps, we use Qiskit API functions to obtain unitary matrices from the circuits which are used to compute the final error value using (3). To optimize the computation of the error value, we combine the last two steps into one. That is, instead of computing the unitary for a solution circuit, we append the adjoint of our input unitary as a black-box gate to the solution circuit. The final unitary of the resultant circuit is \(U_{in}^{\mathrm{t}}U_{syn}\), which can be obtained using fast Qiskit API functions. From there, we can simply plug this value into (3) and obtain the final error.  
Figure 15 in Appendix B.3 shows a visual representation of this optimization, where we highlight parts of the optimized and unoptimized functions called repeatedly by the numerical optimizer. However, note that circuits without any parametrized gates do not incur any numerical optimization time penalty. Lastly, since approximation error calculations require \(U_{in}^{\mathrm{t}}\), we calculate this matrix ahead of time and cache it.