# Review Quantum Circuit Synthesis for [PERSON]'s Algorithm Oracle
## 4 State of the Art
### Classical Synthesis Methodologies
This function was the input to the Tweedledum [31] library; this C++ library has several tasks for synthesizing and optimizing quantum circuits. The specific function used was based on the ESOP-based technique. This technique works similarly to the Zeghalkin polynomials, decomposing the function into an expression that can be later transformed into a particular type of gate, the Toffoli gates. The main advantage of this technique is that it does not require a previous status of reversibility for the Boolean function. Still, it is only performant to small circuits, and it increases the required number of qubits quickly. To solve this problem, a method of hierarchical synthesis was implemented. It divides the Boolean function into intermediate computations that can be later run with specific synthesis techniques, such as ESOP. For this purpose, the library Caterpillar [32] was used. This library has multiple techniques for implementing hierarchical synthesis. The one implemented was XAG-based, which uses the \(AND\) and \(XOR\) gates for dividing the circuit. This type of implementation has the number of qubits defined by \(n+1+a\), where \(n\) represents the number of qubits required by the search function, and \(a\) represents the number of temporary ancilla qubits used to store the intermediate results. Finally, the Boolean function that defines the system can be represented by Equation (11). The main difference between this methodology and [PERSON]'s is that apart from the input and output qubits required for a quantum circuit, ancilla qubits \(a\) appear and serve as an  
Figure 4: Quantum circuit representation of \(f_{2}\). anchor point to additional calculations and divisions of the quantum circuit that allow more complex procedures. \[\left|\,x\right\rangle\left|\,y\right\rangle\left|\,0\right\rangle^{a}\,\to\, \left|\,x\right\rangle\left|\,y\oplus f(x)\right\rangle\left|\,0\right\rangle^ {a} \tag{11}\]  
Finally, [PERSON] implemented the circuit in Qiskit, a Python library created by IBM to simulate and run the quantum circuits. He took the winning implementation for the challenge and compared it to the obtained results from their procedure. The cost function used for evaluation was \(cost=n_{1q}+10\cdot n_{2q}\), where \(n_{1q}\) represents the number of one-qubit gates and \(n_{2q}\) represents the number of two-qubit gates. The circuit optimization was performed manually, and they concluded that their approach had better results than the ones given on the challenge after optimization. The main limitations of this approach were the number of qubits used due to the necessity of a division of circuits that can manage reversible Boolean functions and the manual process of optimization for obtaining comparable results [22]. A similar approach is the one conducted by [PERSON] [23]. It consists of using the XAG graphs as a representation of the quantum circuit that can then be divided into smaller circuits, with the main difference of implementing an optimizer for the division of the graphs based on the number of qubits required and the number of gates. This methodology allows for a reduction in the number of ancilla qubits used to store the intermediate results in qubits of the operation without affecting the reversibility of the unitary matrices. This algorithm was evaluated using [PERSON]'s algorithm search of functionally different graphs, finding a reduction of 30% in the number of gates used and a 2% reduction in the qubits needed. Another approach that tries to tackle the number of qubits problems is the one conducted by [PERSON] [11]. He proposes two alternatives for optimizing the oracle synthesis for [PERSON]'s algorithm. The first proposition is to search for similarity instead of equality, which means searching for a distance between the required field and the desired output. This type of procedure can be conducted with a quantum function \(T\) that represents the distance between the desired output and the evaluated qubits.