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
31
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.5k
24
votes
Accepted
How can we keep Schrödinger's cat alive?
TL;DR: This is probably going to be disappointing. If a cat enters a superposition and we lose track of the relative phase $\phi$ then there is only one deterministic operation that returns to the $|\...
- 24.8k
23
votes
Accepted
Has there been any truly ground breaking advance in quantum algorithms since Grover and Shor?
Have there been any truly ground breaking algorithms besides Grover's
and Shor's?
It depends on what you mean by "truly ground breaking". Grover's and Shor's are particularly unique because they ...
- 61.7k
17
votes
Accepted
In Grover's Algorithm, why does the optimal number of iterations involve a floor?
Applying the Grover iterate a total number of $\lfloor \frac{\pi}{4}\sqrt{N}\rfloor$ times is the best choice if we want to maximize the success probability of Grover's algorithm. This is to some ...
- 611
16
votes
Accepted
What's the point of Grover's algorithm if we have to search the list of elements to build the oracle?
If you have 8 items in the list (like in your card's example), then the input of the oracle is 3 (qu)bits. Number of cards in the deck (52) is irrelevant, you need 3 bits only to encode 8 cards.
You ...
- 3,244
13
votes
Accepted
Can anyone provide me with an example of the for Grover's algorithm on one qubit?
The case of 1 qubit turns out to be pretty bad for understanding Grover's algorithm. There are several scenarios for the function you're looking at:
Both inputs are solutions to $f(x) = 1$.
The ...
- 9,195
12
votes
Accepted
How does the Grover diffusion operator work and why is it optimal?
$\newcommand{\bra}[1]{\left<#1\right|}\newcommand{\ket}[1]{\left|#1\right>}\newcommand{\braket}[2]{\left<#1\middle|#2\right>}\newcommand{\bke}[3]{\left<#1\middle|#2\middle|#3\right>}\...
- 61.7k
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 ...
- 61.7k
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.4k
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.8k
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....
- 42k
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,901
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.8k
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, ...
- 206
8
votes
Is there a layman's explanation for why Grover's algorithm works?
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 $...
- 61.7k
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 ...
glS♦
- 26.9k
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^{...
- 61.7k
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.4k
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.
...
- 61.7k
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 ...
- 42k
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 ...
- 61.7k
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,766
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 ...
- 61.7k
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 ...
glS♦
- 26.9k
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,156
Only top scored, non community-wiki answers of a minimum length are eligible