# Review Quantum Circuit Synthesis for [PERSON]'s Algorithm Oracle
## 4 State of the Art
### Metaheuristics Methodologies  
Metaheuristic methods are another methodology that uses metaheuristic optimization algorithms to generate quantum circuits. These algorithms seek to optimize the output using metrics established for each problem domain [12]. One of these methodologies is the one proposed by [PERSON] [12]. The methodology is called Quantum Ant Programming (QAP) and is based on the Ant Colony Optimization metaheuristic for generating quantum circuits. Its principle is based on a graph; the ants chose a path for this graph, generating a subgraph that represents the desired circuit. The ants create a trail of pheromones to reinforce the gates they should use to obtain the desired results, and the evaporation metric is added to avoid bias in the process. Based on the trail the ants went, a circuit can be created to obtain the results based on the inputs. [PERSON] noticed various problems with the standard way of measuring the performance of this model, so he proposed a new metric for measuring the system's performance and used it in the optimization process. The metric is called the Fidelity of Means Squared to calculate the difference between the obtained states and the desired ones, considering the phase of the result as shown in Equation (13), where \(\left|\,y\right\rangle\) represents the expected output of the system and \(\left|\,x\right\rangle\) the input state of the system. \[\mathcal{F}(\left|\,y\right\rangle,\,\left|\,x\right\rangle)=\left|\,\left\langle y \right|x\right\rangle \tag{13}\]  
The mean square fidelity can be calculated as is shown in Equation (14), where A represents the realized quantum circuit expressed as a unitary matrix, \(X\) represents the set of all input states of the quantum circuit, and \(Y\) represents all expected output states of the circuit. \[\mathcal{MSF}(A,X,Y)=\frac{\sum_{i=1}^{\left|X\right|}\mathcal{F}(\left|\,y \right\rangle,\,A\left|\,x\right\rangle)^{2}}{\left|X\right|} \tag{14}\]  
With this metric, each algorithm was run one hundred times in a predefined test versus a random generation procedure for generating quantum circuits. This approach obtains better results than random generators but has bad fidelity scores for big circuits. It has the limitation of needing more generalization for more extensive circuits and requiring an expensive run procedure each time a new circuit is needed. Another approach is the one proposed by [PERSON] [26]. He uses genetic programming to generate the oracles required for [PERSON]. The algorithm uses a tree structure to represent each circuit and tries to insert, delete, or replace the subtree structure at each iteration. Some constraints are imposed on the mutation operators to ensure syntactically valid quantum programs as individuals [26]. The fitness function used for generating these circuits is reported in Equation (15), where \(h\) represents the total number of fitness cases used minus the number of fitness cases where the program produces the correct answer. \[f=h+c+e \tag{15}\]  
The \(c\) term represents the correctness component and is shown in Equation (16), where the error term represents a threshold applied to not take into consideration more minor errors. \[C=\frac{\sum_{i=1}^{n}\max(0,error_{i}-0.48)}{\max(h,1)} \tag{16}\]  
The last term, \(e\), represents efficiency, which means the number of gates in the final solution divided by a large constant. This allows the circuit generation to center on giving satisfactory results and then optimizing the circuit length based on those results. [PERSON] finally does not use the output as a whole but uses small functions that make the process more scalable to obtain the average of the fitness functions for each result and maximize the desired output. This approach is assessed with small circuits but needs to be escalated for more extensive circuits. Another approach to generating quantum oracles as unitary matrices based on evolutionary algorithms was the one proposed by [PERSON] [27].