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
1
vote
4answers
98 views

Can Grover's algorithm be used to efficiently find elements in unsorted lists?

From my understanding, Grover's algorithm is often misinterpreted as being able to find elements in lists. And when people try to understand the oracle function in terms of this, it leads to confusion....
3
votes
0answers
23 views

Is it possible to nest quantum Markov chain Monte Carlo, mean and minimum algorithms?

Montanaro A. 2015 Quantum speedup of Monte Carlo methods makes the following claim of an algorithm to estimate the mean output $\mu$ of an arbitrary algorithm A, with near-quadratic speedup over ...
3
votes
1answer
38 views

Weird Grover's Algorithm Behavior

I am attempting to use Grover's to find elements in an array that satisfy a comparative query (=, <, >, etc). I am using Qiskit, and am using a qRAM to encode my array. I have experimented with ...
2
votes
0answers
42 views

Are applications with only polynomial speedup worth chasing after? (since error correction adds a heavy overhead)

A number of ML algorithms have demonstrated to have polynomial speed-up: But this (I'm assuming) is without error correcting qubits. How practical are algorithms that only exhibit polynomial speed-up ...
2
votes
3answers
87 views

Grover's algorithm for finding 6/8 states

I'm trying to apply the diffusion operator to this state (normalization factors excluded): $|000\rangle + |001\rangle - |010\rangle - |011\rangle - |100\rangle - |101\rangle - |110\rangle -|111\...
1
vote
1answer
38 views

Grover Algorithm vs Classical Search Algorithms

If Grover algorithm has a better speed than classical search algorithms, would it be an example of where Quantum computers outruns classical computers? Can we use Grover Algorithm in real world ...
1
vote
0answers
35 views

Quantum Search/Count on an unknown superposition state

Question: Search a 'known' element in an 'unknown' quantum database Alternatively, show this is fundamentally impossible (somehow related to the Holevo bound or P < NP?) Related yet different: ...
2
votes
0answers
47 views

A question about Grover's paper “Fixed-Point Quantum Search”

I am reading Grover's paper "Fixed-Point Quantum Search," (arXiv version with a different name) which improves on his earlier quantum research algorithm. However, I'm having difficulty in ...
2
votes
1answer
65 views

Connectivity in Grover's algorithm on real quantum computers

Everytime I execute Grover's search algorithm on IBM real quantum computers I get a wrong answer (it doesn't find the correct winner state) unless I use only 2 qubits. For any higher number of qubits ...
2
votes
1answer
44 views

Is it possible to construct Grover search from Clifford gates only?

In the article Is Quantum Search Pratical the authors emphasized that a complexity of an oracle is often neglected when advantages of Grover search are discussed. In the end, a total complexity of the ...
4
votes
2answers
67 views

How to understand intuitively the Grover diffusion operator?

According to the tutorial https://qiskit.org/textbook/ch-algorithms/grover.html I understand the mathematical principle of diffusion operator: $$ \begin{equation} \begin{split} U_s&=2\left|s\right\...
1
vote
2answers
127 views

Question about a circuit from “Quantum Computing for Computer Scientists”

I am trying to implement a basic quantum computing emulator. In the chapter on Grover's algorithm, we're shown the following circuit: They demonstrate Grover's algorithm with a function $f$ that ...
3
votes
0answers
72 views

How to write the classical algorithm for lights out problem?

I am very new to quantum computing and I have started learning the concepts watching the IBM summerschool videos and trying to solve the IBM quantum challenge problems. One of their problems is ...
2
votes
1answer
33 views

Is Grovers Algorithm Oracle creation a hardware level aspect?

There are numerous questions that asks about practical application demonstration of the Grover algorithm for arrays and databases. However examples are not seen anywhere. While searching for its ...
2
votes
1answer
57 views

How does feedback work in simple Grovers algorithm where $n=4$?

In this example implementation of Grovers Algorithm from the Qiskit Textbook which solves a $2\times 2$ sudoku puzzle: https://qiskit.org/textbook/ch-algorithms/grover.html The circuit iterates twice (...
4
votes
2answers
75 views

