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

Amplitude Amplification for searching $|0\rangle$ in an unknown state

For one known (invertible) function that does: $$f:H^{\otimes 2n}\times H^{\otimes 2n}:|x⟩|0⟩\mapsto|x⟩|y⟩$$ I want to find a similar (invertible) function that does: $$g:H^{\otimes 2n}\times H^{\...
2
votes
1answer
32 views

Combining Amplitude Amplification with HHL

I'm recently learning about how to apply Grover search techniques to other places. An example I've come across is to amplify the probability of measure a $\lvert 1 \rangle$ of the ancilla qubit in HHL ...
-1
votes
0answers
13 views

How to get the $a^{(\gamma)}_L(x)$ in Fixed-Point Quantum Search with an Optimal Number of Queries

Ref: Theodore J. Yoder, Guang Hao Low, and Isaac L. Chuang, Fixed-point QuantumSearch With an Optimal Number of Queries, https://arxiv.org/pdf/1409.3305v2.pdf How to get $a^{(\gamma)}_L(x)=\frac{T_L(x/...
3
votes
1answer
99 views

How to find all marked items by quantum search algorithm?

We know that the Grover algorithm outputs a marked item. Now we want to know the locations of all items. I can't find any paper to solve this problem.
1
vote
1answer
51 views

How does applying Z gate to $|0\rangle$ change the phase of other states during reflection about $|s\rangle$ in Grover algorithm in Qiskit textbook

I am trying to understand the Reflection Gate - Us explained for 2 qubits in the qiskit textbook. In the explanation it is mentioned that first Hadamard gate is applied to change the state $|s\rangle$ ...
3
votes
0answers
35 views

Query complexity on Quantum Pattern Matching of Mateus Algorithm

I am trying to understand the complexity of the Mateus and Omar algorithm for quantum pattern matching, it is clear to me from the pseudocode that the query complexity is $O(\sqrt{N})$, apart from the ...
1
vote
1answer
32 views

Grover's algorithm outputting random/incorrect results

I am sorry if this question is trivial, I am relatively new to QC. Here is my grover's circuit, as you can see it is displaying that it has a 100% probability of measuring 100 however when placed ...
3
votes
1answer
90 views

Understanding Grover’s Oracle for 3-SAT

First of all I'm very new to the quantum computing world so this might seem trivial to you, but it's a hump I was unable to get over for days now. So I'm talking about the version that Qiskit has ...
5
votes
0answers
67 views

Solving linear system $Ax=b$ with exponential speed-up via binary optimization?

The main disadvantage of HHL algorithm for solving $A|x\rangle = |b\rangle$ is that exponential speed-up is reached only in case we are interested in value $\langle x|M|x\rangle$, where $M$ is a ...
2
votes
1answer
54 views

Is there an efficient way to create entangled states using Qiskit?

I am trying to implement Grover's search using Qiskit. And I would like to create entangled states so I could search for the index of a specific value in a list. For example, if the third element in ...
3
votes
1answer
88 views

How does the performance of QAOA and VQE compare to Grover's?

I believe finding the optimal solution is guaranteed for Grover's Algorithm along with quadratic speed-up according to Nielsen and Chuang's book. I wonder if there is any statement regarding QAOA and ...
1
vote
1answer
69 views

In the amplitude amplification algorithm in Nielsen and Chuang's book, why is the error probability $M/N$?

I was able to follow til the yellow-highlighted sentences, which seems to be important to understand. Why M/N is the probability of error? If so 1 - M/N would be the probability of success?
1
vote
1answer
47 views

How to compute the eigenvector of this complex matrix in Grover's algorithm?

We know that SO(3) matrix stands for the proper rotation in 3D space. But when I read this paper, there is a SO(3) matrix stands for the general query matrix of Grover's algorithm in SO(3) form: $$ \...
3
votes
1answer
46 views

How can one evaluation of $U_f$ in Grover's algorithm use only one query of $f$?

I am very much new to quantum computation and do not have a background in quantum mechanics, which I believe is at the root of my confusion around Grover's algorithm. Suppose that we have a search ...
2
votes
1answer
82 views

Does Qiskit Statevector has actual speed up for Grover Search?

From Qiskit document, the Statevector can be used to specify the oracle of Grover Search. After seeing the source code of the operators, it seems a statevector is converted to a rank-1 projector ...
4
votes
0answers
56 views

Is there recent research on experimental implementations of Grover's algorithm with more than 5 qubits?

I could only find experimental work on Grover's algorithm upto 5 qubits here. Is there any more recent research for larger database sizes where Grover's algorithm is employed? Is there any known ...
1
vote
0answers
17 views

Implementing EQP Simon's (removing trivial solution)

I have been studying Brassard and Hoyer's paper, An Exact Quantum Polynomial-Time Algorithm for Simon's Problem (https://arxiv.org/abs/quant-ph/9704027). I have successfully implemented Section 4.1 ...
2
votes
0answers
38 views

Can Grover's algorithm be applied to differential equation solving?

As I understand Grover's algorithm, given the output of a black-box function, can be used to find the corresponding input (or set of inputs if the function is not one-to-one). It is therefore ...
1
vote
0answers
39 views

issues running a 32 qubit grover's algorithm

I have a 32 qubit grover's algoritm however whenever I run it on the simulator that IBM offers it always ouputs a probability of 1 on every single result. Is there a way to run circuits larger then 32 ...
2
votes
3answers
103 views

What is the point of Grover's algorithm, really?

This is a question desguised as a rant. There is a similar question here, What's the point of Grover's algorithm if we have to search the list of elements to build the oracle?, but the answers have ...
2
votes
1answer
77 views

Can I use Grover's algorithm on overlapping sets of qubits?

Let's say I have 3 qubits: $q_1,q_2,q_3$. I want to apply Grover's algorithm on q1,q2, such that q1,q2 $\neq$ 10 and do the same for q2,q3, so that q2,q3 $\neq$ 11. The final possible combinations of ...
4
votes
2answers
187 views

Can I use Grover's algorithm for a function that has multiple arguments which satisfy it?

Let's say we have a function $f(x)$, where $f(011) = 1$, and $f(111) = 1$. Can I still use Grover's algorithm with this function, and receive the result of either $011$, or $111$?
6
votes
1answer
100 views

Does Grover's algorithm always give the correct answer with 100% certainty for two-qubit states?

In the Qiskit tutorial on Grover's algorithm it is stated that with a 2 qubit algorithm the chance of measuring the "right" state is already 100%. But I thought that the algorithm would ...
4
votes
1answer
245 views

How could one implement a circuit using Grover's algorithm to solve a linear system of equations?

Given the following system: $$\begin{bmatrix}0 & 1 & 0\\1 & 1 & 1\\1 & 0 & 1\end{bmatrix} \begin{bmatrix}s_2\\ s_1\\ s_0\end{bmatrix} = \begin{bmatrix}0\\ 0\\ 0\end{bmatrix}$...
5
votes
1answer
67 views

What is meant by “perfect state transfer”?

In discussions on many quantum algorithms especially related to quantum walks, I have seen the term "perfect state transfer" used to describe some property apparently related to the ...
0
votes
1answer
52 views

4Q Grover circuit working in simulator, however producing nonsense in actual quantum computer

I am a noob at quantum computing but I am certain the circuit is correct. I've tried increasing the number of shots, changing the quantum computer. I think it might be a problem with my ccccx gate? I ...
0
votes
0answers
48 views

How to extend Qiskit Quantum Counting with a Truthtable Oracle?

I'm a newbie in Quantum Computing. So please be indulgent with me. I'm trying to adapt the Qiskit Quantum Counting Example, which defines its oracle in a programmed quantum circuit, to use a ...
3
votes
1answer
122 views

Implementing 3-Qubit Grover Algorithm in Qiskit

The Qiskit tutorial on Grover's Algorithm shows an example of finding two marked solutions out of 8 items, produced by 3 qubits. Using the general diffuser code it provides, however, I realize that ...
0
votes
0answers
45 views

Method to mark only when certain conditions are satisfied in the superposition states of qubits

I am Newbie in Quantum Computing World. While studying on my own, I was curious about one thing, so I asked this question. My question is as follows: When I configure the superposition states of ...
7
votes
3answers
184 views

In the adiabatic version of Grover's algorithm, how is the Hamiltonian constructed?

X-posted on physics.stackexchange In quantum computation, there is a famous algorithm to search a marked item in an unstructured database called Grover's algorithm. It achieves a quadratic speedup ...
2
votes
2answers
129 views

Is Grover's algorithm suitable for this search problem?

I wonder if we can utilize Grover's algorithm to solve the following search problem. Leetcode 33. Search in Rotated Sorted Array Example 1: Input: nums = [4,5,6,7,0,1,2], target = 0 Output: true ...
2
votes
1answer
118 views

Grover's algorithm for the real problem of finding the index of an array element

Good day. I am interested in an IMPLEMENTED, not theoretical, example of code for solving the problem of finding the INDEX of an element in an uncorrected array using Grover's Algorithm. The task ...
3
votes
1answer
99 views

How would I theorise a quantum query algorithm in O(1)?

I am currently attempting to solve a problem from Nielsen-Chuang, and I can't seem to figure out how I would do this; I'm trying to implement Grover's algorithm to solve the problem of differentiating ...
3
votes
1answer
230 views

How can Grover's algorithm be implemented when having a string or other data type as input?

For some reason, I'm having difficulty with a seemingly very basic component of Grover's. When reading most explanations, the problem is framed as "consider an unstructured database of N items. ...
1
vote
0answers
50 views

In Grover's oracle, how is the matrix $U_f$ derived for a generic $n$?

Grover's algorithm works by iteration of the operator $$\tag{1}G:=U_S^\perp U_f=H^{\otimes n}U_0^\perp H^{\otimes n}.$$ I know how to write down the matrix for $U_S^\perp$ (the inversion about the ...
4
votes
1answer
66 views

Is there an issue preventing people from scaling Grover's algorithm to larger numbers of qubits?

IBM's quantum experience offers computing up to 15 qubits however through my search of current literature the largest implementation for the algorithm has been with 4 qubits. Is there an issue, ...
2
votes
2answers
69 views

Q-means, QRAM and how it helps algorithmic speedup

I am trying to understand how QRAM will help improve algorithm performance. I am reading a paper on Q-means classification, but I have noticed that some other algorithms (Grovers) seem to have a ...
2
votes
1answer
67 views

How is the Grover iteration realized in an actual quantum circuit?

The number of the Grover's diffuser iterations is proportional to square root of the amount of input data, but how is this realized when building a real quantum circuit? Is it simply by concatenating ...
2
votes
0answers
47 views

In Grover's algorithm, how does the function know what element is to be searched for? [duplicate]

In grover's algorithm the oracle gives the output 1 if the element we want is there, my question is, how does the function know what element is to be searched for or how do you put in the element you ...
1
vote
1answer
76 views

Do states get entangled in Grover’s algorithm?

I am new to QC and right now trying to understand Grover’s algorithm. In Qiskit documents, in the section about solving Sudoku using Grover’s, the first step is explained to be creating three register:...
2
votes
1answer
43 views

Simulating QPE + Grover using Low-Rank Stabilizer Decomposition

I want to simulate a 40-45 Qubit circuit that applies Grover + QPE. I've tried running a simulation on qiskit but can't really go past 18 qubits on my machine. As an alternative, I've been reading ...
3
votes
2answers
184 views

Implementing Grover's oracle with multiple solutions in Qiskit

I want to turn a state $$ |\Psi_1⟩ = \frac{1}{\sqrt{8}}(|000⟩+|001⟩+|010⟩+|011⟩+|100⟩+|101⟩+|110⟩+|111⟩) $$ into $$ |\Psi_2⟩ = \frac{1}{\sqrt{8}}(|000⟩+|001⟩+|010⟩+|011⟩+|100⟩-|101⟩-|110⟩+|111⟩) $$ ...
1
vote
1answer
48 views

Multiply-Controlled X Gate/MCT Gate Implementation

I am currently trying to implement a multi-controlled Toffoli/multi-controlled X gate in Braket, but I am confused as to the general concept of cascaded X gates and other implementations. I've read ...
0
votes
1answer
44 views

How do two H gates act on two entangled qubits?

In this circuit, if the two qubits are initial in state 0, then after the oracle they are entangled and in state: $0.5 * (|00\rangle+|01\rangle+|10\rangle-|11\rangle)$ My question is how do the two H ...
2
votes
1answer
49 views

Where does the time complexity come from when applying Grover's algorithm to AES?

I have just finished multiple readings of Applying Grover’s algorithm to AES: quantum resource estimates, a 2015 paper by Markus Grassl, Brandon Langenberg, Martin Roetteler, and Rainer Steinwandt. ...
2
votes
2answers
126 views

Why does Grover's algorithm reflect along $|000…0\rangle$?

In general I understand Grover's algorithm, how we can think of two separated state spaces, a space $|\alpha\rangle$ with no solutions and a space $|\beta\rangle$ with only solutions, and how the ...
6
votes
2answers
322 views

Quantum Amplitude Estimation vs Quantum Phase Estimation

Quick question concerning the probability of success after a phase estimation algorithm vs an amplitude estimation algorithm. Given the calculation on the wikipedia page, the probability of measuring ...
2
votes
4answers
144 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
30 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
51 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 ...

1
2 3 4 5