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.
364
questions
0
votes
0
answers
6
views
An unexpected result of the Implementation of a finding minimum values algorithm using a qRAM
Motivated by the article Quantum algorithm for finding minimum values in a Quantum Random Access Memory, I'm training to implement a simplified version of the proposed algorithm. But the output isn't ...
- 1
0
votes
1
answer
27
views
Please teach the construction law of oracle $U_f$ in Grover’s algorithm
The framework of Grover's algorithm is shown in Figure from Qiskit.
https://learn.qiskit.org/course/ch-algorithms/grovers-algorithm
But I didn't understand the tutorial's construction rules for $U_f$. ...
- 436
0
votes
0
answers
50
views
Using Classiq for Grover Search
I am participating Classiq Bootcamp, First lesson here, and I need to implement Grover Search in a specific result that satisfies few constrains:
The circuit should encompass a minimum of two Grover ...
- 1,144
4
votes
0
answers
99
views
Grover / amplitude amplification with exponentially high success probability
All the references on Grover / Amplitude Amplification (AA) (Mike&Ike, wiki, Lin Lin lecture notes, etc.) give a recipe for preparing the desired state (or amplifying the state) with probability $\...
- 1,810
2
votes
0
answers
35
views
Generic circuit for signature matrix
Consider a set $ A = \{a_0,a_2,\ldots,a_{k-1}\} \subset [N] := \{0,1,\ldots,N-1\}$.
Consider the diagonal matrix
\begin{equation}
R := I - 2 \sum_{a\in A} |a\rangle\langle a|,
\end{equation}
which is ...
- 591
1
vote
1
answer
51
views
How to implement non-unitary operator in qiskit?
I am trying to make a operator for S-Box for AES. The matrix is non-unitary. When I use Operator command for declaring it as a function. It gives error, the matrix is non-unitary. Thus, the qiskit ...
1
vote
0
answers
17
views
How to calculate number of qubits required for Grover Algorithm while constructing it's oracle and diffuser for any Specific Algorithm or Hash?
I am reading a paper titled, " (Towards Post-Quantum Secure Symmetric Cryptography:
A Mathematical Perspective)". Here, I am able to understand the gate counts and T-depth calculations. ...
1
vote
1
answer
60
views
How can I derive the very basic formulas used in Grover's algorithm?
I have been studying the Grover's algorithm for quite some time. I have used David McMohan (Quantum Computing Explained), M. Suhail Zubairy (Quantum Mechanics For Beginners) and some research papers. ...
2
votes
0
answers
43
views
Amplitude amplification on each register in a product state
let oracle $U_\psi$ prepare a state $\psi$ with success probability $p$. For simplicity assume that $U$ requires a single ancillary qubit and $\psi$ is itself a single-qubit state:
$$
U_\psi |0\rangle|...
- 1,810
3
votes
1
answer
190
views
On the optimality of Grover's algorithm by constant factors
It is well-known that Grover's algorithm is asymptotically optimal. However, is a better algorithm possible by constant factors? And if so, is it known?
Suppose a fixed number of iterations $r$ and ...
- 31
2
votes
2
answers
78
views
Qubit demands of Grover's Algorithm
I have been puzzling over the fact that Grover's algorithm seems to require an exponential number of ancilla qubits in the input size $n$ in order to function. My reasoning is that at every step of ...
- 123
4
votes
2
answers
203
views
When is it justified to have an oracle in a quantum algorithm?
I've always been confused as to when a quantum algorithm is allowed to have an oracle and what kind of a function the oracle can have. For instance, I know in Hamiltonian simulation algorithms, you ...
- 133
1
vote
1
answer
43
views
Amplitude amplification in Grover algorithm
In "Quantum Computation and Quantum Information", they talk about Grover search. One part of the Grover search is Amplitude amplification:
But i think the red line is not true. Because i do ...
- 83
2
votes
1
answer
49
views
How do I interpret the results of a grover's algorithm graph?
I have recently been using Grover's algorithm to solve sudoku by coding. I am unsure how to interpret the graph produced. Could anyone explain?
I have included a link where you can view the graph: ...
- 21
2
votes
0
answers
39
views
Creating oracle for Grover's algorithm on Caesar cipher
I am trying to replicate this oracle circuit
given in this paper. I am trying to implement a Grover circuit that searches for the key for a known plaintext-ciphertext pair (P,C) = (0xF2,0x14). The ...
- 43
-2
votes
2
answers
60
views
Fourier transform and grover search iteration
For https://library.uoh.edu.iq/admin/ebooks/22831-quantum_computer_science.pdf#page=115 , how is fourier transform being used to determine the number of iteration used in grover search ?
- 7
1
vote
1
answer
69
views
Does Grover work for more than N/2 solutions?
I know that only one iteration is required to find the correct answer for $M=N/4$ solutions with Grover's algorithm. Also, I noticed that Grover never finds a solution when there are $N/2$ solutions.
...
- 135
-2
votes
1
answer
61
views
Oracle in Grover's algorithm [duplicate]
In the Grover's algorithm, the solution is already in the Oracle in order to mark winning state(s).
I just wonder if we already know the solution, why do we need to run a circuit ?
- 109
2
votes
0
answers
23
views
Implementing Adiabatic Grover Search via QAOA
I am reading the paper Grover Search Inspired Alternating Operator Ansatz of Quantum Approximate
Optimization Algorithm for Search Problems. The paper proposes running the Adiabatic Grover Search ...
- 181
0
votes
0
answers
41
views
Grover stop iterations if a condition is met
My Qiskit circuit generates many states and I call "solutions" the ones whose last qubit is |1>.
Their number is unknown in advance.
By using Grover, the main instructions are
...
1
vote
1
answer
88
views
General Grover's search showing wrong results on a particular instance
I am trying to implement a general Grover's search for n qubits searching for m marked elements. I happened to observe that for ...
- 43
1
vote
1
answer
23
views
Implementation of Multi-item Search in Grover's algorithm
I am struggling to understand how exactly a multi-item search in a generic Grover algorithm is implemented. As far as I understand, Grover oracle is specifically designed for each marked item. So it ...
- 43
1
vote
1
answer
58
views
Solving max/min problem for graphs based on Grover
Basis is for this post ist the paper https://arxiv.org/pdf/1902.00445.pdf
I want to do something similar using graph data encoded in quantum states. The circuit structure should look like this (first ...
- 11
1
vote
1
answer
45
views
Amplitude Estimation/Counting - unsatisfiability
The Amplitude Amplification paper states in Theorem 13:
For any positive integers $M$ and $k$, and any Boolean function $f: \{0,1,\ldots,N-1\}\rightarrow\{0,1\}$, the algorithm Count $\left(f,M\right)...
- 111
0
votes
2
answers
86
views
Qiskit, Statevector.from_label
I apply Grover's on an eigh qubits circuit
I just want to amplify the states whose qubits 6 and 7 are |1>
The following test works (the state 11011001 is correctly amplified)
...
2
votes
1
answer
137
views
Find the number of iterations for Amplitude Amplification to get the correct states amplified
I'm trying to use Grover operator in Qiskit (more precisely to perform Amplitude Amplification) but I'm facing some problems. I'm experimenting the Quantum Amplitude Amplification in order to amplify ...
- 23
6
votes
1
answer
115
views
Why is Grover's Algorithm considered to be a Quantum Walk?
I have heard it said that Grover's algorithm is (can be modeled as?) a Quantum Walk. In fact, one reason for their popularity is that QW are used in certain Quantum algorithms. I am trying to ...
- 61
1
vote
1
answer
62
views
Defining an oracle with Qiskit
I have a 8-qubits circuit whose final vector state may be for instance:
$$
\frac{\sqrt{2}}{4} |00010101\rangle+\frac{\sqrt{2}}{4} |00101010\rangle+\frac{\sqrt{2}}{4} |01010110\rangle+\frac{\sqrt{2}}{4}...
1
vote
0
answers
52
views
Which applications of quantum singular value transformation use block-encodings in apriori unknown bases?
Quantum singular value transformation (QSVT) algorithm allows performing polynomial transformations on matrices that are block-encoded in a unitary. Typically, block encoding is assumed to be 'the top-...
- 1,455
2
votes
1
answer
57
views
Grover, Qiskit, general definition of "good state"
Trying to implement Grover under Qiskit I found an example with
good_state = ['110','101']
For a given $n$ it possible to define good_state as "any string of $...
1
vote
1
answer
252
views
Grover's algorithm for complex phases
Grover's algorithm traditionally inputs a phase oracle, $U_\omega$ such that $U_\omega | x \rangle = (-1)^{f(x)} | x \rangle$. The task is to find some $x$ such that $f(x) = 1$. In other words, the ...
- 237
0
votes
0
answers
277
views
Grover's algorithm for max cut problem - Implementation in cirq
I am using the Grover's algorithm for max cut problem using an oracle for the graph described below to check whether it admits a valid 2-coloring.
Here are the edges: (0,3),(0,4),(1,3),(1,4),(2,3),(2,...
- 259
0
votes
1
answer
122
views
Marking a specific quantum state in the oracle function in the Grover's algorithm
I have a simple implementation of Grover's algorithm. As depicted in the results, the oracle function marks the state |111>. How can I change the Oracle function to mark |010>?
...
- 259
2
votes
1
answer
64
views
In Grover's algorithm for database search, how are non-queried fields handled?
I've read a lot about the Grover algorithm, and even got beyond the point of understanding the "magic" beyond the oracle function.
What is yet unclear to me is, given an oracle function ...
- 21
1
vote
0
answers
86
views
Superposition of states, finding the "maximum" one
I designed a circuit (under Anaconda/Jupyter/Qiskit) whose output is a superposition of states of n qubits, q(0), ...q(n-1).
For most of them q(n-1) is |0>, and for a few |1>.
I'd like to ...
0
votes
1
answer
17
views
Is there a polynomial time mapping from 'Grover States' to an orthonormal set of vectors
Grover's algorithm solves the problem of 'Quantum Search' which I will describe below:
Given some oracle, $O_f$, such that $O_f | x \rangle = (-1)^{f(x)} | x \rangle$, find a value of $x$ such that $...
- 237
3
votes
0
answers
39
views
How could one use Grover's algorithm to find pairs of elements?
Imagine we have a set of distinct natural numbers which we divide into two unsorted lists $A$ and $B$. Then, there is a third list $E$ containing pairs of (pairwise) distinct natural numbers. We would ...
- 31
2
votes
1
answer
42
views
The approximation of the time evolution operator U, using Trotter formula, can't hold anymore taking a time step of $\Delta t = \pi$
The problems arises from a consideration written on the book "Quantum computation and quantum information" from Michael A. Nielsen and Isaac L. Chuang on page 259.
In this chapter it's ...
5
votes
2
answers
275
views
Is that possible to simulate Grover's algorithm in quadratic time?
So it is clear that the Grover algorithm offers a quadratic speedup over the classical algorithms; my question is, is it known how to simulate Grover at the most quadratic time? To clarify my question,...
- 338
0
votes
0
answers
38
views
Question about passage in search algorithm chapter, Nielsen-Chuang
I'd like to ask how to get to the final line of equation 6.22, I wonder about the cos and sin functions in particular. (page 257 Nielsen-Chuang)
1
vote
0
answers
32
views
Quantum Amplitude Estimation formulations (Brassard et. al. vs Montanaro)
I am puzzled on the relation between the two approaches (old and new).
(a) The original approach of QAE as described by Brassard et. al. uses two operators to form ${Q}$:
$$
{Q}={A} {S}_0 {A}^{\dagger}...
- 585
0
votes
1
answer
59
views
Grover's algorithm mathematical equation
Suppose there is a single marked state in a data base of $N=2^2$ elements. The grover iteration finds the state with some probabaility. First it adds a negative phase to the single (assumption) marked ...
- 1,410
0
votes
0
answers
68
views
Using Quantum Amplitude Estimation to find integral
I am trying to use the Quantum Amplitude Estimation (QAE) algorithm to find the numerical integral of sin^2(x) in the range ...
- 537
0
votes
1
answer
48
views
'Grover' object has no attribute 'run'
Trying to do an application of Grover's algorithm. I am referring to Qiskit's video on the satisfiability problem however aqua does not exist so I am trying some work arounds.
...
2
votes
0
answers
55
views
Converting from amplitude encoding to basis encoding
The question is inspired from Preparing a quantum state from a classical probability distribution which shows how basis encoding $\frac{1}{\sqrt n}\sum_{x=0}^{n-1}|x\rangle|p(x)\rangle$ may be ...
- 31
0
votes
1
answer
55
views
Qiskit error: "Circuit circuit-91 contains invalid instructions"
I am following the examples given in this qiskit article about the Grover's algorithm.
I am trying to use this method that is given:
...
- 369
7
votes
1
answer
126
views
Is it possible to perform search with $O(\sqrt{N})$ copies of a "resource" state rather than an oracle?
Suppose that we wish to find $x$ s.t. $f(x) = 1$. Instead of having access to an oracle like $U_f: |i\rangle \mapsto (-1)^{f(i)}|i\rangle$ or $U_f: |i\rangle|z\rangle \mapsto |i\rangle|z\oplus f(i)\...
- 665
-1
votes
1
answer
148
views
Grover with 3 qubits [duplicate]
Could someone please post a screenshot or a link for Grover's algorithm with 3 qubits with an oracle tuned for the solution at 101 ?
1
vote
0
answers
35
views
Amplitude amplification when an exact input state is unknown but amplitude is known
Let initial quantum state be $|s\rangle = a|0\rangle|d_a\rangle + b|1\rangle|d_b\rangle$. I know value of amplitude $a$, but I do not know $|d_a\rangle$ and $|d_b\rangle$. These unknown states can be ...
- 31
1
vote
0
answers
16
views
Why is the probaility of finding the winner qubit state decreasing after multiple iterations of Grover's algorithm?
Basically I'm using IBM Quantum to run the following circuit that implements Grover's algortihm by selecting the state |1001> for amplification.
This gives me a probability of finding |1001> of ...
- 21