# Review Quantum Circuit Synthesis for [PERSON]'s Algorithm Oracle
## 4 State of the Art
### Classical Synthesis Methodologies  
Classical synthesis methodologies start with a Boolean function as its main component for representing an oracle. This function is later transformed into a quantum circuit. The types of transformations depend on the methodology. The studies that include this methodology can be divided into two subgroups: one that uses a direct approach for converting the Boolean function in a circuit and one that uses a framework, like a compiler, for setting the transformation and can include more complex operations. For example, [PERSON]'s initial approach [PERSON] (1973) starts with a function representing the expected output of the circuit as shown in Table 2, where \(x\) represents an input bit and \(f_{i}\) a Boolean function acting on \(x\). [PERSON] proposes the construction of the desired output based on a vector space, the bases of which depend on the number of qubits used. The vector bases for one qubit are shown in Equation (9), where \(\oplus\) represents a vector sum done in binary base, and \(\mathbb{I}\) represents the vector \( \begin{bmatrix}1\\ 1\end{bmatrix} \). \[E_{1}=x= \begin{bmatrix}0\\ 1\end{bmatrix} ,\,e_{0}=x\bigoplus\mathbb{I}= \begin{bmatrix}1\\ 0\end{bmatrix}  \tag{9}\] \begin{table}
\begin{tabular}{c c c c c} \hline \hline \(x\) & \(f_{0}\) & \(f_{1}\) & \(f_{2}\) & \(f_{3}\) \\ \hline
1 & 0 & 1 & 0 & 1 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Truth table for one bit. Figure 3: Knowledge graph of articles related to quantum oracle synthesis [PERSON] (1973); [PERSON] (1973); [PERSON] (1973); [PERSON] (1973); [PERSON] (1973); [PERSON] (1973); [PERSON] (1973); [PERSON] (1973); and [PERSON] (1973). Yellow nodes represent metaheuristic methodologies, purple nodes represent neural network methodologies, and green nodes represent classical approaches to oracle synthesis. Gray nodes represent languages and libraries used by the different sets of methods. Based on these vector bases, a new polynomial vector can be written for \(\mathrm{e}_{0}\) in terms of the input \(x\), as is shown in Equation (10). Where \(x^{0}\) represents a column vector \( \begin{bmatrix}1\\ 1\end{bmatrix} \), \(x^{1}\) represents \( \begin{bmatrix}0\\ 1\end{bmatrix} \) and the \(e_{0}\) value is equivalent to \(f_{2}(x)\) in Table 2. This is known as a Zhegalkin polynomial and is the main component used by [PERSON] for obtaining the quantum circuit [21]. \[E_{0}=f_{2}(x)=1\cdot x^{0}\bigoplus 1\cdot x^{1} \tag{10}\]  
If the coefficients of variable \(x\) are represented as a column vector \( \begin{bmatrix}1\\ 1\end{bmatrix} \) of name \(p_{0}\), each of the values of vector \(p_{0}\) represents a quantum gate that can be mapped on a quantum circuit. This is shown in Figure 4, where the first qubit represents \(x\) and the second qubit represents the output of the function \(f_{2}(x)\). This procedure can be amplified to multiple inputs and outputs, which is [PERSON]'s main proposition. The main advantage of this approach is that it considers the reversibility of the quantum circuit. This fundamental property is inherited from the unitary matrices that represent the operations. On the other hand, this approach limits the number of qubits used because it involves adding a qubit for each function output. The input qubits are only used as operation resources. Similar problems happen with [PERSON]'s proposition [22]. He uses the problem stated in the 2019 IBM hackathon, called the Zed City problem. The problem consists of a graph representing the distribution of districts in a specific place; the objective is to assign a color to each place, avoiding having adjacent vertices with the same color. [PERSON] proposed representing the problem as a Boolean function that describes the search scope of viable solutions to a specific layout. Then, this function would be processed with [PERSON]'s algorithm to obtain a viable layout [22]. The process was performed by implementing a Python function that represents the Boolean scope of search.