Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

3
votes
1answer
117 views

Practical example of Grover's algorithm (in Q#)

Is there any real example for Grover's algorithm but with real database (generated from SQL or file)? I download the Q# development kit & its example, there was one call DatabaseSearchExample ...
7
votes
1answer
101 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., ...
8
votes
2answers
148 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;...
3
votes
1answer
65 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 ...
6
votes
0answers
50 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 ...
4
votes
1answer
83 views

How many qubits does it take to break a 10 characters password?

Let's assume we developed a hashcat-like programs for quantum computer. How many qubits we need to find the correct hash (WPA, MD5,...) from a 10 characters password make from upper, lower & ...
16
votes
1answer
579 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 ...
7
votes
1answer
125 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 ...
11
votes
2answers
438 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 ...
13
votes
2answers
152 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 ...
7
votes
1answer
332 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 ...
5
votes
1answer
54 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 + \...
3
votes
1answer
115 views

Example of Grover's Algorithm applied to a decision problem?

I recently asked this question on Grover's algorithm, and I am still fairly confused about the whole thing. Consider the following snippet from this post (written by DIDIx13) which for convenience I ...
9
votes
4answers
320 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 $$...
7
votes
1answer
130 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 ...
9
votes
1answer
94 views

Grover's algorithm,: the necessity of an oracle qubit.

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 ...
11
votes
2answers
285 views

Grover's algorithm: where is the list?

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 ...
12
votes
2answers
410 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 ...
9
votes
1answer
125 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 ...
6
votes
2answers
199 views

Grover's Algorithm - why do we 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
2answers
497 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 ...
6
votes
2answers
253 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. ...
21
votes
3answers
540 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 ...