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

How to extend Qiskit Quantum Counting with a Truthtable Oracle?

I'm a newbie in Quantum Computing. So please be indulgent with me. I'm trying to adapt the Qiskit Quantum Counting Example, which defines its oracle in a programmed quantum circuit, to use a ...
3
votes
1answer
67 views

Implementing 3-Qubit Grover Algorithm in Qiskit

The Qiskit tutorial on Grover's Algorithm shows an example of finding two marked solutions out of 8 items, produced by 3 qubits. Using the general diffuser code it provides, however, I realize that ...
0
votes
0answers
43 views

Method to mark only when certain conditions are satisfied in the superposition states of qubits

I am Newbie in Quantum Computing World. While studying on my own, I was curious about one thing, so I asked this question. My question is as follows: When I configure the superposition states of ...
4
votes
1answer
67 views

Final Hamiltonian for Adiabatic Grover

X-posted on physics.stackexchange In quantum computation, there is a famous algorithm to search a marked item in an unstructured database called Grover's algorithm. It achieves a quadratic speedup ...
2
votes
2answers
110 views

Is Grover's algorithm suitable for this search problem?

I wonder if we can utilize Grover's algorithm to solve the following search problem. Leetcode 33. Search in Rotated Sorted Array Example 1: Input: nums = [4,5,6,7,0,1,2], target = 0 Output: true ...
2
votes
1answer
90 views

Grover's algorithm for the real problem of finding the index of an array element

Good day. I am interested in an IMPLEMENTED, not theoretical, example of code for solving the problem of finding the INDEX of an element in an uncorrected array using Grover's Algorithm. The task ...
3
votes
1answer
91 views

How would I theorise a quantum query algorithm in O(1)?

I am currently attempting to solve a problem from Nielsen-Chuang, and I can't seem to figure out how I would do this; I'm trying to implement Grover's algorithm to solve the problem of differentiating ...
2
votes
1answer
188 views

Understanding Grover's Algorithm

For some reason, I'm having difficulty with a seemingly very basic component of Grover's. When reading most explanations, the problem is framed as "consider an unstructured database of N items. ...
1
vote
0answers
45 views

In Grover's oracle, how is the matrix $U_f$ derived for a generic $n$?

Grover's algorithm works by iteration of the operator $$\tag{1}G:=U_S^\perp U_f=H^{\otimes n}U_0^\perp H^{\otimes n}.$$ I know how to write down the matrix for $U_S^\perp$ (the inversion about the ...
4
votes
1answer
58 views

Is there an issue preventing people from scaling Grover's algorithm to larger numbers of qubits?

IBM's quantum experience offers computing up to 15 qubits however through my search of current literature the largest implementation for the algorithm has been with 4 qubits. Is there an issue, ...
2
votes
2answers
62 views

Q-means, QRAM and how it helps algorithmic speedup

I am trying to understand how QRAM will help improve algorithm performance. I am reading a paper on Q-means classification, but I have noticed that some other algorithms (Grovers) seem to have a ...
2
votes
1answer
66 views

How is the Grover iteration realized in an actual quantum circuit?

The number of the Grover's diffuser iterations is proportional to square root of the amount of input data, but how is this realized when building a real quantum circuit? Is it simply by concatenating ...
2
votes
0answers
46 views

In Grover's algorithm, how does the function know what element is to be searched for? [duplicate]

In grover's algorithm the oracle gives the output 1 if the element we want is there, my question is, how does the function know what element is to be searched for or how do you put in the element you ...
1
vote
1answer
73 views

Do states get entangled in Grover’s algorithm?

I am new to QC and right now trying to understand Grover’s algorithm. In Qiskit documents, in the section about solving Sudoku using Grover’s, the first step is explained to be creating three register:...
2
votes
1answer
40 views

Simulating QPE + Grover using Low-Rank Stabilizer Decomposition

I want to simulate a 40-45 Qubit circuit that applies Grover + QPE. I've tried running a simulation on qiskit but can't really go past 18 qubits on my machine. As an alternative, I've been reading ...
3
votes
2answers
108 views

Implementing Grover's oracle with multiple solutions in Qiskit

I want to turn a state $$ |\Psi_1⟩ = \frac{1}{\sqrt{8}}(|000⟩+|001⟩+|010⟩+|011⟩+|100⟩+|101⟩+|110⟩+|111⟩) $$ into $$ |\Psi_2⟩ = \frac{1}{\sqrt{8}}(|000⟩+|001⟩+|010⟩+|011⟩+|100⟩-|101⟩-|110⟩+|111⟩) $$ ...
1
vote
1answer
42 views

