Stack Exchange Network

Stack Exchange network consists of 175 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.

5
votes
1answer
60 views

Durr and Hoyer's: A Quantum Algorithm for Finding the Minimum

I'm trying to understand this algorithm: arXiv:quant-ph/9607014 and I already have a problem on page 1, when they say that initializing the memory and "marking the elements $j$ such that $T[j]<T[y]$...
4
votes
1answer
55 views

Adapting search algorithm to search the minimum in a database in $O(\sqrt{N}\log(N))$ queries

I need some hint on how to adapt grover's algorithm to search the minimum in a database with $N=2^n$ elements in $O(\sqrt{N}\log(N))$ queries with probability of success $\geq 2/3$. I know I can do it ...
2
votes
1answer
64 views

How do you implement the gates for Grover's algorithm for more than 4 elements?

I am currently working intensively on the Grover algorithm and have understood the individual "building blocks" of the algorithm so far. There are also references in the literature to Nielsen, e.g. an ...
5
votes
3answers
99 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 ...
2
votes
0answers
31 views

Grover's algorithm and Battleship solution

I have read that quantum computers are not known to be able to solve NP-complete problems in polynomial time. However, if you consider a game of Battleship with grid size $X, Y$ and represent this by ...
3
votes
2answers
103 views

Finding the second smallest number. Is it achievable in QC?

I have a set of numbers in a superposition state (example: 3,8,1,5) in a quantum register (of 3 qubits). So I try to find the $n^{\text{th}}$ smallest number (...
3
votes
1answer
57 views

Validity of the Grover Iterator

I am interested in showing the validity of the Grover operator. Now there are several ways to show it. One way is with complete induction. It has to be shown that the following relationship applies: $...
1
vote
2answers
79 views

Is there a way to reverse the amplitudes of a quantum system?

For example in grover search algorithm, assuming that the amplified amplitude is $\alpha$ , is it possible to perform this operation : $\alpha |0...\rangle + \beta |1...\rangle \longmapsto \beta|0...\...
8
votes
1answer
84 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 ...
4
votes
2answers
51 views

Is the $|-\rangle$ state the only one that can do the trick for Grover's algorithm?

$\newcommand{\qr}[1]{|#1\rangle}$Grover algorithm's input is a superposition, representing the haystack, and the Bell state $\qr{-}$. The $\qr{-}$ seems utterly important: when I replaced $\qr{-}$ by,...
2
votes
0answers
100 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 ...
4
votes
2answers
62 views

Why is Grover's algorithm not converging monotonically? (Python implementation)

I have tried to implement Grover's algorithm for three qubits in python/numpy and the first two iterations work like a charm but the third one starts to diverge. Is this expected, or is there a bug in ...
4
votes
1answer
48 views

Grover's algorithm oracle matrix

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 ...
2
votes
1answer
44 views

Grover algorithm for more than one element

I am currently working on the Grover algorithm again. In many lectures and documents, as well as books, I noticed that there is always talk of looking for a single element of $N$ elements. Now I read ...
4
votes
1answer
71 views

Grover operator 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 ...
3
votes
2answers
79 views

Grover algorithm phase shift and steps

I am currently working on the Grover algorithm and have a few questions. In the third step of the algorithm, a phase shift is performed on all states, except $|0\rangle$. My question is, why is the ...
5
votes
0answers
43 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 ...
2
votes
3answers
2k views

Is there any (really) quantum procedure that's an algorithm and not a Las Vegas algorithm?

Let me take Grover's algorithm as an example. In most cases, Grover's algorithm is able to yield with a high probability the desired term of the superposition. When the superposition has more than 4 ...
4
votes
2answers
113 views

Grover's algorithm with 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 ...
2
votes
0answers
23 views

Speedup Prange ISD using Grover

In his 2009 paper, Grover vs McElicee, Bernstein proposed to use the Grover's algorithm to obtain a quadratic speedup on the Prange ISD. However, it is not quite clear to me in which part of the ...
2
votes
1answer
321 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 ...
8
votes
1answer
132 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
194 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
121 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 ...
7
votes
1answer
101 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
117 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 & ...
19
votes
1answer
678 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
188 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 ...
12
votes
2answers
780 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 ...
15
votes
2answers
211 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 ...
10
votes
2answers
601 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
62 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
190 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 ...
10
votes
4answers
470 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 $$...
8
votes
1answer
177 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
142 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 ...
13
votes
2answers
526 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 ...
13
votes
2answers
626 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
178 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
239 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\...
12
votes
2answers
941 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 ...
7
votes
2answers
349 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. ...
23
votes
3answers
796 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 ...