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.

Filter by
Sorted by
Tagged with
3
votes
3answers
114 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 ...
7
votes
2answers
313 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\...
2
votes
0answers
21 views

Grover's algorithm for game tree

Scott Aaronson gives the outline of an algorithm to evaluate whether there exists a satisfying assignment for a given game tree. The idea is to use Grover's search recursively, for each level of the ...
5
votes
3answers
325 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?
4
votes
1answer
192 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 ...
9
votes
1answer
326 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 ...
5
votes
2answers
64 views

Are there many practical problems for which Grover's algorithm beats the best heuristic classical algorithm?

It's well known that, given an oracle for a function $f$ from a very large set $S$ (of order $N \gg 1$) to $\{0, 1\}$, Grover's algorithm can find an element of $S$ that maps to 1 with $\sim \sqrt{N}$ ...
2
votes
1answer
124 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 ...
1
vote
2answers
79 views

Is it possible to change the oracle in Grover's search to ponderate probabilities in multiple values search?

If I want to to search 2 values with Grover's algorithm, it outputs the same probability for both that is bigger that the no searched states that have the same lower percent. If I use an oracle ...
0
votes
1answer
95 views

If I have a state $a|0000\rangle+b|0011\rangle$, how do you change it to make $b>a$?

How to increase the amplitude of a specific quantum state? If my quantum circuit produces the state $a|0000\rangle+b|0011\rangle$, how to make $b>a$?
26
votes
3answers
2k 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 ...
1
vote
2answers
81 views

Angular Error associated with Quantum Search Algorithm

Chapter 6.3 of "Quantum Computation and Quantum Information 10th Anniversary Edition" textbook by Nielsen and Chuang talks about using the Quantum Counting Algorithm to find the number of solutions to ...
3
votes
1answer
101 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 ...
1
vote
1answer
43 views

How does ControlledOnInt in Qsharp make it's Grovers Oracle?

I have an example with 6 qubits for names and 6 for telephones. I encoded their relation like this: ...
1
vote
1answer
32 views

Entangling marked qubit with part of the register in Grover's search

Can the marked qubit be associated only with half of the register? I mean if I can ask the oracle if the $2$ low qubits from a $4$ qubit register have a certain value. I ask this to know if I can ...
12
votes
3answers
497 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 ...
4
votes
2answers
64 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 ...
-4
votes
1answer
58 views

What about this metaphor for quantum computing? [closed]

Suppose you have a large collection of N numbered copper coins. However, one of them is nickel but looks exactly the same as the rest. How do you find out which number the nickel coin has? Classical ...
1
vote
1answer
48 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 ...
3
votes
1answer
98 views

Counting in Q#: number of solutions

I have this program derived from Microsoft Quantum Katas for counting (see here): ...
3
votes
0answers
48 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 ...
3
votes
1answer
226 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
1answer
248 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
75 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 ...
8
votes
2answers
268 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 ...
4
votes
1answer
62 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 ...
5
votes
1answer
160 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
117 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 ...
2
votes
1answer
114 views

Grover's algorithm returns skewed probability distribution

I wrote an implementation of Grover's algorithm that looks like this: ...
0
votes
1answer
82 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 ...
2
votes
1answer
73 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 ...
15
votes
4answers
923 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
199 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 ...
3
votes
1answer
64 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
106 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
1answer
185 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
91 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
343 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
87 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
70 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,...
1
vote
1answer
105 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
94 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: $...
10
votes
1answer
223 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
0answers
49 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
67 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
154 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
139 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]$...
3
votes
1answer
605 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 ...
3
votes
2answers
129 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
88 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...\...