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
42 views

Different result between Q# and Qiskit

I'm running a search program with custom initial state. I wrote a program in Q# and one in Qiskit but I get different results even if the code seems to be peforming the same operations. The Q# result ...
0
votes
0answers
19 views

Why does Grover's Diffusion Operator have the word “diffusion” in its name? [duplicate]

Where do I see the diffusion in the Grovers operator? I would think there should be an analogy to classical diffusion but I am not able to see the correspondence.
0
votes
1answer
21 views

Grover algorithm in Q#

I have this program derived from Microsoft Quantum Kata for quantum search (Grover algorithm) (see here) ...
0
votes
0answers
88 views

Can one use a quantum circuit as a pathfinding algorithm?

I've been learning about quantum computing, and I noticed that another way to describe the state vector is as a path in a binary tree where each level of tree represents another qubit, each node ...
1
vote
1answer
26 views

Alternative Grover's Diffuse Operator [duplicate]

I was wondering if there is any good references where I could read to understand the construction of Unitary Operators such as the Diffuse Operator in Grover's Algorithm. I am looking to build my own ...
2
votes
1answer
57 views

Lemma 1 in the paper by Brassard, Hoyer, Tapp (1998) on Quantum counting

In the paper by Brassard, Hoyer, Tapp (1998) on Quantum Counting we have the following expression for the state: $$|Y\rangle =\sum_{i\in\mathbb{Z}}x_i|i\rangle |Y_i\rangle.$$ Now we have a quantum ...
-2
votes
1answer
54 views

Grover's 3-qubits tutorial: Why we need the last X gates

I'm following the tutorial in Grover's Algorithm - Example 3 qubits I'm trying to understand the amplitude amplification using the reflection. But I cannot understand if we really need the step 3d (...
0
votes
0answers
16 views

How exactly does a chaotic amplitude amplifier work?

In this link (the bottom presentation) is described an application of Grover's algorithm for 3SAT (and a possible quantum version of Shoning's algorithm for 3SAT). I can find my way through the ...
4
votes
1answer
45 views

What to do when the amount of solutions is not known before applying Grovers Algorithm?

When running Grovers Algorithm one has to know how many solutions there are right? When the number of solutions are not known is then what do you do then?
2
votes
1answer
43 views

How can you decompose Grover's diffusion operator into gates?

I know how Grover's diffusion operator works ($U_s = 2|s\rangle\langle s|-I$) with the inversion around the mean. However, I want to implement it in simpler gates, to use the algorithm. How can I do ...
4
votes
1answer
521 views

Can anyone provide me with an example of the for Grover's algorithm on one qubit?

I'm having trouble understanding Grover's Algorithm, so I'd like to start with the case with 1 qubit. But I don't see anyone build it for 1 qubit, only 2 is the minimum. Is it because that's ...
2
votes
2answers
62 views

Can we use different oracles for each (extended) Grover iteration?

Within the context of Grover's algorithm,  if there are  $N/4$  elements marked instead of just one ($N = 2^n$) , if we run one iteration of Grover's algorithm (one phase inversion and one inversion ...
0
votes
1answer
128 views

Grover search with different diffusion operators

I was reading about the Grover Search algorithm on https://qiskit.org/textbook/ch-algorithms/grover.html#example. I understood the method but I have a few questions. My question regards the two-qubit ...
2
votes
1answer
51 views

Calcuate $\langle x | D | y \rangle$ for arbitrary $x,y \in \{0,1\}^n$

We are considering Grover's algorithm with a search space of size $2^n$ for an arbitrary integer $n$ for arbitrary $n$, and a unique marked element $x_0$. Question: Calculate $\langle x | D | y \...
3
votes
1answer
63 views

Grover's Algorithm on a Database with more than 50% matching entries

The Setup for Grover's Algorithm is the following: Given an oracle $f_O^{\pm}$ representing a Query on a Database with total $N$ entries $N$ of which $k$ are matching. Grover's Algorithm is used to ...
1
vote
2answers
74 views

Does anyone know of Qiskit source code for a Bernstein Vazirani grover's algorithm for N bits? If so please share

I'm just getting started in the space of quantum computing, I've built a 5 qubit program for Bernstein-Vazirani, but am trying to figure out how to go about building an N bit version of Bernstein-...
1
vote
2answers
69 views

Why is the number of solutions given in Qiskit textbook(Quantum Counting Algorithm) as N-M instead of M?

I'm following the Qiskit textbook for Quantum Counting. We have assumed $M$ as the number of states containing solutions throughout the algorithm but at last, $N-M$ has been taken as the solution. ...
5
votes
3answers
439 views

XOR gate for n control qubits in qiskit

I am currently creating a blackbox for a grover search algorithm to solve the graph colouring problem with qiskit. One of my search criteria is that one node can only have one color. Therefore, with ...
1
vote
0answers
34 views

Equality comparator for two qubits each

I'm trying to implement Grover's algorithm. For the oracle I have three nodes which are represented by two qubits for each node. How can I check if the states of two nodes are not equal?
0
votes
1answer
40 views

Grover oracle result: vectors (0,1) & (0,1) => two Hadamards => product of two H results => CZ = (.5, .-5, -.5, -.5)

According to the Grover's algorithm section in the IBM Quantum Experience, if I have two qubits in the "one" state (vectors (0,1) and (0,1)), and I apply a Hadamard gate to each of them, and then ...
3
votes
1answer
47 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 ...
6
votes
1answer
167 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
71 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 ...
0
votes
0answers
39 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$  ...
1
vote
2answers
145 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 ...
1
vote
1answer
41 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
53 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
1answer
64 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
26 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
1answer
161 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 ...
2
votes
1answer
51 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 ...
2
votes
0answers
23 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
34 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 ...
2
votes
0answers
40 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
0answers
32 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 ...
1
vote
2answers
75 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]] : ...
0
votes
1answer
96 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 ...
3
votes
1answer
50 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
34 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
104 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
84 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 ...
6
votes
1answer
79 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
83 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
5answers
153 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
48 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
66 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
3answers
143 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
46 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
68 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
87 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 ...