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
1
vote
0answers
37 views

Grover's algorithm for 3SAT problem gives erroneous results

I'm writing a code in python with qiskit that implements Grover's algorithm to solve the 3-SAT problem, but when I run it it doesn't give the correct annswer. I've checked the circuit with the ...
1
vote
1answer
56 views

Grover diffusion operator for a 3 qubit system

I want to make a three qubit system that marks the states where the last qubit is 0. I have made an oracle function but when I try to run the reflection the amplitudes are only higher than the others ...
4
votes
1answer
50 views

Logical Explanation behind second reflection in Grover's algorithm

Logically, what does the second reflection in Grover's algorithm do? I currently don't have a lot of background in linear algebra so I'm failing to understand what exactly its purpose is and what it ...
2
votes
1answer
27 views

Negating amplitude in amplitude amplification when second qubit is 0 not working

I have experimented a bit with Grover's Algorithm, and I wanted to search for the states $|00\rangle$ and $|10\rangle$. I tried making a Quantum Circuit, which looks like the one below, but measuring ...
4
votes
3answers
402 views

Nielsen and Chuang, Exercise 6.5: How to simulate oracle for n+1 qubits using one oracle gate for n qubits and one extra qubit?

In Chapter 6 of "Quantum Computation and Quantum Information" textbook by Nielsen and Chuang, Exercise 6.5 p.255: We have an oracle gate $O$ for $n$ qubit ($2^n=N$ searching items), and we would ...
2
votes
2answers
115 views

Nielsen and Chuang, Exercise 6.12: How to simulate the specific Hamiltonian in the search algorithm by the Oracle gates?

In Chapter 6 of "Quantum Computation and Quantum Information" Textbook by Nielsen and Chuang, Exercise 6.12: Exercise 6.12: (Alternative Hamiltonian for quantum search) Suppose: $$H=|x\rangle\...
5
votes
1answer
62 views

Why, in Grover's algorithm, $H^{\otimes n}(2|0\rangle\! \langle0| - \mathcal{I})H^{\otimes n}=2|\psi\rangle \!\langle\psi| - \mathcal{I}$?

I've been working through Grovers algorithm. I've read many times that $*^1H^{\otimes n}(2|0\rangle \langle0| - \mathcal{I})H^{\otimes n}$ is equivalent to $*^22|\psi\rangle \langle\psi| - \mathcal{I}...
3
votes
2answers
38 views

How many iterations does Grover’s search need to find one out of $M$ marked items?

How many iterations are needed in Grover’s quantum search for finding one out of M marked items in a database containing N items (for 1 < M < N/2)? I would have thought we just reduce the size ...
2
votes
0answers
41 views

Grover's search for solving TSP

Consider the modified version of the Traveling Salesman Problem where you are searching for a path of length lass than some $k$. We can solve this problem using Grover's search where we encode each ...
1
vote
0answers
36 views

In Grover, how to implement oracle and amplification using Qiskit?

I found some examples of implementing the oracle when the marked state is $|000\rangle$. But how can we know what gate we should use inside of the oracle? Besides, for the part implementation, the ...
-1
votes
2answers
77 views

How do you pass input to a circuit? [closed]

I've implemented Grover's search algorithm in qiskit, and I'd like to pass in an input to run through the circuit. How is that done?
2
votes
1answer
66 views

What is the difference between Grover's and Amplitude Amplification?

I'm confused about what precisely is the difference between Grover's Algorithm and Amplitude Amplification. I've heard some sources say they are different algorithms and others say they are the same ...
4
votes
2answers
109 views

Significance of the term “diffusion” in Grover's diffusion operator

In the context of Grover's algorithm, the diffusion operator is defined as $U_s = 2|s\rangle \langle s| - I$ with $|s\rangle\equiv |+\rangle^{\otimes n}$. What is the significance of the term "...
3
votes
2answers
168 views

Probability of observing search string $\omega$ after $r$ iterations

Per Wikipedia, in Grover's algorithm the probability of observing search string $\omega$ after $r$ iterations is: $$\left|\begin{bmatrix}\langle \omega | \omega \rangle &\langle \omega | s \...
4
votes
0answers
66 views

Exact functions of a single-iteration Grover Search Algorithm's operators

I'm doing a practice assignment where I'm asked to identify specific features of the Grover Search Algorithm's second operator (picture in post, further on "$Us$"), which mirrors the system relative ...
2
votes
1answer
80 views

Why can we forget about the ancilla bit in Grover's algorithm?

$\def\braket#1#2{\langle#1|#2\rangle}\def\bra#1{\langle#1|}\def\ket#1{|#1\rangle}$ When using Grover's algorithm to invert a function $f\colon \{0,1\}^m \rightarrow \{0,1\}$, an ancilla bit is used in ...
2
votes
2answers
116 views

In Grover's Algorithm, does the exact solution need to be given to the oracle?

From my understanding, the oracle function in Grover's algorithm is used as a way to check for the desired outcome. I have looked at this example which implements the Exactly-1 3-SAT problem and the ...
2
votes
0answers
50 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
306 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 ...
5
votes
2answers
130 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}$ ...
0
votes
1answer
106 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$?
1
vote
2answers
89 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 ...
4
votes
1answer
161 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
78 views

How does ControlledOnInt in Q# make it Grovers Oracle?

I have an example with 6 qubits for names and 6 for telephones. I encoded their relation like this: ...
1
vote
1answer
43 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 ...
2
votes
2answers
101 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 ...
-4
votes
1answer
94 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 ...
4
votes
2answers
71 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
74 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 ...
4
votes
0answers
68 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
265 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
141 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
4answers
531 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
338 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
1answer
206 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
174 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
121 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
104 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
137 views

Counting in Q#: number of solutions

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

Grover's algorithm returns skewed probability distribution

I wrote an implementation of Grover's algorithm that looks like this: ...
3
votes
1answer
74 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 ...
5
votes
1answer
242 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
122 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{,} $$...
4
votes
1answer
376 views

Grover's algorithm: number of searches required to find a key

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
147 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 ...
1
vote
1answer
143 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
509 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
115 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
198 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 ...
3
votes
1answer
95 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 ...