Oracle questions in Grover's Algorithm

  • #1
dakshina gandikota
2
0
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
612
229
> 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 .
 

Suggested for: Oracle questions in Grover's Algorithm

Replies
13
Views
1K
Replies
0
Views
2K
  • Last Post
Replies
7
Views
3K
Replies
2
Views
366
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
259
Replies
11
Views
12K
Top