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.

3
votes
1answer
32 views

Reversible crypto systems for use in the Grover's algorithm

I'm working on some papers (here and here) that use the Grover algorithm to crack krypto systems like AES and SHA. I had already asked a first question here. Now, however, a new question has arisen ...
4
votes
1answer
80 views

Prove that the operator $H U_{0^\perp}H$ can be expressed as $2|\psi\rangle\langle\psi|-I$

I'm trying to solve the following problem related to the mathematical explanation of Grover's algorithm. Let $$ \lvert\psi\rangle = \dfrac{1}{\sqrt{N}} \sum_{x=0}^{N-1}{\lvert x \rangle} \,\text{,} $$...
5
votes
0answers
88 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 ...
4
votes
1answer
97 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 ...
3
votes
1answer
76 views

Proof that Grover's operator can be written as $D_N=-H_n R_N H_n$

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: $...
3
votes
1answer
95 views

Grover's algorithm - DES circuit as oracle?

In the literature before me, the quantum oracle of the Grover algorithm is shown as a function, in which a sign change is made possible $|x\rangle\rightarrow(-1)^{f(x)}|x\rangle$. I have read that it ...
5
votes
3answers
172 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 ...
13
votes
3answers
644 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 ...
3
votes
1answer
293 views

Grover's algorithm: number of searches

I would like to start my question with a quote: If an encrypted document and its source can be obtained, it is possible to attempt to find the 56-bit key. An exhaustive search by conventional means ...
2
votes
1answer
44 views

Consequences of Grover's algorithm

I want to look more closely at the consequences of the Grovers algorithm. As is well known, the algorithm provides a quadratic improvement compared to classical search algorithms. Specifically, I ...
4
votes
2answers
61 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,...
0
votes
1answer
79 views

What can be a mini research project based on Grover's algorithm or the Deutsch Jozsa algorithm?

I need to work out a research project on quantum computing as a part of my curriculum. I was wondering how to implement something theoretically with the basic knowledge I have. I have learned about ...
3
votes
2answers
72 views

In what sense do repeated applications of Grover's operator rotate the state closer to the target?

I'm studying the quantum search algorithm on this book: M.A. Nielsen, I.L. Chuang, "Quantum Computation and Quantum Information", Cambridge Univ. Press (2000) [~p. 252]. To sum up we have a state: $...
9
votes
1answer
166 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 ...
3
votes
1answer
62 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 ...
8
votes
1answer
215 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 ...
2
votes
0answers
35 views

N&C quantum circuit for Grover's algorithm

In the chapter about the Grover algorithm, it is suggested that the gate which executes the phase shift is given in the following form: Now I have looked at this gate in detail and come to the ...
4
votes
1answer
61 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
73 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
1answer
77 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]$...
2
votes
1answer
388 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 ...
2
votes
0answers
33 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
111 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 (...
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...\...
2
votes
0answers
104 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 ...
7
votes
1answer
87 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 ...
7
votes
1answer
102 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
2answers
70 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 ...
2
votes
1answer
46 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
79 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
92 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 ...
4
votes
0answers
45 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
126 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 ...
7
votes
1answer
201 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 ...
15
votes
2answers
228 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 ...
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 ...
10
votes
2answers
674 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 ...
8
votes
1answer
143 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., ...
13
votes
2answers
686 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 ...
8
votes
2answers
201 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
128 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 ...
4
votes
1answer
120 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
703 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 ...
12
votes
2answers
890 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 ...
23
votes
3answers
857 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
votes
1answer
219 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
512 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 $$...
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 + \...
6
votes
2answers
248 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\...