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
2
votes
2answers
86 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 ...
2
votes
1answer
44 views

Implementing sum on Boolean with Grover algorithm

We are trying to implement a "sum over 4 booleans = k" in the spirit of Grover search. First, we have 4 qubits, one for each boolean q00, q01, q02, q03,; then 4 ...
3
votes
0answers
27 views

What exactly is the reason why the Abrams - Lloyd algorithm does not allow implementation using unitary gates and ancillary qubits?

In their original paper (last part of the paper), Abrams and Lloyd present a quantum algorithm that could potentially efficiently solve NP complete problems (in linear time). Their algorithm, robust ...
5
votes
1answer
91 views

Preparing a quantum state from a classical probability distribution

Suppose I have a black-box unitary $U_p$ which is described as follows: given a finite probability distribution $p:\{1,\ldots,n\}\rightarrow \mathbb{R}_{\geq0}$, where $\sum_{x=1}^n p(x)=1$, the ...
1
vote
1answer
53 views

Question about Grover algorithm implementation in the Quirk simulator

I want to implement the Grover iteration instead of the multi-control qubit implemented as in this picture: I want to implement them like in this example of five qubits: I mean how can I decompose ...
1
vote
2answers
88 views

How to write decent code for oracle in Qiskit without custom circuit or long truth table?

I am now practising using Qiskit. The example of Grover's algorithm in tutorials suggests using logical expression, truth table or circuit to construct the oracle. In most textbooks on quantum ...
0
votes
0answers
35 views

Question about the Grover-Sysoev algorithm [duplicate]

We consider  a quantum circuit that takes as input two vectors $\vert x \rangle$  and $\vert y \rangle$. The output of this quantum circuit must contain the reflected vector of   $\vert y \rangle$  ...
2
votes
0answers
96 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
1answer
87 views

Exponential speedup of Grover's algorithm?

This question was inspired by the following reference: Reference paper We use the usual notation.  $N = 2^n$ ,  the number of all possible n-bit strings . The oracle  $U_\omega$ can be put in the ...
1
vote
1answer
27 views

Quantum search algorithm with exactly 2 solutions

In Quantum Country's post on the quantum search algorithm, they lay out the search algorithm for the case where there is exactly one solution $| s \rangle$. The key steps are to start in the equal ...
1
vote
1answer
52 views

Can a circuit map $|x,y\rangle$ to the reflection of $|y\rangle$ with respect to $|x\rangle$?

Statement of the problem. I want to consider/design a quantum circuit that takes as input two vectors $\vert x \rangle$  and $\vert y \rangle$. The output of this quantum circuit must contain the ...
2
votes
0answers
37 views

A question about Sysoev's extension of Grover's algorithm

An interesting optimization of Grover's quantum algorithm is discussed in Sysoev's paper: Reference paper  We use the usual notation.  $N = 2^n$ ,  the number of all possible n-bit strings . The ...
2
votes
1answer
46 views

How does the Grover's Algorithm work with a real example? [duplicate]

I am new to this field and I have been baffled by the idea of Oracle for a long time. I am aware of the procedure, but I am very confused about how we choose the oracle. Let say we have 4 poker ...
1
vote
1answer
23 views

Writing Grover's Iterator in different computational phase [duplicate]

This question is from Nielson and Chuang's Quantum Computation and Quantum Information: Here $|\alpha\rangle$ is given by: $$\frac{1}{\sqrt{N-M}}\sum_{x} "|x\rangle $$ where $\sum_{x}" |x\rangle$ is ...
1
vote
2answers
66 views

Result of Grover on Qiskit simulator

I have executed this circuit and I don't understand why the result is $|11\rangle$ ? [q[0], q[1]] : solution register [q[2]] : ...
2
votes
0answers
18 views

How to find a marked item out of $K < N$ marked items when K is unknown?

I'm wondering about time complexities of variants of the searching problem in Grover's Algorithm. I know that using G.A. the time complexity required to find a market item reduces to $O(\sqrt N)$. ...
2
votes
1answer
27 views

How to correctly define $U_\omega$ for Grover's search algorithm

I am working on Grover's algorithm and I am trying to implement the algorithm. I am following the Microsoft quantum katas and I finished and did everything correctly. I am trying to implement the ...
3
votes
5answers
141 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 ...
3
votes
1answer
43 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 ...
20
votes
2answers
417 views

Can adiabatic quantum computing be faster than Grover's algorithm?

It has been proven that adiabatic quantum computing is equivalent to "standard", or gate-model quantum computing. Adiabatic computing, however, shows promises for optimisation problems, where the ...
2
votes
0answers
30 views

How can we apply Quantum Algorithms (Grover's to be specific) to edge coloring problem?

I am a novice in the Quantum Computing field. Recently we were discussing NP-complete problems in Algorithms class and a question arose in my mind which I have stated above, can anyone help me with ...
0
votes
1answer
49 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
2answers
55 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 ...
1
vote
1answer
29 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 ...
5
votes
1answer
693 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 ...
1
vote
2answers
92 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 ...
1
vote
1answer
62 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
47 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
67 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 ...
1
vote
1answer
36 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
61 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 ...
2
votes
0answers
38 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
64 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
71 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
1answer
82 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 ...
1
vote
0answers
57 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 ...
4
votes
1answer
57 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
35 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
0answers
76 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 ...
2
votes
2answers
151 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\...
4
votes
3answers
479 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 ...
5
votes
1answer
72 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
1answer
99 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 ...
3
votes
2answers
55 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 ...
4
votes
1answer
388 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 ...
-1
votes
2answers
90 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?
16
votes
4answers
1k 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
2answers
185 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 \...
3
votes
1answer
100 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
1answer
364 views

How can Grover's operator be represented 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 ...