Questions tagged [grovers-algorithm]
Grover's search algorithm is an algorithm that can perform a search in the order of square root of the input size. This is a provable speed up over the best classical algorithm, which requires a time of order N to perform a search.
395
questions
45
votes
2
answers
9k
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 ...
glS♦
- 24.8k
38
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
32
votes
2
answers
2k
views
Has there been any truly ground breaking advance in quantum algorithms since Grover and Shor?
(Sorry for a somewhat amateurish question)
I studied quantum computing from 2004 to 2007, but I've lost track of the field since then. At the time there was a lot of hype and talk of QC potentially ...
- 675
30
votes
5
answers
4k
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 ...
- 701
24
votes
2
answers
7k
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 ...
- 3,124
20
votes
2
answers
780
views
Can adiabatic quantum computing be faster than Grover's algorithm?
It has been proven that adiabatic quantum computing is equivalent to "standard", or gate-model quantum computing. Adiabatic computing, however, shows promises for optimisation problems, where the ...
18
votes
4
answers
4k
views
What applications does Grover's Search Algorithm have?
Grover's Search algorithm is usually talked about in terms of finding a marked entry in an unsorted database. This is a natural formalism that lets it be applied directly to searching for solutions to ...
- 58k
17
votes
1
answer
4k
views
How can we keep Schrödinger's cat alive?
We know, Schrödinger's cat inside the box is in the equal superposition state of both alive and dead. We can express its state as $$|\text{cat}_\phi\rangle= \frac{|\text{alive}\rangle+e^{i\phi}|\text{...
- 376
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
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
14
votes
4
answers
2k
views
Grover's Algorithm and its relation to complexity classes?
I am getting confused about Grover's algorithm and it's connection to complexity classes.
The Grover's algorithm finds and element $k$ in a database of $N=2^n$ (such that $f(k)=1$) of elements with $$...
13
votes
2
answers
983
views
Can we speed up the Grover's Algorithm by running parallel processes?
In classical computing, we can run the key search (for example AES) by running parallel computing nodes as many as possible.
It is clear that we can run many Grover's algorithms, too.
My question is;...
- 709
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
11
votes
1
answer
1k
views
How is Grover's algorithm used to estimate the mean and median of a set of numbers?
On the Wikipedia page for Grover's algorithm, it is mentioned that:
"Grover's algorithm can also be used for estimating the mean and median of a set of numbers"
So far I only knew how it can be ...
- 17.5k
11
votes
1
answer
861
views
Why is an oracle qubit necessary in Grover's algorithm?
I am a bit confused about the necessity of an oracle qubit in Grover's algorithm.
My question is, does it depend on how you implement your oracle whether you need an oracle qubit or not? Or, it there ...
- 842
11
votes
2
answers
943
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
11
votes
3
answers
2k
views
Implementation of the oracle of Grover's algorithm on IBM Q using three qubits
I am trying to get used to IBM Q by implementing three qubits Grover's algorithm but having difficulty to implement the oracle.
Could you show how to do that or suggest some good resources to get ...
- 842
10
votes
2
answers
4k
views
In Grover's Algorithm, why does the optimal number of iterations involve a floor?
On page 157 of Kaye, Laflamme and Mosca they write that in Grover's algorithm we need to apply Grover's iterate a total of:
$$\Big\lfloor \frac{\pi}{4} \sqrt{N}\Big\rfloor$$
(They actually wrote $\Big\...
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
10
votes
1
answer
1k
views
Preparing a quantum state from a classical probability distribution
Suppose I have a black-box unitary $U_p$ which is described as follows: given a finite probability distribution $p:\{1,\ldots,n\}\rightarrow \mathbb{R}_{\geq0}$, where $\sum_{x=1}^n p(x)=1$, the ...
- 2,008
10
votes
1
answer
633
views
Quantum attack on hash functions
The line of questioning is inspired by the pick one trick in Section 4 of the PDF version of the paper
Quantum Attacks on Classical Proof Systems - The Hardness of Quantum Rewinding (Ambainis et al., ...
- 2,913
9
votes
2
answers
1k
views
Quantum Amplitude Estimation vs Quantum Phase Estimation
Quick question concerning the probability of success after a phase estimation algorithm vs an amplitude estimation algorithm.
Given the calculation on the wikipedia page, the probability of measuring ...
- 1,756
9
votes
1
answer
405
views
Current limits on Grover search space
I was wondering why till date Grover search has been implemented only till 3 qubits (corresponding to size of database = 8). Refer this paper
The reason why I ask is that we have much larger sized ...
- 191
9
votes
1
answer
1k
views
What is the complexity of the quantum phase estimation in Grover's algorithm?
Suppose we are using GA (Grover's algorithm) such that we are given it has 2 or more solutions. The search space is of size $N$. We all know Grover's algorithm has, at worst, a time complexity ...
- 336
8
votes
4
answers
2k
views
Grover algorithm for a database search: where is the quantum advantage?
I have been trying to understand what could be the advantage of using Grover algorithm for searching in an arbitrary unordered database D(key, value) with N values instead of a classical search.
I ...
- 183
8
votes
3
answers
728
views
In the adiabatic version of Grover's algorithm, how is the Hamiltonian constructed?
X-posted on physics.stackexchange
In quantum computation, there is a famous algorithm to search a marked item in an unstructured database called Grover's algorithm. It achieves a quadratic speedup ...
8
votes
1
answer
114
views
Correspondence between the Topological model and Quantum Circuit model
For example, given the $R$ & $F$ gates and Toric codes for a given problem, how to convert this code into the conventional circuit model and vice versa.
From the literature developed, it seems ...
user5438
7
votes
4
answers
1k
views
Nielsen and Chuang, Exercise 6.5: How to simulate oracle for n+1 qubits using one oracle gate for n qubits and one extra qubit?
In Chapter 6 of "Quantum Computation and Quantum Information" textbook by Nielsen and Chuang, Exercise 6.5 p.255:
We have an oracle gate $O$ for $n$ qubit ($2^n=N$ searching items),
and we would ...
- 160
7
votes
2
answers
656
views
Significance of the term "diffusion" in Grover's diffusion operator
In the context of Grover's algorithm, the diffusion operator is defined as $U_s = 2|s\rangle \langle s| - I$ with $|s\rangle\equiv |+\rangle^{\otimes n}$. What is the significance of the term "...
- 17.5k
7
votes
1
answer
792
views
How did Lov Grover think up his search algorithm? How might one have discovered it themselves?
There are two related but distinct parts to my question and I'm happy to hear perspectives on either:
Any historical details, testimonies, papers that shed insight into what Lov Grover was working on ...
- 805
7
votes
1
answer
458
views
Grover's diffusion on subset of input space
Is it possible to run grover's diffusion step on a subset of the possible input space?
By this, I mean is it possible to do the diffusion process with a state space isn't in a total superposition of ...
7
votes
1
answer
2k
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 ...
user4961
7
votes
1
answer
1k
views
Proof of the optimality of Grover's algorithm
I am currently working on the proof of Grover's algorithm, which states that the runtime is optimal.
In Nielsen they say, the idea is to check whether $D_k$ is restricted and does not grow faster than ...
- 658
7
votes
1
answer
288
views
How significant are the variants of Grover's Algorithm?
I found a paper by Grover titled "How significant are the known collision and element distinctness quantum algorithms?", in which he expressed criticism to several famous algorithms, including ...
- 173
7
votes
1
answer
131
views
Is it possible to perform search with $O(\sqrt{N})$ copies of a "resource" state rather than an oracle?
Suppose that we wish to find $x$ s.t. $f(x) = 1$. Instead of having access to an oracle like $U_f: |i\rangle \mapsto (-1)^{f(i)}|i\rangle$ or $U_f: |i\rangle|z\rangle \mapsto |i\rangle|z\oplus f(i)\...
- 805
7
votes
2
answers
1k
views
In amplitude amplification, how are the amplitudes of qubits changed?
I am relatively new to quantum computing and I feel like I don't fully understand the power of quantum computing due to a lack of understanding of how amplitude amplification works.
What is ...
- 133
7
votes
1
answer
293
views
What is meant by "perfect state transfer"?
In discussions on many quantum algorithms especially related to quantum walks, I have seen the term "perfect state transfer" used to describe some property apparently related to the ...
- 12.1k
7
votes
0
answers
311
views
Solving linear system $Ax=b$ with exponential speed-up via binary optimization?
The main disadvantage of HHL algorithm for solving $A|x\rangle = |b\rangle$ is that exponential speed-up is reached only in case we are interested in value $\langle x|M|x\rangle$, where $M$ is a ...
- 14.1k
6
votes
3
answers
1k
views
XOR gate for n control qubits in qiskit
I am currently creating a blackbox for a grover search algorithm to solve the graph colouring problem with qiskit. One of my search criteria is that one node can only have one color. Therefore, with ...
- 71
6
votes
1
answer
894
views
Can anyone provide me with an example of the for Grover's algorithm on one qubit?
I'm having trouble understanding Grover's Algorithm, so I'd like to start with the case with 1 qubit. But I don't see anyone build it for 1 qubit, only 2 is the minimum. Is it because that's ...
- 526
6
votes
2
answers
878
views
How to implement Grover's diffusion operator when starting with a W state?
In the general form of Grover's algorithm, we start with the uniform superposition of n qubits. Now, suppose instead that we start with a generic state, for example ...
- 548
6
votes
3
answers
473
views
Why is the application of an oracle function not a measurement?
Why is the application of an oracle function not a measurement, causing the collapse of the system? How can you know the state of the system (the input of the oracle function) without measurement?
6
votes
1
answer
948
views
How to create the oracle matrix in Grover's algorithm?
I'm trying to implement Grover's algorithm in pyQuil, but I'm having trouble creating the oracle matrix given the function $f$, where $f(x)=1$ if $x=w$ and $f(x)=0$ otherwise. In most of the ...
- 61
6
votes
1
answer
715
views
Does Grover's algorithm always give the correct answer with 100% certainty for two-qubit states?
In the Qiskit tutorial on Grover's algorithm it is stated that with a 2 qubit algorithm the chance of measuring the "right" state is already 100%.
But I thought that the algorithm would ...
- 165
6
votes
1
answer
1k
views
Second reflection in the Grover's algorithm
When interpreted geometrically, the second phase of the Grover's algorithm which corresponds to inversion about the mean is interpreted as reflection over the original state.
Can you explain ...
- 471
6
votes
2
answers
184
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
6
votes
1
answer
112
views
Why, in Grover's algorithm, $H^{\otimes n}(2|0\rangle\! \langle0| - \mathcal{I})H^{\otimes n}=2|\psi\rangle \!\langle\psi| - \mathcal{I}$?
I've been working through Grovers algorithm. I've read many times that $*^1H^{\otimes n}(2|0\rangle \langle0| - \mathcal{I})H^{\otimes n}$ is equivalent to $*^22|\psi\rangle \langle\psi| - \mathcal{I}...
- 133
6
votes
1
answer
652
views
Implementation of Grover's Algorithm (minimum spanning tree)
I am trying to solve a minimum spanning tree problem using Grover's Algorithm. To accomplish this I would need to search a list for the minimum weight or edge for each point, for example:
Given the ...
6
votes
1
answer
121
views
How to obtain arbitrary distribution in quantum database
I was working on the Grover's algorithm and the most common example is for a unitary distribution in a quantum database, for example:
$|\psi\rangle = \frac{1}{2}|00\rangle + \frac{1}{2}|01\rangle + \...
- 1,049
6
votes
1
answer
446
views
Are applications with only polynomial speedup worth chasing after? (since error correction adds a heavy overhead)
A number of ML algorithms have demonstrated to have polynomial speed-up:
But this (I'm assuming) is without error correcting qubits. How practical are algorithms that only exhibit polynomial speed-up ...
- 1,129