Oracle questions in Grover's Algorithm

  • #1

Main Question or Discussion Point

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=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?
 

Answers and Replies

  • #2
Strilanc
Science Advisor
588
210
> 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 .
 

Related Threads on Oracle questions in Grover's Algorithm

Replies
13
Views
1K
Replies
0
Views
2K
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
919
Replies
11
Views
11K
  • Last Post
Replies
4
Views
1K
Replies
1
Views
2K
Replies
1
Views
2K
Top