In Grover's Algorithm, does the exact solution need to be given to the oracle?

Question

From my understanding, the oracle function in Grover's algorithm is used as a way to check for the desired outcome.

I have looked at this example which implements the Exactly-1 3-SAT problem and the oracle function follows some rules which only returns True for the correct solution. I have also looked at this which looks for two marked states.

In the second example it looks like the exact solution is given to the oracle which I don't understand as I thought we are supposed to be searching for the solution.

I was wondering if I am misinterpreting this and also how an oracle function can be created if we don't know the rules (like a maze)?

Answer 1

The first example you're looking at is closer to the process of building an oracle for practical applications than the second one. The oracle circuit has to encode the Boolean formula for a specific instance of the problem you're trying to solve, and not the known solutions themselves. When you encode the oracle, you don't know the answer to the problem, but you do know the formula that describes the problem instance and create an oracle based on this knowledge.

The tag grovers-algorithm has a lot of discussions on oracle implementations, since this is probably one of the most confusing topics about the Grover's algorithm - you might want to check them out.

If you're looking for more examples of building oracles for SAT problems given only the SAT formula, you can find them in my tutorial (for a different flavor of SAT problem, but the logic of the steps that have to be done to convert a formula into an oracle is more or less the same for all problems).

Answer 2

Nielsen and Chuang's book made a very good point about the problem to solve using Grover's algorithm: it is easy to recognize a solution but difficult to find one. As a practical example, it is much easier to determine whether a very large number between $10^{10^{10}}$ and $10^{10^{11}}$ is prime or not, than to find a prime number in this range (FYI, the largest known prime has $24,862,048$ digits).