# Review Quantum Circuit Synthesis for [PERSON]'s Algorithm Oracle
## 4 State of the Art
### Classical Synthesis Methodologies
This type of search also reduces the number of \(CX\) gates that the search procedure requires but has the cost of requiring a more precise number of iterations for the oracle and the diffusion operator [11]. The second alternative he proposes is a Phase-Tolerant Synthesis. This type of synthesis considers that the phase inversion of a state is not required for it to be applied to [PERSON]'s algorithm since it does not change the result obtained. For example, the state shown in Equation (12) represents the desired state of the synthesis method, where \(x\) represents the input, \(T(x)\) the distance to the desired output, \(\mathcal{X}_{x}\) garbage phases, and \(n\) the number of inputs. This expression has additional phase terms \(\mathcal{X}_{x}\) that can be eliminated from the synthesis process. \[\sum_{x=0}^{2^{n}-1}\exp(i\mathcal{X}_{x})\left|\,x\right\rangle\left|\,T(x)\right\rangle \tag{12}\]  
This procedure significantly reduces the gates required for constructing the quantum circuit. [PERSON] assessed this implementation with a database search. He encrypted the data in a quantum circuit. Then, he used the Gray synthesis method from the Tweedledum library and the Phase Tolerant Synthesis to construct an oracle that can search for a register [11]. After the implementation, he iterated thirty times for different database sizes and measured the average \(CNOT\) gates, \(U\) rotation gates that were happening and the number of qubits used. The experiment concluded that the metrics scaled linearly with the database being searched independent of the method used. The limitations of this approach are that the number of qubits is very dependent on the database being used in the search process, the hash algorithm limits the similarity search, and the involvement of a logic synthesis increases the computational complexity compared to the classical search. [PERSON] [24] took another approach to synthesizing Oracles. This approach is similar to the one proposed by [PERSON] [17], where instead of generating oracles based on a Boolean function, an initial set of quantum circuits is defined for performing specific arithmetic operators. In the case of [PERSON] [17], this is conducted with a less-than operation and a search of numbers that are less than a specific value with [PERSON]'s algorithm. [PERSON] uses this concept to define a compilation framework [24]. He proposes a language with a series of steps that transform a function into an oracle that can be used on a quantum circuit. The process starts with the OQIMP, a predefined language that allows the expression of oracles in terms of a series of operations already available. The representation of an Oracle in OQIMP language is then translated to OQASM, a quantum assembly language, throughout a series of predefined circuits and gates that do not have an entanglement due to a language restriction. The quantum circuit is then translated to a Quantum Computer or simulator for testing. Besides the primary process, [PERSON] has designed a test suite to verify the compatibility of the circuits [24]. This verification consists of a formal automated tester set programmed in COQ; additionally, with a randomized test suite PBT, this last one allows testing the process based on random inputs and expected outputs. This methodology has a predefined reduction in the number of qubits and the depth of the circuit. [PERSON] implemented an oracle to evaluate the implementation and find matching registers in a hash function (ChaCha20). This oracle was later used in [PERSON]'s algorithm to assess its validity, but its performance was not evaluated. The main limitation of this approach is that it is restricted to the language being used, properties like the entanglement are not an option for the qubits available, and the optimization process is performed after the circuit's construction. A similar approach was implemented by [PERSON] [25], establishing a limited set of symbolic mapping between the input of the gates and the outputs.