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
1 vote
1 answer
33 views

Grover Iteration

I have two questions regarding a search algorithm based on the Grover Iteration. Lets assume I would have a classical database: ...
user avatar
  • 141
2 votes
0 answers
29 views

Mark a state if it is part of another register

I am wondering something, especially about Grover algorithm: imagine I have a quantum register $a$ and a quantum register $b$ of equal length. Then, suppose I apply some algorithms on $a$ s.t. it is ...
user avatar
  • 63
1 vote
2 answers
30 views

Hadamard gate in Grover algorithm

What is the need to apply the Hadamard gate as the first step while designing the diffuser circuit in the implementation of Grover's algorithm? I know what the gate does but I cannot understand what ...
user avatar
0 votes
0 answers
64 views

Grovers algorithm: Diffuser on a state that isn't a linear superposition of all possible states

I've been trying to get Grover's algorithm to work, where part of the qubits have been measured, before Grovers is iterated. I have found a circuit that works, but I don't get why it does. I have ...
user avatar
1 vote
0 answers
13 views

Reflection operator in amplitude amplification for block encoding

I am trying to figure out equation (2.33) here. Given that \begin{gather} U_{\psi_0}|{0^m}\rangle|{0^n}\rangle=\sqrt{p_0}|{0^m}\rangle|{\psi_0}\rangle+\sqrt{1-p_0}|{\perp}\rangle,\\ (\Pi\otimes I_n)|{\...
user avatar
  • 1,478
1 vote
2 answers
68 views

Quantum algorithm to determine the existence of a solution

Consider two vectors $u$, $t$ living in some space (let's say $ℝ^{n}$), and the following (simple) problem: Find a vector $v$ such that $∃a,b\inℝ$, $au+bv=t$ Imagine I want to use Grover to find a ...
user avatar
  • 63
0 votes
0 answers
24 views

Grover search with index register entangled with ancilla

I have a question: when Grover's search is set up with ancilla qubits in an entangled state, does it still work or not? Consider an example with a 4-size search space. Firstly, we use 2 qubits ...
user avatar
1 vote
2 answers
62 views

How do I use the quantum searching algorithm to loop search through a datafile in qiskit?

I have a localhost index.html has a table contains names and address and balances etc... also there is a search bar on the home page to go through the pages, the interesting thing is, there is loooot ...
user avatar
2 votes
1 answer
68 views

Grover's Search Number of iterations for M > 1

In Grover's Search algorithm, how to determine the number of iterations for any $M$ such that $1 < M < N/2$? The calculations given in the Nielsen and Chuang book say that $R \leq \frac{\pi}{4} ...
user avatar
0 votes
1 answer
60 views

Is there a toy oracle to show the feasibility of Grover's algorithm?

Is there any small 'toy' oracle that can show the feasibility of Grover's algorithm for searching (without using the geometric rotation interpretation)? It is confusing that we cannot know the ...
user avatar
6 votes
2 answers
125 views

How do we know a "quantum function call" is worth the same amount of time as a "classical function call?"

In quantum and classical algorithms, we often need to do "function calls." Quantum algorithms such as Grover's algorithm or the Deutsch–Jozsa algorithm can take a fewer number of function ...
user avatar
1 vote
1 answer
49 views

Slight modification of Grover's algorithm

Let $S$ be a set $\{| j ⟩~|~j = 0, 1, · · · ,N − 1\}$ with assuming $⟨j_i|j_j⟩ = δ_{ij}$. Thus, total number of quantum states in $S$ is $N$. Usual Grover’s algorithm is to find a state $|w⟩ \in S$ ...
user avatar
3 votes
1 answer
73 views

Grover's algorithm: Rotation in opposite direction

In Grover's algorithm we have the solution superposition $|\omega\rangle$ and the non-solution superposition $|s'\rangle$ (containing all non-solutions). Furthermore, we rotate our starting equal-...
user avatar
1 vote
0 answers
44 views

Using rotation gates instead of Grover

I have a conceptual question about Grover's algorithm. In the textbook case, we always assume to have an oracle that singles out the correct states by giving them a negative phase. Then, we use phase ...
user avatar
  • 43
1 vote
2 answers
59 views

Implementing the Oracle in Grover

I need your expert opinions/comments on this problem. Suppose I have a database (say 16 entries), such that db[0] = 0.12, db[1] = 0.84, db[2] = 0.55, ..., db[15] = 0.91. I want the oracle to mark ...
user avatar
  • 51
0 votes
1 answer
91 views

Grover's algorithm for 3SAT problem gives unexpected results

Based on SAT problem and Grover's algorithm, I've done some experiments. For the below example, I've received unexpected results: Input: boolean function: ...
user avatar
0 votes
0 answers
52 views

Q# Grover Tutorial Problem

Referring to the Q# tutorial on Grover algorithm in https://docs.microsoft.com/en-us/azure/quantum/tutorial-qdk-grovers-search?tabs=tabid-visualstudio, I replicated the code exactly in Visual Studio ...
user avatar
  • 51
2 votes
1 answer
72 views

Implementing the Quantum Oracle

Suppose I have a simple function $f(x): 1 + x$ and I want to find $x$ such that $f(x) = 5$, for instance, using the Grover search. Am I correct to say that I will need to implement this function $f(x)$...
user avatar
  • 51
7 votes
1 answer
437 views

How did Lov Grover think up his search algorithm? How might one have discovered it themselves?

There are two related but distinct parts to my question and I'm happy to hear perspectives on either: Any historical details, testimonies, papers that shed insight into what Lov Grover was working on ...
user avatar
  • 473
3 votes
0 answers
23 views

Why does QAA need QPE to estimate the probability of the good state?

I have some trouble understanding some aspects of the Quantum Amplification Algorithm (QAA). I am using this reference for the following discussion (section 4). The QAA applies a certain operator $Q :=...
user avatar
  • 483
2 votes
1 answer
66 views

Amplitude amplification with or without ancilla state

I am trying to understand amplitude amplification and I am able to find two formulations (almost identical). (A) No ancilla Usually, and what I do understand quite well, is that you start with the ...
user avatar
  • 483
1 vote
1 answer
47 views

SOlving SAT problem having Boolean And f(x) = x1 and x2 and (not x3) using Grover's algorithm

Solving SAT using Grover's algorithm , if the f(x) = x1 and x2 and (not x3). I have a few questions: is this considered a 3 SAT problem as there are three literals here and one clause? I have seen ...
user avatar
2 votes
0 answers
33 views

Amplifying states using partial information

Assume we have an initial state $(H^{\otimes n}|0\rangle)|0\rangle = \frac{1}{\sqrt{N}}\sum_{i=0}^{N-1}|i\rangle|0\rangle$ in two $n$-qubit registers (let $N=2^n$). Then we feed this state through a ...
user avatar
  • 43
1 vote
1 answer
62 views

Grover search in Quantum Computation and Quantum Information (Nielsen and Chuang)

in Nielsen and Chuang's book in Box 6.1 (page 256 for 10th edition) there is a example of Grover's search algorithm for 3 qubits (2 as search space + 1 for oracle). I am currently trying to implement ...
user avatar
  • 35
0 votes
1 answer
57 views

Using Grover on entangled states

I am trying to implement Grover's algorithm on an entangled state. The idea is that I will have a state $\sum_x\alpha_x|f(x),x\rangle$ and I want to measure the $x$, for which $f(x)=0$. Note that $f$ ...
user avatar
  • 43
2 votes
1 answer
58 views

Accuracy of Grover algorithm is 100% for 2 qubit, 94.5% on 3 qubit and 96.2% for 4 qubit on simulator. Why it decreasing and then again increasing?

The accuracy of Grover's algorithm decreases for 3 qubit then increases for 4 qubit and then again increases for 5-qubit on simulator (qasm simulator) with pi/4(sqrt N) iterations. What is the reason ...
user avatar
2 votes
1 answer
236 views

Oblivious Amplitude Amplification

I've been looking for the OAA paper but I've been unsuccessful in finding it. (so any links will also be helpful) My question is essentially this, given the state: $$\vert 0good \rangle + \vert 1bad \...
user avatar
  • 196
3 votes
1 answer
127 views

Is it possible to recover a marked bitstring from a superposition?

Is it possible to recover a marked bitstring from a superposition? For example, consider the state $$\lvert \psi \rangle = \frac{1}{2}\left(\lvert 00 \rangle \lvert 0 \rangle + \lvert 01 \rangle \...
user avatar
1 vote
2 answers
62 views

Is it possible to run the Grover algorithm under specific condition

The Grover algorithm deals with sorting in an unstructured database and we can build an oracle (target function f) to achieve this. The oracle returns 1 if the element we search is founded otherwise 0....
user avatar
2 votes
0 answers
22 views

Is the execution of a circuit neglectable for large optimization problems?

Assume a large combinatorial optimization problem should be solved (e.g. via Grover) and further assume there is a (near error free) universal quantum computer with a sufficient number of qubits (and ...
user avatar
3 votes
1 answer
42 views

How to verify a matrix-vector product with Grover search?

I am looking at the Ambainis et al. method of verifying whether $AB = C$ in $O(n^{7/4})$ queries, as described in Buhrman and Špalek. They have the following sentence: verify the matrix-vector ...
user avatar
2 votes
0 answers
32 views

Does the diffusion operator change when there are multiple iterations of the Grover cycle?

My question relates to the theoretical application of the diffusion operator in Grover's algorithm. I understand that a single Grover iteration on an equal superposition will change the amplitude of ...
user avatar
4 votes
2 answers
179 views

Phase Oracle in Qiskit Solving Satisfiability Problems using Grover's Algorithm Section

In Qiskit Textbook, there is a section on solving satisfiability problems using Grover's Algorithm. For the 3SAT instance they construct the following phase oracle: Is there any reasoning behind ...
user avatar
  • 441
3 votes
1 answer
144 views

In generals Amplitude Amplification algorithm, the initial state does not need to attain equally superposition?

In the beginning of this paper about amplitude amplification algorithm, the author stated the conventions of amplitude amplification which I quoted the important part for your convenience as follows: ...
user avatar
  • 2,458
1 vote
1 answer
81 views

How to implement *nested* Grover search (in Quirk)?

$\newcommand{\ket}[1]{|#1 \rangle}$ $\newcommand{\bra}[1]{\langle #1 |}$ PS: I suppose this question could also ask "How to implement $2 \ket{s}\bra{s} - I$ for any (identifiable) $\ket{s} \in \...
user avatar
  • 364
3 votes
1 answer
163 views

Qiskit Implementation of Grover's Algorithm to search a list

Suppose I have a list of numbers from 0 to 32, that is $ [0,1,2....31, 32].$ I want to find a number $n$ in this list such that it satisfies a property, say $n$ is prime. How would I translate this to ...
user avatar
2 votes
0 answers
60 views

Understanding Qiskit 0.32 's $\texttt{AmplificationProblem()}$ behaviour

This is related to my previous question. To apply amplitude amplification in Qiskit, one needs to use AmplificationProblem() or ...
user avatar
  • 438
1 vote
2 answers
83 views

Setting the $\texttt{state_preparation}$ for $\texttt{AmplificationProblem()}$ in the scope of Grover's algorithm

I am having trouble setting the state_preparation parameter of AmplificationProblem() from ...
user avatar
  • 438
2 votes
3 answers
129 views

Confusion about the Grover algorithm

Suppose I have a list of items: $(a, b, c, d, e, f, g, h)$. I could encode these letters in $3$ qubits such that $a = \vert 000\rangle, b = \vert 001\rangle, \cdots, h = \vert 111\rangle$. If I'm ...
user avatar
3 votes
1 answer
49 views

Soundness of Grover's search application

I find that some algorithms can be sped up using Grover's search, but I have a question about the soundness of new algorithms. Since Grover's search is a probabilistic method, it has a chance to make ...
user avatar
3 votes
1 answer
106 views

Using Quantum Bit String Comparision inside Grover's algorithm

Intro I am trying to implement a quantum bit string comparator (QBSC) circuit (based on this paper) into a simple Grover's algorithm but I am unfortunately running into issues. The paper has two ...
user avatar
3 votes
1 answer
42 views

Synthesize superposition state using generalized Grover algorithm

I'm following the paper by Grover (L. K. Grover, Phys. Rev. Lett., 85:2000) and trying to synthesize the following superposition state $$|\psi\rangle = \frac{2|00\rangle - 3|01\rangle - 4i|10\rangle + ...
user avatar
0 votes
0 answers
57 views

Qiskit- Building an oracle to test on Qiskit's Grover

I want to build an oracle with multiple state solutions. For example: For n=4 qubits, I want the state solutions to be 1111, 1101, 1110 and 1100. So, as you can see, in all solutions, there are two ...
user avatar
  • 1
1 vote
1 answer
98 views

Why Grover's search return even distribution with half solution

The image below is the result of finding 4 correct answers from 8 candidates using qiskit. The 4 correct answers I set were 000, 001, 010, 011, but the graph shows the probability is incorrect (the ...
user avatar
2 votes
1 answer
156 views

Grover search with multiple solution implementation strategy

I am confused about how to implement a strategy for Grover's search with multiple solutions. My goal is to find all $t$ solutions in $N$ elements. I got this question because I found people used query ...
user avatar
0 votes
0 answers
26 views

Multiple Values Grover's Algorithm Design Circuit

I am currently working on implementing the oracle with multiple solutions, with the equation as follows: $|q\rangle \xrightarrow{\text{oracle}} (-1)^{f(x)}|q\rangle$ where $f(x) \leq \delta $ will ...
user avatar
1 vote
2 answers
119 views

Can Grover's algorithm be used to search in a real database?

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 ...
user avatar
2 votes
2 answers
279 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 ...
user avatar
3 votes
1 answer
80 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 ...
user avatar
0 votes
1 answer
73 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 ...
user avatar

1
2 3 4 5 6