0
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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: enter image description here

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$:

enter image description here

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

enter image description here

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):

enter image description here

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 ;-)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.