Qiskit: How can I modify Grover's algorithm to search for a state that doesn't belong to a basis set?

Let's say I need to find the state $111$ in a "database" that is not the computational basis for a 3-qubits system (because it doesn't contain all of the basis vectors or contains the same ...
1
vote
0answers
58 views

Length / transpilation issues with Grover's algorithm

I would like to discuss the discrepancies between what we see in the simulator versus what we see in the actual running of the code on any IBMQ machine for any qubits at 5 or above. I am doing a final ...
3
votes
3answers
125 views

Is there an explanation for why, to search through an unstructured database, the average number of checks is $\frac{N}{2}$ in classical computation?

I have came across many books online that all explain that if $N$ is large enough, then the average number of checks in $N/2$ but is there a mathematical explanation or derivation for why this is true?...
2
votes
0answers
31 views

How to implement the Maximum or Minimum Searching Algorithm (QUMMSA) circuit in Quirk?

I am Java and Python programmer who started self-learning Quantum Computing a couple of months back. The journey has been thus far very tough. I have been using QisKit and Quirk to learn by in ...
2
votes
1answer
57 views

Is Grover's algorithm only applicable to a pure state?

I've been trying to perform Grover's algorithm on entangled states, e.g. $|00\rangle + |11\rangle$. However, the algorithm apparently doesn't seem to amplify the amplitude of the state $|11\rangle$ ...
2
votes
1answer
27 views

Hybrid lower bound proof Kaye Laflamme Mosca (lemma 9.3.6)

I am confused about one point in the proof on the lower bounds in Kaye, Laflamme Mosca's lemma 9.3.6. Context: $|\psi_T\rangle$ is the final state of the search algorithm that started on the all-zero ...
2
votes
1answer
25 views

Grover's Search applied to Schöning's Algorithm

In this paper by Ambainis, he talks about the applicability of Grover's Search to Schöning's algorithm for solving the 3SAT problem to obtain a runtime of $O(\sqrt{1.329...^n}$. In the original ...
2
votes
0answers
51 views

How to perform computation on an ancilla register in Grover's mean estimation algorithm?

While reading about Grover's mean estimation algorithm, I came across this post on StackExchange. As an undergrad, there are several points I don't quite understand. What is the role of $f(x)$. ...
0
votes
1answer
63 views

Grover's algorithm with matrix_product_state method

I implemented Grover algorithm with matrix_product_state method in qiskit. But I found something strange. I designed the oracle part come out $|1111\rangle$ but, real output was $0011\rangle$. I check ...
1
vote
1answer
52 views

Qiskit BasicAer & Aer

While I'm simulating grover's algorithm, I found that with BasicAer backend it works well but with Aer it is not. What is the difference between ...
2
votes
1answer
33 views

How exactly does Grovers algorithm “crack” symmetric key encryption?

How exactly does Grovers algorithm "crack" symmetric key encryption? I searched around on the internet, and found that it could make the key length effectively half as long, meaning you only ...
2
votes
1answer
22 views

In amplitude amplification, isn't the speedup hindered by the realization of $S_o$?

In brassard et al. Amplitude Amplification work, they define the Q operator as $$\mathbf{Q} = -AS_{o}A^{-1}S_{\chi}$$ where $S_{o}$ is an operator which flips the sign of the $|0 \rangle$ state. Which ...
0
votes
0answers
55 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
26 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
39 views

Grover algorithm in Q#

I have this program derived from Microsoft Quantum Kata for quantum search (Grover algorithm) (see here) ...
0
votes
0answers
146 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
30 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
62 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
76 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
22 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 ...
5
votes
1answer
85 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?
4
votes
1answer
117 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 ...
6
votes
1answer
544 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
74 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 ...
1
vote
1answer
142 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 ...
3
votes
1answer
54 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
74 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
91 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
106 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
519 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
38 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
45 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
55 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 ...
7
votes
1answer
250 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
86 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 ...