Linked Questions

37 votes
4 answers
12k views

Is there a layman's explanation for why Grover's algorithm works?

This blogpost by Scott Aaronson is a very useful and simple explanation of Shor's algorithm. I'm wondering if there is such an explanation for the second most famous quantum algorithm: Grover's ...
29 votes
5 answers
3k views

What's the point of Grover's algorithm if we have to search the list of elements to build the oracle?

Grover's algorithm is used, among other things, to search an item $\mathbf{y}$ in an unordered list of items $[\mathbf{x}_0, \mathbf{x}_1, ..., \mathbf{x}_{n-1}]$ of length $n$. Even though there are ...
  • 677
36 votes
3 answers
3k views

Can a quantum computer simulate a normal computer?

Similar to the question Could a Turing Machine simulate a quantum computer?: given a 'classical' algorithm, is it always possible to formulate an equivalent algorithm which can be performed on a ...
40 votes
2 answers
7k views

How is the oracle in Grover's search algorithm implemented?

Grover's search algorithm provides a provable quadratic speed-up for unsorted database search. The algorithm is usually expressed by the following quantum circuit: In most representations, a crucial ...
  • 20.8k
31 votes
1 answer
9k views

What exactly is an oracle?

What exactly is an "oracle"? Wikipedia says that an oracle is a "blackbox", but I'm not sure what that means. For example, in the Deutsch–Jozsa algorithm,$\hspace{85px}$,is the oracle just the box ...
15 votes
4 answers
2k views

How is the Grover-Algorithm applied to a database?

Question I want to use the Grover-Algorithm to search an unsorted database for an element $x$. Now the question arises, how do I initialize index and value of the database with the qubits? Example ...
  • 151
24 votes
2 answers
6k views

How does the Grover diffusion operator work and why is it optimal?

In this answer, Grover's algorithm is explained. The explanation indicates that the algorithm relies heavily on the Grover Diffusion Operator, but does not give details on the inner workings of this ...
15 votes
3 answers
3k views

Grover's algorithm: a real life example?

I'm fairly confused about how Grover's algorithm could be used in practice and I'd like to ask help on clarification through an example. Let's assume an $N=8$ element database that contains colors ...
  • 151
10 votes
3 answers
1k views

Does the oracle in Grover's algorithm need to contain information about the entirety of the database?

Grover's algorithm is often described as a way to search a database in $O(\sqrt{N})$ time. For using it we need an oracle gate that represents some function $f$ such that $f^{-1}(1)$ is the answer. ...
  • 647
11 votes
2 answers
810 views

Grover's algorithm: what to input to Oracle?

I am confused about what to input to Oracle in Grover's algorithm. Don't we need to input what we are looking for and where to find what we are looking for to Oracle, in addition to the ...
  • 842
5 votes
1 answer
1k views

How is Grover's operator represented as a rotation matrix?

I have seen that it is possible to represent the Grover iterator as a rotation matrix $G$. My question is, how can you do that exactly? So we say that $|\psi\rangle$ is a superposition of the states ...
user avatar
3 votes
1 answer
1k views

Why does Grover's search invert about the mean?

Let $\vert s\rangle = \frac{1}{\sqrt{N}}\sum_{i=1}^N\vert x_i\rangle$ be an equal superposition over states from which we need to find one solution state $\vert w\rangle$. The phase flip operator in ...
  • 2,405
4 votes
2 answers
482 views

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

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 ...
  • 117
5 votes
1 answer
1k views

How does an oracle function in Grover's algorithm actually work?

I have lately been studying quantum algorithms. I have gone through the Deutsch algorithm and Grover's algorithm. There's always a function in the oracle which somehow 'recognizes' the solution ...
2 votes
4 answers
520 views

Can Grover's algorithm be used to efficiently find elements in unsorted lists?

From my understanding, Grover's algorithm is often misinterpreted as being able to find elements in lists. And when people try to understand the oracle function in terms of this, it leads to confusion....