Linked Questions
17 questions linked to/from How is the oracle in Grover's search algorithm implemented?
38
votes
4
answers
15k
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 ...
- 3,124
38
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 ...
- 630
16
votes
3
answers
5k
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 ...
- 161
11
votes
4
answers
2k
views
Grover's algorithm in a nutshell
I am trying to understand Grover's algorithm. I read that this algorithm is able to find an entry in an unsorted list in just $\sqrt N$ steps, and needs only $\log N$ space.
I understand entanglement ...
- 251
10
votes
3
answers
901
views
What is the simplest algorithm to demonstrate intuitively quantum speed-up?
What's the simplest algorithm (like Deutsch's algorithm and Grover's Algorithm) for intuitively demonstrating quantum speed-up? And can this algorithm be explained intuitively?
Ideally this would be ...
- 1,149
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. ...
- 687
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
3
answers
858
views
What is the point of Grover's algorithm, really?
This is a question desguised as a rant. There is a similar question here, What's the point of Grover's algorithm if we have to search the list of elements to build the oracle?, but the answers have ...
- 171
4
votes
1
answer
266
views
How Grover's algorithm retrieves a value from an unsorted list in $O(\sqrt{N})$ steps, if the iterator is consisted of more than $O(1)$ steps?
First, I would like to state that I went through many excellent sources of information (among them - Grover's original paper, several QCSE posts like 1 2, and many more sources) - And yet I couldn't ...
- 1,779
6
votes
2
answers
190
views
How do we know a "quantum function call" is worth the same amount of time as a "classical function call?"
In quantum and classical algorithms, we often need to do "function calls." Quantum algorithms such as Grover's algorithm or the Deutsch–Jozsa algorithm can take a fewer number of function ...
- 359
3
votes
1
answer
386
views
How does the Grover's Algorithm work with a real example? [duplicate]
I am new to this field and I have been baffled by the idea of Oracle for a long time.
I am aware of the procedure, but I am very confused about how we choose the oracle.
Let say we have 4 poker ...
- 181
0
votes
1
answer
170
views
What is the oracle in every quantum algorithm?
There is a machine called oracle which appears in a lot of algorithm of quantum computing, such as Deutsch's algorithm, QFT period-finding. This oracle machine really makes me confused. I've read ...
- 171
1
vote
1
answer
153
views
How is the oracle physically implemented in Deutsch algorithm?
In the Deutsch algorithm, the oracle implementation for the function f is taken as a black box, but physically, how is the oracle implemented? Why can we assume such a black box exists for the ...
3
votes
1
answer
123
views
How can one evaluation of $U_f$ in Grover's algorithm use only one query of $f$?
I am very much new to quantum computation and do not have a background in quantum mechanics, which I believe is at the root of my confusion around Grover's algorithm.
Suppose that we have a search ...
- 33
1
vote
0
answers
206
views
In Grover's oracle, how is the matrix $U_f$ derived for a generic $n$?
Grover's algorithm works by iteration of the operator $$\tag{1}G:=U_S^\perp U_f=H^{\otimes n}U_0^\perp H^{\otimes n}.$$
I know how to write down the matrix for $U_S^\perp$ (the inversion about the ...
- 143