# 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.

93 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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 ...
115 views

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 ...
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 ...
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 ...
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 ...
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 ...
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}$ ...
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$?
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 ...
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 ...
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: ...
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 ...
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 ...
94 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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?
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 ...
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 ...
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 ...
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 ...
137 views

### Counting in Q#: number of solutions

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

### Grover's algorithm returns skewed probability distribution

I wrote an implementation of Grover's algorithm that looks like this: ...
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 ...
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 ...
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{,}$$...
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 ...
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 ...
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 ...
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 ...