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

Oracle with multiple solutions, Grover's Algorithm- Qiskit

Using qiskit, I want to build an oracle with multiple solutions. I am planning to use 10qubits. I don't know if i'm doing it right but where it goes: ...
0
votes
1answer
34 views

Trying to understand Grover's Algorithm

I'd like to start with saying sorry if my question makes no sense as I'm a physics student, but only in third year. I've discovered Grover's algorithm, but what I'm not sure of is if it could be used ...
2
votes
2answers
242 views

What is the circuit for grover's algorithm if N is not a power of 2?

From the literature it seems that grover's algorithm works if $N$ is not a power of $2$. For instance, https://en.wikipedia.org/wiki/Grover%27s_algorithm and https://arxiv.org/abs/quant-ph/0005055 I ...
3
votes
1answer
72 views

Can quantum search be performed without phase estimation?

In the quantum search algorithm with a known number of answers $M$ out of a search space of size $N$, it seems that the algorithm works pretty well (though not with pinpoint accuracy) for a fairly ...
0
votes
1answer
56 views

Applying Hadamard gate to $\sqrt{3/4}|0\rangle + \sqrt{1/4}|1\rangle$

[I am just transferring this from Stack Overflow. It might need editing.] ———— [The reader can skip to “It all sounds fine…”, before the spreadsheet representation.] I am trying to figure out quantum ...
-1
votes
1answer
70 views

Negative Probability — Reality vs Description [closed]

I understand that quantum physics supports the concept that the probability of a qubit collapsing into (say) 1, can be negative or positive… and that quantum computing uses this as a feature, adding ...
2
votes
1answer
88 views

Does the input of the quantum counting algorithm have to be a uniform superposition state?

Will the quantum counting algorithm work if the input is not a uniform superposition (even not a superposition of all basis states)? For example, if I use a state such as : $$\frac{1}{4}(2\vert 0000\...
14
votes
1answer
4k views

How can we keep Schrödinger's cat alive?

We know, Schrödinger's cat inside the box is in the equal superposition state of both alive and dead. We can express its state as $$|\text{cat}_\phi\rangle= \frac{|\text{alive}\rangle+e^{i\phi}|\text{...
5
votes
1answer
117 views

BHT algorithm implementation

Summary of Method Amplitude Amplification Summary The BHT algorithm uses amplitude amplification, a nice generalisation of Grover's algorithm, where there is a subset $G\subset X$ of good elements in ...
0
votes
0answers
51 views

How does the amplitude amplification in Grover's algorithm work?

As the question says - how does the amplitude amplification in Grover's algorithm work? I am fine with adding the negative phase on the winning state, but how does one generate the diffuser to ...
2
votes
1answer
67 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
53 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 ...
3
votes
1answer
105 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
63 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
41 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
39 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
115 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 ...
6
votes
0answers
110 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
63 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
128 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 ...
0
votes
1answer
75 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
55 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
52 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 ...
3
votes
1answer
91 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
57 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
19 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
41 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
41 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
135 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
84 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
196 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
125 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
260 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
75 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
54 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
67 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
165 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
48 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
201 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
140 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
199 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
104 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
243 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
52 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
69 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, ...
3
votes
2answers
92 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
71 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
81 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
45 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 ...

1
2 3 4 5