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
0
votes
0answers
26 views

Finding minimum with Grover

I am a beginner in quantum computing. I have already computed the sat quantum solver with Grover search and then, I would like to compute the "minimum search" of Dür and Hoyer. My question is: Is it ...
2
votes
0answers
18 views

Quantum circuit CCX optimization for Grover

I am working on a circuit for a Grover problem and during that I am trying to minimize the used QuBits. The problem is shown in the attached image. In this case the circuit is more or less efficient ...
1
vote
1answer
26 views

Construct a orale for XOR

I am trying to construct an oracle which should accept 10 or 01 (i.e. $|1\rangle$ should be returned for these input). In the below picture the oracle is between the barrier and after the barrier we ...
2
votes
2answers
41 views

Need some explanation about a notation in Grover's algorithm

I was reading a wonderful lecture from John wright on Grover's algorithm. In section 2.3, he makes some simplifications : Lastly, we are also going to assume that the data is labeled as $n$-bit ...
-2
votes
0answers
79 views

As part of genomic epidemiology, using 2-Qubit Grover Search Algorithm to track and predict the target state of covid-19 mutation

As part of genomic epidemiology, using my 2-qubit device, I like to apply Grover search algorithm to track and to predict the target state of covid-19 mutation. Specifically, through amplitude ...
1
vote
1answer
46 views

Are $\mathrm{cRz}$ with angle $\pi$ and $\mathrm{cZ}$ equal on the IBM Quantum Experience?

I was trying to implement the 2-qubit Grover algorithm without the auxiliary bit. Before finding the gate symbol for the controlled $\mathrm{Z}$, I worked with the controlled $\mathrm{Rz}$. The gate ...
4
votes
0answers
45 views

Changing qubits coefficients to trigonometric functions in Grover Algorithm

In this paper, in Appendix B.1 (Grover's Search Algorithm and Grover Operator G), it does a change of coefficients, such as what is done for the Bloch Sphere, but for a many qubits system using only ...
3
votes
0answers
59 views

Difficulty in implementing Grover's Algorithm with large number of qubits

It seems IBM offers a 15 qubit quantum computer through their quantum experience program. However, upon a quick search through the literature, the largest implementation of Grover's algorithm I have ...
3
votes
2answers
79 views

Any other quantum algorithms than Jozsa-Deutsch decision algorithm, Grover search algorithm, Shor factorization algorithm?

I have been working on implementing Jozsa-Deutsch decision algorithm, Grover search algorithm, Shor factorization algorithm on my home made 2 qubits device. I am wondering if there are any other ...
1
vote
1answer
28 views

Hadamard/Phase/Hadamard and Inversion about the Mean

I understand the matrix multiplication behind Grover's algorithm, but I'd like to get an intuitive grasp on why sequence of gates Hadamard-Phase-Hadamard does inversion about the mean. Can anyone help?...
2
votes
1answer
52 views

What observable do we measure at the end of a quantum search algorithm?

In the quantum search algorithm below, also known as Grover's algorithm, what observable do we measure at the end of the protocol? That is, in the red box, it says "measure the first $n$ qubits", but ...
1
vote
2answers
86 views

Is it possible to mine bitcoin by implementing Grover's algorithm on a quantum computer

This has been bothering me for a while. Bitcoin mining involves repeatedly changing the nonce (and occasionally the timestamp and Merkle root) in a block header and hashing it repeatedly, until the ...
2
votes
0answers
35 views

Easiest hash function to implement on Qiskit

Trying to build an Oracle circuit for Grover's algorithm that will try to find a desired input in order to get a certain output of a hash function. Was wondering if there were any 4 or 8 bit hash ...
-2
votes
1answer
61 views

Grover’s algorithm [closed]

According to some references (Lectures on Quantum Computation at Carnegie Mellon School of Computer Science) Grover’s algorithm uses only O($\sqrt{N}\ln {N}$) gates. Using this to calculate desired ...
1
vote
1answer
57 views

Controlled NOT gate using multiple control qubits in Q#

I am trying to implement the Grover's search algorithm using Q# and I am not able to implement the oracle (black box) part for the search of state $|1010\rangle$. How to implement the controlled NOT ...
1
vote
0answers
50 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
68 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
54 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
31 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
426 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
128 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
67 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
45 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
57 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
47 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
80 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?
3
votes
1answer
85 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
118 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
178 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
69 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
88 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
131 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
60 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
382 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
185 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
107 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
189 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
95 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
44 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
103 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
114 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
73 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
86 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
74 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
270 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
188 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
607 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
342 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
246 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 ...