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

123 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$  ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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, q] : solution register [q] : ...
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)$. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
36 views

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

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\... 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 ... 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}... 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 ... 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 ... 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 ... 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? 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 ... 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 \...
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 ...