2
$\begingroup$

To program Grover algorithm oracle, we need to know the answer already then what is the point of building the oracle. To me its like we are telling the oracle the correct answer and just asking it the correct answer. Please help to understand the point here.

In other words, since Grover is a search algorithm and if we already know the answer to build the oracle then why do we even need to search/build oracle to find the same answer that we know.

$\endgroup$
2

2 Answers 2

2
$\begingroup$

You don't need to know the answer to build the oracle for Grover. The Oracle only needs to only be able to "mark" the state you're looking for. In a real-life application, you wouldn't be looking for a specific bit-string, but rather you're looking for a bit string with a specific property X. Take the following example for instance:

You have a function $f(x)$ and you want to solve $f(x) = y$, for some $y$. Now for this specific problem, you can usually solve the problem analytically and it would be kind of dumb to do a search for $x$ but I think this example will demonstrate why you wouldn't need to know the answer. To do this using Grover, you can build a circuit $U$ such that:

$$U\vert x\rangle\vert0\rangle = \vert x\rangle \vert f(x)\rangle$$

Then if you prepare the state $(H^{\otimes m}\otimes I^{\otimes n})(\vert 0\rangle^{\otimes m}\otimes \vert 0\rangle^{\otimes n})$, $U$ will map it to:

$$\frac{1}{\sqrt{2^m}}\sum_x \vert x\rangle \vert f(x)\rangle$$

In this case we would need an oracle that can mark a state if it equals $y$, then we can perform Grover's search on the second register. If we're successful, then the first register will contain the answer to $f(x) = y$.

$\endgroup$
2
$\begingroup$

In my experience, coming up with a good small-scale example to the Grover search is not easy. Most of them look tautological because, as you say, typically building an oracle already uses the knowledge of the solution.

To combat these bias, imagine a really large and difficult classical computation that gives a yes/no answer. For instance, given a bitstring the computation determines whether the integer corresponding to this bitstring is prime or not (just an example). You can always turn a classical circuit that does this computation into an analogous quantum circuit. This will be your oracle.

Now, if you are given a list of $10^6$ numbers and need to find a unique prime number among them, classicaly you need to check each number and run the classical oracle about $10^6$ times. If you can run Grover on that scale, you'd only need to execute the quantum oracle $\sim10^3$ times.

$\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.