Skip to main content

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

How to extract key from a Grover's attack?

I have implemented a lightweight cipher on a quantum circuit, Now, by implementing oracle and amplifying I can increase the probability of the marked ciphered state. While there is no mechanism to ...
Syed Shahmir Kazmi's user avatar
3 votes
1 answer
75 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)...
Olly Britton's user avatar
2 votes
1 answer
122 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): ...
taketoshi kinoshita's user avatar
3 votes
1 answer
119 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 ...
ivmihajlin's user avatar
2 votes
0 answers
61 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(...
ivmihajlin's user avatar
5 votes
0 answers
71 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 $\...
Mark Spinelli's user avatar
3 votes
1 answer
120 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 ...
mingo's user avatar
  • 105
0 votes
0 answers
38 views

Proof that if W is the image of a Unitary operator with an $n^O(1)$ size quantum circuit, then $R_W$ has an $n^O(1)$ circuit as well

I have been working on the following problem Suppose $H$ is the Hilbert space of n qubits. Let $W_0$ be the subspace of $H ⊗ H$ with basis $|x_0⟩$, x = 0,...,N −1 where $N = 2^n$. Suppose $U$ is a ...
user145282's user avatar
2 votes
1 answer
146 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.
Ayush Agarwal's user avatar
1 vote
0 answers
50 views

State amplification in Grover when starting with W state

I have two 3-qubit registers, each one is prepared in $W$ state, so my two registers are in state: $$\left|W_3\right\rangle\otimes \left|W_3\right\rangle \ ,$$I use this (6-qubits) diffusion operator ...
user12910's user avatar
  • 451
1 vote
1 answer
92 views

Understanding the diffusion operator in Grover's algorithm

I understand how Grover's algorithm works and its geometrical interpretation. However, I am struggling to understand the implementation of the diffusion operator. Whilst I know what the diffusion ...
aghin's user avatar
  • 129
1 vote
1 answer
89 views

What is wrong with my quantum grover's algorithm?

I am trying to create Grover's algorithm in quantum programming with Qiskit to find the target binary string 010. This is my process : Apply a Hadamard gate to 4 ...
Royal Mail's user avatar
2 votes
1 answer
67 views

Grover search - data representation

I am a mechanical engineer conducting an undergrad research project on quantum computing so fairly new to the whole thing, forgive me if this is a silly question. I understand the basic principles of ...
Max's user avatar
  • 21
1 vote
0 answers
51 views

working of Variable time amplitude amplification (VTAA) compared to amplitude amplification (AA)

I read the paper by Ambianis on variable time amplitude amplification to improve the $\kappa$ (condition number) dependency for the Quantum linear system algorithm by Childs et al.. I can see VTAA ...
Manish Kumar's user avatar
2 votes
0 answers
42 views

Grover meets Anyone - feasibility

Recently, a variety of algorithms have been proposed to combine Grover algorithm with other quantum algorithms. As an example, given a function $f: \{0, 1\}^n\mapsto \{0,1\}$, the Grover meet Simon ...
tigerjack's user avatar
  • 548
0 votes
0 answers
60 views

How to Correctly Measure All Qubits in a Quantum Circuit?

Description: I'm currently working on a project that involves running quantum circuits as a hybrid job on the aws tensor network simulator 'tn1'. Error on the Cloudwatch logs:...
Neel's user avatar
  • 11
1 vote
1 answer
66 views

Complexity of pixel detection in quantum images

In this paper Identification of Desired Pixels in an Image Using Grover's Quantum Search Algorithm it is stated in the abstract that "[...]As has been observed in complexity analysis, Grover's ...
aghin's user avatar
  • 129
1 vote
0 answers
79 views

Memory Issue When Executing Quantum Circuit on AWS Braket with qiskit

Description: I'm currently facing memory-related issues while trying to execute quantum circuits as a hybrid job on the aws tensor network simulator 'tn1' using Qiskit. Despite various attempts to ...
Neel's user avatar
  • 11
1 vote
2 answers
67 views

How to Properly Run a Circuit with Qiskit on AWS Braket, AttributeError: 'AwsDevice' object has no attribute 'configuration' by Current Implementation

Description: I'm currently working on a project that involves running quantum circuits as a hybrid job on the aws tensor network simulator 'tn1'. However, I'm encountering some issues when trying to ...
Neel's user avatar
  • 13
1 vote
1 answer
131 views

Trivial speedup of Grover to log(N) using interference?

I have started to read more about Grover's algorithm to find the binary string $x'$ of $n$ bits for which $f(x=x')=1$ while $f(x\neq x')=0$, out of a total possibility space of $N=2^n$. So it works as ...
Wouter's user avatar
  • 301
0 votes
0 answers
16 views

Diffuser's hadamard logic in equal superposition with negative phases

This is with reference to the question here: How to understand intuitively the Grover diffusion operator? Overall it makes sense on how H^n of the diffuser logic creates the |000..0> from an equal ...
GRK's user avatar
  • 21
2 votes
1 answer
57 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
27 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
73 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
344 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
84 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
1 answer
61 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
883 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
58 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
68 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
38 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
114 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
110 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
70 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
76 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
  • 436
2 votes
1 answer
114 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
100 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
  • 113
1 vote
0 answers
45 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
93 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
190 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
80 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,482
4 votes
0 answers
136 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,971
2 votes
0 answers
45 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
179 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
55 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
93 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
70 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,971
4 votes
1 answer
230 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
  • 113
2 votes
2 answers
312 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
297 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 ...
confusion's user avatar
  • 155

1
2 3 4 5
8