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
0 answers
50 views

Qiskit GroverOptimizer - How to draw the circuit?

The following codes works, but as a black box. I'd like to draw the circuit that GroverOptimizer uses. How to do? ...
Maurice Clerc's user avatar
2 votes
1 answer
56 views

Quantum Computing and Overhead

Consider Grover's Algorithm, which identifies a specific $N$-bit string from the set of all $N$-bit strings. The string test function only has to be called $2^{\frac{N}{2}}$ times instead of $2^{N-1}$ ...
itere79's user avatar
  • 21
2 votes
0 answers
23 views

Grover search with zero error

Suppose we need to find out whether or not a set of elements $x_1,...,x_n$ contains any marked items.Show that any quantum algorithm that can solve this problem successfully with zero probability ...
Lagrangekmno4's user avatar
1 vote
1 answer
63 views

How write a marking oracle if greater than with Q#?

I'm trying to write a code to find a minimum in a list. I follow this paper : A quantum algorithm for finding the minimum. So I need to write an operator to mark the case $T [j] < T[y]$. My idea is ...
Cyrano's user avatar
  • 13
3 votes
2 answers
320 views

What is the intuition behind uniform Hadamard superposition?

I noticed that in many quantum algorithms, you apply a layer of uniform Hadamard transformation before and after the operations in between. For example, Deutsch-Josza, Simon's, and Grover's search. ...
Ryan Wang's user avatar
  • 247
1 vote
1 answer
63 views

Preparation of Grover’s algorithm: How to implement the oracle $U_f$?

In order to understand Grover’s algorithm, we need to be able to implement $U_f$ from a black box implementing $f$, which we know how to do. Suppose you have this black box as we can find in some ...
NotaChoice's user avatar
1 vote
0 answers
29 views

How to actually solve for the eigenstates in the adiabatic version of Grover's algorithm

The adiabatic version of Grover's algorithm says that the eigenstates of the Hamiltonian $H(t)=(1-\frac{t}{T})H_0+\frac{t}{T}H_m$ (equation 10 in the linked paper) can be used to solve the eigenvalue ...
requiemman's user avatar
1 vote
1 answer
852 views

Why can't Grover's algorithm apparently solve this simple situation?

