# Oracle questions in Grover's Algorithm

• I
• dakshina gandikota
In summary, Grover's search algorithm is used to find a satisfying answer for a verifiable question, and it works even when the answer is only known through a checker program. The algorithm requires sqrt(N) invocations of the oracle, where N is the number of states given by N=2L and L is the number of qubits. This is because even if a program can easily evaluate a question, it may not be easy to figure out an answer that satisfies it. David Deutsch explains the use of NAND and XOR gates in the diffusion step of the algorithm.

#### dakshina gandikota

https://people.cs.umass.edu/~strubell/doc/quantum_tutorial.pdf
https://www.codeproject.com/Articles/1131573/Grovers-Search-Algorithm-explained

I have these questions:
1. The Oracle "knows" the correct bits in the first invocation itself. So why do sqrt(N) invocations where N is the number of states given by N=2L and L is the number of qubits?
2. Conversely, the intent seems: to increase the amplitude of the answer bits taking into account the noise from the environment during computation. I don't find any other reason to invoke the oracle beyond once. Anyone agree?
In this video

David Deutsch explains the diffusion in the algorithm using NAND and XOR gates. Can anyone explain to me what he means by that?

> The Oracle "knows" the correct bits in the first invocation itself. So why do sqrt(N) invocations where N is the number of states given by N=2L and L is the number of qubits?

Just because you have a computer program that will output True for some value X, that doesn't mean you can easily figure out X or that the writer of the program needed to know X. For example, pick a random ten thousand bit prime P, then write:

Code:
P = ...
def is_period(x):
return pow(2, x, P) == 1

This program is easy to evaluate, but its not so easy to figure out an x that makes it return true.

The power of Grover's algorithm is that it works in these situations where you only have a checker program. Anything you can phrase as a verifiable question, you can use Grover's algorithm to search for a satisfying answer.

The reason you need sqrt(N) evaluations is not so simple. See Section 4 of https://www.cs.cmu.edu/~odonnell/quantum15/lecture11.pdf .