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.

2
votes
1answer
31 views

Does an oracle use only the eigenstates of the quantum register?

The working of a quantum oracle is still not completely clear to me and I have a few questions: As I understand it, an oracle is a unitary quantum gate and must somehow differentiate between the ...
1
vote
1answer
36 views

Construction of Phase Shift Operation used in Quantum Search

In Chapter 6 of "Quantum Computation and Quantum Information" Textbook by Nielsen and Chuang, Box 6.1 gives a circuit example of Quantum Search Algorithm done on a two-bit sized search space. The ...
2
votes
0answers
41 views

Grover search for basis states with complex coefficents and multiple marked states

I tried to run Grover's search for basis states with complex coefficients, including the marked basis (complex coefficients because the states are obtained from inverse QFT), but it could not amplify ...
6
votes
1answer
205 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 ...
5
votes
1answer
61 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
2answers
194 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 ...
5
votes
3answers
306 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?
2
votes
0answers
55 views

Grover diffusion operator different gates

I have two gates here for the Grover diffusion operator. The first gate is completely understandable for me, so I implemented it myself after submitting some papers that I read. This is the first ...
4
votes
1answer
52 views

Success probability in Grover's algorithm where there are multiple targets

The Grover algorithm allows you to search for multiple elements. Assuming my search space contains four elements, if I only search for one element, I get the one I'm looking for with a probability of ...
4
votes
1answer
112 views

Grover search with single query to $f(x)$ and multiple queries to $f(x) = a$

Assume $f(x)$ is an $n$ bits to $m$ bits function and we want to use Grover's search algorithm to find $x$ such that $f(x) = a$, where $a$ is some $m$-bit predetermined value. When using the ...
0
votes
1answer
74 views

Grover's algorithm and RSA from Nielsen

Nilsen states that one can define a function for the oracle in the Grover algorithm, which is constructed as follows. So there is a number $m$ that consists of $p$ and $q$ (both primes) $m = pq$. Now ...
3
votes
1answer
79 views

Counting in Q#: number of solutions

I have this program derived from Microsoft Quantum Katas for counting (see here): ...
2
votes
1answer
108 views

Grover's algorithm returns skewed probability distribution

I wrote an implementation of Grover's algorithm that looks like this: ...
3
votes
1answer
62 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 ...
3
votes
1answer
184 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 ...
4
votes
1answer
102 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{,} $$...
3
votes
1answer
333 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
67 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 ...
0
votes
1answer
96 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 ...
4
votes
1answer
127 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 ...
3
votes
2answers
84 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: $...
5
votes
1answer
137 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 ...
2
votes
0answers
45 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 ...
5
votes
1answer
116 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
64 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
130 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 ...
7
votes
3answers
320 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
1answer
65 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
124 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
88 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: $...
1
vote
2answers
85 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
94 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
66 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
119 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 ...
5
votes
2answers
88 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
165 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 ...
2
votes
1answer
71 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
141 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 ...
2
votes
2answers
157 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
50 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
175 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
25 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
546 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
178 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., ...
9
votes
2answers
239 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
200 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
107 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
139 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 & ...
21
votes
1answer
771 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 ...