I'm utilizing Grover's algorithm to solve a straightforward problem. It presents eight options, but only four are correct (the 1's in the S column) $$\begin{array}{c|c|c|c} q_0& q_1\ & q_2\ &...
Hadamard's user avatar
2 votes
1 answer
54 views

Get confused about the implementation of Amplitude Amplifier

I have a circuit $A$, which produces $$A|0^n\rangle _a |00\rangle _b = \phi_0 |00\rangle _b + \phi_1 |01\rangle _b+ \phi_2 |10\rangle _b + \phi_3 |11\rangle _b$$ And only $\phi_0 |00\rangle _b$ is ...
Alexis's user avatar
  • 203
1 vote
0 answers
66 views

Can Amplitude Amplification amplify an unknown state? [duplicate]

If you have for example the basis states $|000\rangle$ and $|xxx\rangle$. The value of the second basis state is unknown, but the amplitude of both states is given. Also the amplitude of the second ...
Manuel's user avatar
  • 45
2 votes
0 answers
34 views

Derivation of energy gap formula for adiabatic Grover algorithm

I am having a difficulty in finding the full derivation for local search energy gap, as described in In the adiabatic version of Grover's algorithm, how is the Hamiltonian constructed?. I looked ...
Paulske's user avatar
  • 457
1 vote
1 answer
88 views

Why doesn´t Grover's Algorithm work for my Qiskit circuit?

I built a circuit in Qiskit with two GHZ states. In the beginning, I created the superposition $\sim\bigg(|0000\rangle+|0101\rangle+|1010\rangle+|1111\rangle\bigg)$ with two $H$s, and two $CNOT$s. Now,...
Manuel's user avatar
  • 45
4 votes
1 answer
85 views

Minimum probability of measuring marked state in Grover's algorithm is 1/8

I recently came across the proposition that for a database containing $N$ elements with $m<\sqrt{N}$ marked elements, applying Grover's algorithm with any $T$ $(0<T<\sqrt{N}-1)$ iterations (...
requiemman's user avatar
1 vote
0 answers
51 views

How to implement Gover's algorithm with unknown number of solutions using qiskit or pennylane?

In general Grover's algorithm has a fixed number of solutions. But in special cases, we can't know the exact number of solutions, even the solutions change over time. So how to construct oracle in ...
Ren-Xin Zhao's user avatar
2 votes
1 answer
71 views

Quantum algorithm for AES?

We all know about Shor's algorithm to attack RSA but what is the state of the art for attacking symetric algorithm such as AES today with quantum computers ? What are the most promising papers on this ...
Duen's user avatar
  • 326
2 votes
1 answer
82 views

Quantum circuit implementation of shift operator in quantum walk

I'm considering discrete-time quantum walk on $2\times2$ grid with periodic quantum walk. In particular focus on shift operator which has the form : \begin{equation} S|i,j\rangle \otimes |x,y\...
Young Kindaichi's user avatar
4 votes
1 answer
99 views

Generalization of optimality of Grover's algorithm for an arbitrary number of marked elements

In the final remark Zalka's paper about the proof of exact optimality of Grover's algorithm for the search problem with a single marked state, we have the following suggestion for future work: "...
Bridi's user avatar
  • 103
1 vote
0 answers
43 views

How are these circuit diagrams in Grover's algorithm understood and why are they designed this way?

As shown in the figure, there are two labelled quantum states 000, 101. why are 3 $Z$-gates placed first in the phase oracle and then 2 controllable $Z$-gates in sequence? What is the logic that makes ...
Ren-Xin Zhao's user avatar
1 vote
0 answers
52 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 ...
j__j's user avatar
  • 11
1 vote
1 answer
116 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$. ...
Ren-Xin Zhao's user avatar
0 votes
0 answers
76 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 ...
Ron Cohen's user avatar
  • 1,184
4 votes
0 answers
128 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 $\...
mavzolej's user avatar
  • 1,901
2 votes
0 answers
44 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 ...
Cuhrazatee's user avatar
1 vote
1 answer
108 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 ...
Syed Shahmir Kazmi's user avatar
2 votes
0 answers
37 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. ...
Syed Shahmir Kazmi's user avatar
1 vote
1 answer
68 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. ...
Syed Shahmir Kazmi's user avatar
3 votes
0 answers
64 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|...
mavzolej's user avatar
  • 1,901
3 votes
1 answer
224 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 ...
Bridi's user avatar
  • 103
2 votes
2 answers
151 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 ...
slithy_tove's user avatar
4 votes
2 answers
224 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 ...
BQPcomplete's user avatar
1 vote
1 answer
88 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 ...
Huy By's user avatar
  • 83
2 votes
1 answer
61 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: ...
Hannah's user avatar
  • 21
2 votes
0 answers
60 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 ...
abirbhav's user avatar
-2 votes
2 answers
70 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 ?
kevin's user avatar
  • 7
1 vote
1 answer
145 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. ...
leonboe1's user avatar
  • 135
-2 votes
1 answer
81 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 ?
lenhhoxung's user avatar
2 votes
0 answers
37 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 ...
user82261's user avatar
  • 181
0 votes
0 answers
45 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 ...
Maurice Clerc's user avatar
1 vote
1 answer
107 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 ...
abirbhav's user avatar
1 vote
1 answer
32 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 ...
abirbhav's user avatar
1 vote
1 answer
93 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 ...
17tmh's user avatar
  • 11
1 vote
1 answer
62 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)...
inq's user avatar
  • 111
0 votes
2 answers
192 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) ...
Maurice Clerc's user avatar
2 votes
1 answer
191 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 ...
Tommaso's user avatar
  • 23
6 votes
1 answer
165 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 ...
Andreas132's user avatar
1 vote
1 answer
105 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}...
Maurice Clerc's user avatar
1 vote
0 answers
89 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-...
Nikita Nemkov's user avatar
2 votes
1 answer
65 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 $...
Maurice Clerc's user avatar
1 vote
1 answer
280 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 ...
Andrew Baker's user avatar
0 votes
0 answers
365 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,...
Hamideh's user avatar
  • 269

1
2 3 4 5
8