Multiply-Controlled X Gate/MCT Gate Implementation

I am currently trying to implement a multi-controlled Toffoli/multi-controlled X gate in Braket, but I am confused as to the general concept of cascaded X gates and other implementations. I've read ...
0
votes
1answer
42 views

How do two H gates act on two entangled qubits?

In this circuit, if the two qubits are initial in state 0, then after the oracle they are entangled and in state: $0.5 * (|00\rangle+|01\rangle+|10\rangle-|11\rangle)$ My question is how do the two H ...
2
votes
1answer
42 views

Where does the time complexity come from when applying Grover's algorithm to AES?

I have just finished multiple readings of Applying Grover’s algorithm to AES: quantum resource estimates, a 2015 paper by Markus Grassl, Brandon Langenberg, Martin Roetteler, and Rainer Steinwandt. ...
2
votes
2answers
89 views

Why does Grover's algorithm rotate around $|000…0\rangle$?

In general I understand Grover's algorithm, how we can think of two separated state spaces, a space $|\alpha\rangle$ with no solutions and a space $|\beta\rangle$ with only solutions, and how the ...
5
votes
1answer
175 views

Quantum Amplitude Estimation vs Quantum Phase Estimation

Quick question concerning the probability of success after a phase estimation algorithm vs an amplitude estimation algorithm. Given the calculation on the wikipedia page, the probability of measuring ...
2
votes
4answers
122 views

Can Grover's algorithm be used to efficiently find elements in unsorted lists?

From my understanding, Grover's algorithm is often misinterpreted as being able to find elements in lists. And when people try to understand the oracle function in terms of this, it leads to confusion....
3
votes
0answers
27 views

Is it possible to nest quantum Markov chain Monte Carlo, mean and minimum algorithms?

Montanaro A. 2015 Quantum speedup of Monte Carlo methods makes the following claim of an algorithm to estimate the mean output $\mu$ of an arbitrary algorithm A, with near-quadratic speedup over ...
3
votes
1answer
47 views

Weird Grover's Algorithm Behavior

I am attempting to use Grover's to find elements in an array that satisfy a comparative query (=, <, >, etc). I am using Qiskit, and am using a qRAM to encode my array. I have experimented with ...
4
votes
1answer
69 views

Are applications with only polynomial speedup worth chasing after? (since error correction adds a heavy overhead)

A number of ML algorithms have demonstrated to have polynomial speed-up: But this (I'm assuming) is without error correcting qubits. How practical are algorithms that only exhibit polynomial speed-up ...
2
votes
3answers
92 views

Grover's algorithm for finding 6/8 states

I'm trying to apply the diffusion operator to this state (normalization factors excluded): $|000\rangle + |001\rangle - |010\rangle - |011\rangle - |100\rangle - |101\rangle - |110\rangle -|111\...
1
vote
1answer
61 views

Grover Algorithm vs Classical Search Algorithms

If Grover algorithm has a better speed than classical search algorithms, would it be an example of where Quantum computers outruns classical computers? Can we use Grover Algorithm in real world ...
1
vote
0answers
41 views

Quantum Search/Count on an unknown superposition state

Question: Search a 'known' element in an 'unknown' quantum database Alternatively, show this is fundamentally impossible (somehow related to the Holevo bound or P < NP?) Related yet different: ...
2
votes
0answers
51 views

A question about Grover's paper “Fixed-Point Quantum Search”

I am reading Grover's paper "Fixed-Point Quantum Search," (arXiv version with a different name) which improves on his earlier quantum research algorithm. However, I'm having difficulty in ...
2
votes
1answer
78 views

Connectivity in Grover's algorithm on real quantum computers

Everytime I execute Grover's search algorithm on IBM real quantum computers I get a wrong answer (it doesn't find the correct winner state) unless I use only 2 qubits. For any higher number of qubits ...
2
votes
1answer
51 views

Is it possible to construct Grover search from Clifford gates only?

In the article Is Quantum Search Pratical the authors emphasized that a complexity of an oracle is often neglected when advantages of Grover search are discussed. In the end, a total complexity of the ...
4
votes
2answers
80 views

How to understand intuitively the Grover diffusion operator?

According to the tutorial https://qiskit.org/textbook/ch-algorithms/grover.html I understand the mathematical principle of diffusion operator: $$ \begin{equation} \begin{split} U_s&=2\left|s\right\...
1
vote
2answers
133 views

Question about a circuit from “Quantum Computing for Computer Scientists”

I am trying to implement a basic quantum computing emulator. In the chapter on Grover's algorithm, we're shown the following circuit: They demonstrate Grover's algorithm with a function $f$ that ...
3
votes
0answers
123 views

