Skip to main content
The 2024 Developer Survey results are live! See the results

# Tag Info

## Hot answers tagged grovers-algorithm

33 votes
Accepted

### How is the oracle in Grover's search algorithm implemented?

The function $f$ is simply an arbitrary boolean function of a bit string: $f\colon \{0,1\}^n \to \{0,1\}$. For applications to breaking cryptography, such as [1], [2], or [3], this is not actually a ‘...
• 1,078
30 votes
Accepted

### Is there a layman's explanation for why Grover's algorithm works?

There is a good explanation by Craig Gidney here (he also has other great content, including a circuit simulator, on his blog). Essentially, Grover's algorithm applies when you have a function which ...
• 11.3k
24 votes
Accepted

• 60.2k
11 votes
Accepted

### How is Grover's algorithm used to estimate the mean and median of a set of numbers?

The idea for estimating the mean is roughly as follows: For any $f(x)$ that gives outputs in the reals, define a rescaled $F(x)$ that gives outputs in the range 0 to 1. We aim to estimate the mean of ...
• 60.2k
11 votes

### How is the Grover-Algorithm applied to a database?

I've been working on this problem as well. As a beginner and a classical programmer (i.e., I don't speak Quantum Mechanics), it is difficult to get an understanding of the concepts without complete ...
• 111
10 votes
Accepted

### Grover's Algorithm and its relation to complexity classes?

Summary There is a theory of complexity of search problems (also known as relation problems). This theory includes classes called FP, FNP, and FBQP which are effectively about solving search problems ...
• 12.2k
10 votes
Accepted

### Significance of the term "diffusion" in Grover's diffusion operator

I had forwarded this question to Dr. Lov Grover and received the following response. I guess inversion about average is a better name for the $\mathrm{W}\mathbb I_0\mathrm{W}$ transformation. When I ...
• 17.7k
10 votes
Accepted

### Nielsen and Chuang, Exercise 6.5: How to simulate oracle for n+1 qubits using one oracle gate for n qubits and one extra qubit?

The simplest solution is to use an ancilla in the $|+\rangle$ state. Swap that ancilla for the oracle's output qubit, conditioned on the control qubit being false, before and after applying the oracle....
• 40.1k
9 votes
Accepted

### Can adiabatic quantum computing be faster than Grover's algorithm?

Good question. For unstructured search, adiabatic quantum computation indeed gives the exact same $\sqrt{N}$ speedup that the standard gate-based Grover's algorithm does, as proven in this important ...
• 2,861
9 votes
Accepted

### What applications does Grover's Search Algorithm have?

Apart from the ones you mentioned, another application of (a modified) Grover's algorithm which I'm aware of is solving the Collision problem in complexity theory, quantum computing and computational ...
• 17.7k
9 votes
Accepted

### Is there any (really) quantum procedure that's an algorithm and not a Las Vegas algorithm?

It sounds like you're looking for algorithms that succeed deterministically with probability 1, instead of probabilistic algorithms that succeed with probability bounded from a 1/2 by a finite amount, ...
8 votes

I find a graphical approach quite good for giving some insight without getting too technical. We need some inputs: we can produce a state $|\psi\rangle$ with non-zero overlap with the 'marked' state $... • 60.2k 8 votes Accepted ### Does the oracle in Grover's algorithm need to contain information about the entirety of the database?$\newcommand{\xtarget}{\boldsymbol{x}_{\operatorname{target}}}\newcommand{\bs}[1]{{\boldsymbol #1}}\newcommand{\on}[1]{{\operatorname{#1}}}$No, it does not. The "oracle" in Grover's algorithm is a ... • 26.1k 8 votes Accepted ### Can we speed up the Grover's Algorithm by running parallel processes? Certainly! Imagine you have$K=2^k$copies of the search oracle$U_S$that you can use. Normally, you'd search by iterating the action $$H^{\otimes n}(\mathbb{I}_n-2|0\rangle\langle 0|^{\otimes n})H^{... • 60.2k 8 votes ### Is there any (really) quantum procedure that's an algorithm and not a Las Vegas algorithm? Although the probability of not getting the desired result decreases exponentially, it is technically not guaranteed that one will ever get the desired measurement. Therefore, we cannot prove that ... • 12.2k 8 votes ### How to create the oracle matrix in Grover's algorithm? For most functions f(x), there is nothing better than calculating all the values. After all, for most functions, there is no better way of defining the function than giving its truth table. ... • 60.2k 8 votes ### XOR gate for n control qubits in qiskit You can create gates that are controlled on 0 or on 1. You could therefore implement this condition as several gates in a row, each controlled by 1 in the index of the qubit and 0 elsewhere. This will ... • 3,251 8 votes Accepted ### XOR gate for n control qubits in qiskit For the general case, you can use a counting strategy like this: This has a gate count of O(n \lg n) and a work qubit count of O(\lg n). Much better than the naive O(n^2) gate count. You can ... • 40.1k 8 votes Accepted ### How can you decompose Grover's diffusion operator into gates? Grover's diffusion operator can be implemented with H, X and a controlled Z gate. I will show this mathematically. Since |s\rangle = |+\rangle^{\otimes n} :$$ U_s = 2|s\rangle\langle s|-I = H^{\... • 887 8 votes Accepted ### How could one implement a circuit using Grover's algorithm to solve a linear system of equations? You certainly could use Grover's search. You would create 2 registers. This first, of 3 qubits, would effectively store the$\{s_0,s_1,s_2\}$. This is the standard register for Grovers on which you ... • 60.2k 7 votes ### How does the Grover diffusion operator work and why is it optimal? One way of defining the diffusion operator is1$D = -H^{\otimes n}U_0H^{\otimes n}$, where$U_0$is the phase oracle $$U_0\left|0^{\otimes n}\right> = -\left|0^{\otimes n}\right>,\,U_0\left|x\... • 3,726 7 votes ### How is the oracle in Grover's search algorithm implemented? Well, Grover's original paper, "Quantum mechanics helps in searching for a needle in a haystack" clearly states, it assumes that C(S) can be evaluated in a constant time. Grover's search is not ... • 323 7 votes ### What's the point of Grover's algorithm if we have to search the list of elements to build the oracle? While it is perhaps easiest for us to think about the function of the oracle as already having computed all these values, that's not what it's doing. In the case you described, the oracle has 8 ... • 60.2k 7 votes ### Grover's algorithm: a real life example? This is already partially discussed in this related question, but I'll try here to address more specifically some of the issues you rise. Generally speaking, Grover's algorithm rests upon the ... • 26.1k 7 votes Accepted ### Preparing a quantum state from a classical probability distribution Suppose we have two quantum circuits, the first one S computes (or at least approximates) the classical squareroot function (\sqrt{\cdot}) via$$S|x\rangle|0\rangle=|x\rangle |\sqrt{x}\rangle,$\$ ...
• 2,111

Only top scored, non community-wiki answers of a minimum length are eligible