Linked Questions
15 questions linked to/from How is the oracle in Grover's search algorithm implemented?
37
votes
4
answers
14k
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
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 ...
- 610
15
votes
3
answers
4k
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
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 ...
- 241
10
votes
3
answers
826
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,099
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. ...
- 657
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
585
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
198
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,709
6
votes
2
answers
173
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
335
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
3
votes
1
answer
97
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
1
answer
124
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 ...
1
vote
0
answers
192
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 ...
- 133
2
votes
1
answer
71
views
In Grover's algorithm for database search, how are non-queried fields handled?
I've read a lot about the Grover algorithm, and even got beyond the point of understanding the "magic" beyond the oracle function.
What is yet unclear to me is, given an oracle function ...
- 21