Oracle questions in Grover's Algorithm

[dakshina gandikota]

Following these links:

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=2^L 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?

 

[Strilanc]

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

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 .