# Reverse engineering an oracle and finding a universal gate set to construct it

Grover's algorithm inputs a function, $$f \colon \{0, 1\}^N \mapsto \{0, 1\}$$, and is tasked with finding where the function is equal to $$1$$. Suppose we were given this set of values (given $$X \subseteq \{0, 1\}^N$$ such that $$f(x \in X) = 1$$).

Is there an algorithm that can convert this into a Grover oracle, $$U | x \rangle = (-1)^{f(x)} | x \rangle$$, but in terms of a universal gate set? In other words, I'm asking if we can take the output of Grover's algorithm, and reconstruct the oracle input.

## 1 Answer

I think you can. The Grover oracle is ultimately composed of phase inversion and inversion around the mean operators, executed in sequence a specific number of iterations.

The phase inversion 'oracle' is usually depicted as:

But it can be straightforward to generate a circuit, especially if the number of solutions is just 1, eg., for a single solution $$|11010\rangle$$:

The inversion around the mean (also called diffusion operator), is straightforward to connect to that ancilla bit $$y$$ at the bottom:

It corresponds to the closed form below, which yields $$-W$$, where W would be a big operator. Note the - sign, but the direction of the rotation does not matter: $$H^{\otimes n} X^{\otimes {n-1}}(CZ)^{n}X^{\otimes {n-1}}H^{\otimes n} = -W$$

And then you have to sequence these components similar to this picture (the operator names are a bit different):

If you have multiple solutions, you'd have to logically 'or' them to that ancilla qubit $$y$$, a few more ancillas may be necessary for that when constructing the circuit (I also hope I got those drawings correct ;-)