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.
433 questions
4
votes
0
answers
103
views
Are quadratic speedups viable on photonic architectures given faster logical gate speeds?
The paper Focus beyond quadratic speedups for error-corrected quantum advantage argues that practical quantum advantage within the next two decades is unlikely for superconducting quantum computers ...
- 2,626
1
vote
1
answer
111
views
Why is the fastest quantum time complexity of unstructured search O(sqrt(n))?
Recently, I have watched video on 3Blue1Brown about Grover's algorithm. He give an example that:
To find a secret number in the range from 0 to n−1, you can query a
hidden function that returns “true”...
- 13
3
votes
0
answers
62
views
Does Knowing a bound for the number of solutions allow for any improvement for the Quantum counting algorithm
Recently, I've been looking at the Quantum Counting Algorithm, derived from Grover's algorithm in (https://arxiv.org/pdf/quant-ph/9605034).
Background:
I got especially interested in, if the prime ...
- 366
3
votes
2
answers
280
views
Can't figure out Telescoping Sum Trick in Proof
I was reading the fantastic paper "Grover’s algorithm is an approximation of imaginary-time evolution" (https://arxiv.org/abs/2507.15065) and there's a step in their proof that I can't ...
- 55
2
votes
1
answer
148
views
Grover's algorithm oracle is the classical Householder reflection?
I am learning Grover by reading the lecture notes https://www.cs.cmu.edu/~odonnell/quantum15/lecture04.pdf
It assumes the availability of an oracle gate $O_f$ that provides the following output:
$$
- \...
- 29
0
votes
1
answer
104
views
How to construct an oracle and flips the phase of the solution bit strings?
I am trying to solve the boolean problem (x1 or x2) and (~x1 or ~x2 or x3) using Grover's algorithm. The only measured bits are q0, q1, and q2. This is my oracle:
...
- 3
2
votes
1
answer
107
views
Grover's Algorithm oracle for finding an 8-bit key
I've been trying around different things with Grover's algorithm, and would want to experiment a practical scenario with it by building an oracle to find an 8-bit key.
Very shortly explained, my ...
0
votes
0
answers
62
views
How to make a phase oracle that marks the largest number?
I have a list of strategies each with a corresponding score, I want my oracle to apply the phase shift on the strategy with the largest score value. Without knowing the values beforehand how would I ...
- 21
0
votes
1
answer
184
views
Logical error on Grover's Algorithm protected by Shor's error correction
Hey guys I need some help figuring out why this code will not return the correct keyed result
Basically it is Gorver's Algorithm that is protected by Shor's error correction but when run '000' always ...
- 1
3
votes
1
answer
138
views
How to describe the phase detection operator of the adaptive GROVER algorithm mathematically?
After reading document https://link.springer.com/chapter/10.1007/978-3-319-11857-4_41, I have been curious about the mathematical expression of the phase detection operator. I searched for articles ...
- 610
1
vote
1
answer
136
views
How is Grover's algorithm faster than an apples-to-apples classical version?
Nearly every time I've read about Grover's algorithm, there is an introduction to the equivalent classical algorithm. It goes something like this:
You're searching for a hidden integer that only a ...
- 113
1
vote
2
answers
129
views
Is it possible to entangle two qubits (by means of Grover techniques)?
Given two separate states, I'd like to entangle them to a specific configuration.
Example 1:
$$|+\rangle \otimes |+\rangle \rightarrow \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)$$
Example 2:
$$(a_1|0\...
- 2,173
3
votes
1
answer
464
views
Simplifying the Grover's algorithm
I am learning quantum computing as a beginner and have a question about the Grover’s algorithm (perhaps a naive question). I understand that the key of the Grover’s algorithm is to iteratively use a ...
- 31
3
votes
2
answers
993
views
Grover's algorithm number of iterations
I am trying to understand Grover's algorithm without much of a background in quantum. I believe I understood the main parts to be:
The quantum state is initialized to represent all $n$ possible ...
- 133
-2
votes
1
answer
258
views
Is Grover's Algorithm useless?
If I know what oracle to implement, I know what is the state that I am searching for, so why should I use this algorithm?
I mean, if my quantum control system knows how to implement the oracle, it ...
- 61
0
votes
1
answer
181
views
Grover's algorithm in Qiskit, problems with growing number of qubits
I am building a n-qubit circuit for Grover's algorithm using the material on Qiskit Github as a guide.
https://github.com/Qiskit/textbook/blob/main/notebooks/ch-algorithms/grover.ipynb
In particular I ...
- 49
3
votes
2
answers
282
views
Quantum Monte Carlo and Quadratic Speedup
In classical Monte Carlo, when we want to predict a value for something which has inherent uncertainty, such as predicting a stock value, we use a mathematical model like Geometric Brownian Motion and ...
- 285
3
votes
0
answers
59
views
Amplitude Amplification without access to the Algorithm A: $\mathcal{A}|0\rangle=|\psi\rangle$
I am working on my thesis and I am in a situation where I want to, ideally, use amplitude amplification (as described by Brassard et al. 2000 / arXiv). This is a generalisation of Grover's Search. It ...
0
votes
0
answers
71
views
Coding Oracle for Grover's Algorithm - Qiskit
I am looking to create an oracle that marks the solution states by checking the arrays entries(1 column and many rows) with a threshold. If the value in the array is greater then the threshold the ...
1
vote
1
answer
127
views
Dot product estimation using Amplitude Estimation
To my understanding—from this paper for example (arXiv)—given a state $\frac{1}{\| w\| } \sum_x w(x) |x\rangle$ and given an algorithm that produces $k$ copies of the state $|u\rangle$, we can ...
- 157
1
vote
1
answer
196
views
How to solve "Maximum allowed dimension exceeded" while trying to run Grover's algorithm in IBM backend?
I am trying to run Grover's algorithm on IBM backend. The previous code was running fine but due to some recent changes in qiskit, I had to modify it. But I can't seem to fix this "Maximum ...
- 55
4
votes
2
answers
171
views
How to add the basis state $\vert 0 \rangle$ to an arbitrary uniform superposition state?
There is an unknown uniform superposition state $$\vert \psi \rangle = \frac{1}{\sqrt{N}} (\vert k_1 \rangle + \vert k_2 \rangle + \cdots + \vert k_N \rangle),$$ where $$k_1 \neq k_2 \neq \cdots k_p \...
- 41
1
vote
3
answers
2k
views
Step by step explanation of Grover diffusion operator quantum circuit for 2 qubits
I am a newbie to quantum computing and recently came across Grover's algorithm. I'm now trying to understand its quantum circuit for 2 qubits.
I have understood the oracle which marks the correct ...
- 285
2
votes
1
answer
158
views
How to solve circuit error in qiskit
I am trying to run the grover's algorithm in qiskit using Google collab.
...
- 55
0
votes
0
answers
40
views
Constructing Conditional Phase Shift in Grover's Algorithm and Optimality of Grover's Algorithm for Multiple Solutions
I’m currently working through some questions related to Grover's algorithm and need help with the following:
Conditional Phase Shift Construction using single qubits and two-qubits gate? Also, how ...
3
votes
1
answer
206
views
Doubt on construction of phase oracle in Grover's Algorithm
In the above question from de Wolf's lecture notes, I'm facing difficulties in constructing the oracle. I'm unable to understand how to use the boolean oracle to construct a phase oracle. Any help ...
- 33
1
vote
1
answer
73
views
Grover's algorithm: Build the uniform quantum state over all $n$-bit strings
I am visualising the set $A_1$ as given in the IBM presentation found here: Grover's algorithm. In the presentation, this set is defined by the following expression:
$$A_1 = \{ x \in \Sigma^n: f(x) = ...
1
vote
0
answers
68
views
Amplitude Amplification on subsystem of unknown entangled state
Consider we have a single copy of a state,
\begin{equation}
|\psi\rangle = b |0\rangle_{anc} \otimes |B\rangle_{tar} + g |1\rangle_{anc} \otimes |G\rangle_{tar}
\end{equation}
where the amplitudes $...
- 21
1
vote
1
answer
127
views
Implementation of the Grover's oracle in a real life use case
Imagine a database of DNA fingerprints, each one characteristic of only one person. You
are given a DNA trace and asked to find the person to which it belongs. There is no way
(to my knowledge !) to ...
- 537
0
votes
2
answers
132
views
Boosting amplitude of IMPLY gate
Here is IMPLY gate truth table:
And here is my circuit:
It returned expected output:
Since, 0xx is my solution, how do I boost that amplitude. I know that I ...
3
votes
1
answer
94
views
Why is an exponential scaling chosen in the Grover Algorithm for an unknown amount of solutions?
In "tight bounds on quantum searching" by Boyer et al., an exponential scaling for the upper limit of the interval is presented, that is some number $\lambda^s$. This number is the upper ...
- 33
0
votes
1
answer
265
views
How to program Grover's Operator?
I understand the theory behind Grover's operator but I still am unsure how to code it. I have a quantum circuit with 13 qubits. Could someone please tell me step by step the code to use for Grover's ...
1
vote
1
answer
95
views
Qiskit Grover search with QasmSimulator
I'm working through a Qiskit tutorial on Grover search. Unfortunately it was published in 2023 and the tutorial's version of Qiskit (earlier than v1.00) is now out of date. I tried to rewrite the ...
0
votes
0
answers
57
views
How many times do I have to repeat the oracle + amplitude amplification in Grover's algorithm?
My question is: How many times do I have to repeat the oracle + amplitude amplification in Grover's algorithm?
For further info: I am using 13 qubits and the # of solution states is unknown (may have ...
2
votes
0
answers
116
views
Understanding sources of error in 4-bit Grover's search on IBM QC
This question is similar to some others I've come across, related to why a 4-qubit implementation of Grover's search yields such poor results when run on the IBM QC compared to the 3-qubit case (...
- 121
0
votes
1
answer
99
views
Does an MCZ gate flip the phase of the target qubit if it is in the 0 state?
I am trying to flip the phase of the solution state in an oracle for Grover's algorithm. I am wondering if an MCZ gate will flip the target qubit of |0> if the control qubits are in their correct ...
1
vote
1
answer
194
views
Quantum algorithm for finding minimum $x$ such that $f(x)=1$
I am currently working on a project which includes the comparison of strings in $O(\sqrt{n})$ complexity where $n$ is the length of the string. The reference for this algorithm can be found in ...
1
vote
1
answer
183
views
2
votes
0
answers
81
views
Confusion on the Quantum Minimum Finding Algorithm
I am a new beginner in quantum algorithms. Recently, I was trying to learn the quantum minimum finding algorithm appeared in here. I am struggling to fully understand the operations in the algorithm.
...
- 21
3
votes
1
answer
437
views
Wong's "Introduction to Classical and Quantum Computing" Exercise 7.23
I am currently working my way through "Introduction to Classical and Quantum Computing" by Thomas Wong. I am trying to solve the following problem:
Exercise 7.23. Answer the following ...
- 91
0
votes
1
answer
97
views
Applying cz gate in oracle for Grovers Algorithm
Theoretically say I have a 2 qubit circuit where the solution state is |11>. I was watching a video from qiskit (https://www.youtube.com/watch?v=0RPFWZj7Jm0) on this and in the oracle they only ...
2
votes
0
answers
84
views
Seeking Recommendations on Quantum Attacks
I'm exploring quantum attacks (in the Q1 model) on symmetric structures, including hash functions, block ciphers, modes of operation and stream ciphers with time complexity beyond quadratic speedup. I'...
user29747
3
votes
2
answers
308
views
Why does "Read the Fine Print" say that a quantum computer can "maybe" achieve a modest speedup for optimization problems?
Quantum Machine Learning Algorithms: Read the Fine Print says:
By using a quantum computer,
one could dramatically accelerate the simulation of quantum physics and chemistry (the original application
...
- 2,626
3
votes
1
answer
500
views
Implementing the reflection in Grover's algorithm with $\{\mathtt{CNOT}, H, X\}$
Suppose we have a boolean function $f : \{0, \cdots, N - 1\} \to \{0, 1\}$ and want to determine $x$ such that $f(x) = 1$ given a reduced quantum oracle $V_f$ defined by
$$
V_f | x\rangle := (-1)^{f(x)...
- 53
2
votes
1
answer
263
views
Cannot get a correct quantum count for a sudoku example
I've implemented a quantum counting algorithm for a sudoku example by following
the amplitude estimation algorithm introduced in Mosca's textbook (An Introduction to Quantum Computing, page#172):
...
- 1,532
3
votes
1
answer
162
views
What's the cost of finding $(x,y)$ such that $g(f(x),y)=1$ via Grover?
I have two functions $f:\{0,1\}^n \rightarrow \{0,1\}^m$ and $g: \{0,1\}^m \times \{0,1\}^k\rightarrow \{0,1\}$ and I want to find a point $(x,y)$ such that $g(f(x),y)=1$ (let's assume there is only ...
- 101
2
votes
0
answers
83
views
Grover with randomized oracle
I'm sorry if this is a stupid question. I want to know about the behavior of Grover's algorithm with oracle having a low one-sided probability of error. So if $f(x)=0$ my oracle returns $0$ and if $f(...
- 101
5
votes
0
answers
132
views
Can we beat Grover for derangement problems?
Recall that a derangement of $N$ objects is (isomorphic to) a permutation of $\{1,\cdots, N\}$ that has no fixed point. The probability that a random permutation $f$ is a derangement rapidly reaches $\...
- 16.3k
3
votes
1
answer
220
views
How to perform amplitude amplification when the initial amplitude of aiming state is unknown
Let's say, I want to perform amplitude amplification on the quantum state
$$|s\rangle=\sum_{i=0}^{2^n-1}m_i |i\rangle\,,$$
And the aiming state is $|x\rangle\,.$
Usually, when I perform amplitude ...
- 125
2
votes
1
answer
286
views
Where to find the Grover's algorithm for Qiskit 1.0.2?
Can anyone please provide me with the latest version of qiskit 1.0.2 Grover's algorithm, as the earlier version is throwing an error.