How to write the classical algorithm for lights out problem?

I am very new to quantum computing and I have started learning the concepts watching the IBM summerschool videos and trying to solve the IBM quantum challenge problems. One of their problems is ...
2
votes
1answer
34 views

Is Grovers Algorithm Oracle creation a hardware level aspect?

There are numerous questions that asks about practical application demonstration of the Grover algorithm for arrays and databases. However examples are not seen anywhere. While searching for its ...
2
votes
1answer
66 views

How does feedback work in simple Grovers algorithm where $n=4$?

In this example implementation of Grovers Algorithm from the Qiskit Textbook which solves a $2\times 2$ sudoku puzzle: https://qiskit.org/textbook/ch-algorithms/grover.html The circuit iterates twice (...
4
votes
2answers
90 views

Qiskit: How can I modify Grover's algorithm to search for a state that doesn't belong to a basis set?

Let's say I need to find the state $111$ in a "database" that is not the computational basis for a 3-qubits system (because it doesn't contain all of the basis vectors or contains the same ...
1
vote
0answers
59 views

Length / transpilation issues with Grover's algorithm

I would like to discuss the discrepancies between what we see in the simulator versus what we see in the actual running of the code on any IBMQ machine for any qubits at 5 or above. I am doing a final ...
3
votes
3answers
131 views

Is there an explanation for why, to search through an unstructured database, the average number of checks is $\frac{N}{2}$ in classical computation?

I have came across many books online that all explain that if $N$ is large enough, then the average number of checks in $N/2$ but is there a mathematical explanation or derivation for why this is true?...
2
votes
0answers
37 views

How to implement the Maximum or Minimum Searching Algorithm (QUMMSA) circuit in Quirk?

I am Java and Python programmer who started self-learning Quantum Computing a couple of months back. The journey has been thus far very tough. I have been using QisKit and Quirk to learn by in ...
2
votes
1answer
68 views

Is Grover's algorithm only applicable to a pure state?

I've been trying to perform Grover's algorithm on entangled states, e.g. $|00\rangle + |11\rangle$. However, the algorithm apparently doesn't seem to amplify the amplitude of the state $|11\rangle$ ...
2
votes
1answer
29 views

Hybrid lower bound proof Kaye Laflamme Mosca (lemma 9.3.6)

I am confused about one point in the proof on the lower bounds in Kaye, Laflamme Mosca's lemma 9.3.6. Context: $|\psi_T\rangle$ is the final state of the search algorithm that started on the all-zero ...
2
votes
1answer
27 views

Grover's Search applied to Schöning's Algorithm

In this paper by Ambainis, he talks about the applicability of Grover's Search to Schöning's algorithm for solving the 3SAT problem to obtain a runtime of $O(\sqrt{1.329...^n}$. In the original ...
2
votes
0answers
53 views

How to perform computation on an ancilla register in Grover's mean estimation algorithm?

While reading about Grover's mean estimation algorithm, I came across this post on StackExchange. As an undergrad, there are several points I don't quite understand. What is the role of $f(x)$. ...
0
votes
1answer
76 views

Grover's algorithm with matrix_product_state method

I implemented Grover algorithm with matrix_product_state method in qiskit. But I found something strange. I designed the oracle part come out $|1111\rangle$ but, real output was $0011\rangle$. I check ...
1
vote
1answer
92 views

Qiskit BasicAer & Aer

While I'm simulating grover's algorithm, I found that with BasicAer backend it works well but with Aer it is not. What is the difference between ...
2
votes
1answer
53 views

How exactly does Grovers algorithm “crack” symmetric key encryption?

How exactly does Grovers algorithm "crack" symmetric key encryption? I searched around on the internet, and found that it could make the key length effectively half as long, meaning you only ...
2
votes
1answer
29 views

In amplitude amplification, isn't the speedup hindered by the realization of $S_o$?

In brassard et al. Amplitude Amplification work, they define the Q operator as $$\mathbf{Q} = -AS_{o}A^{-1}S_{\chi}$$ where $S_{o}$ is an operator which flips the sign of the $|0 \rangle$ state. Which ...
0
votes
0answers
60 views

Different result between Q# and Qiskit

I'm running a search program with custom initial state. I wrote a program in Q# and one in Qiskit but I get different results even if the code seems to be peforming the same operations. The Q# result ...
0
votes
0answers
29 views

Why does Grover's Diffusion Operator have the word “diffusion” in its name? [duplicate]

Where do I see the diffusion in the Grovers operator? I would think there should be an analogy to classical diffusion but I am not able to see the correspondence.