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 ...
user avatar
27 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 ‘...
user avatar
22 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 ...
user avatar
  • 47.1k
22 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 $|\...
user avatar
  • 13.5k
14 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 ...
user avatar
  • 3,034
13 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 ...
user avatar
11 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>}\...
user avatar
  • 47.1k
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 ...
user avatar
11 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 ...
user avatar
10 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 ...
user avatar
  • 47.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 ...
user avatar
  • 2,107
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, ...
user avatar
9 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....
user avatar
  • 22.5k
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 $...
user avatar
  • 47.1k
8 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 ...
user avatar
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 ...
user avatar
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. ...
user avatar
  • 47.1k
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 ...
user avatar
  • 3,183
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 ...
user avatar
  • 22.5k
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 ...
user avatar
  • 47.1k
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 ...
user avatar
  • 47.1k
7 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 ...
user avatar
  • 18.8k
7 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 ...
user avatar
7 votes
Accepted

Implementing Grover's oracle with multiple solutions in Qiskit

There are different ways to achieve that, my favorite is probably this one: The oracle you describe above is just a classical function ("True if my bitstring is 101 or 110") converted to a ...
user avatar
  • 2,253
7 votes
Accepted

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

Lov Grover actually wrote a paper on how he came up with his search algorithm: https://arxiv.org/abs/quant-ph/0109116 There are three main sources of inspiration: Firstly, he talks about how quantum ...
user avatar
  • 475
6 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\...
user avatar
  • 3,457
6 votes
Accepted

Why is an oracle qubit necessary in Grover's algorithm?

From the perspective of defining the quantum circuit, the oracle qubit is not strictly necessary. For example, in Grover's search, you might normally define the action of the oracle as $$ U|x\rangle|y\...
user avatar
  • 47.1k
6 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 ...
user avatar
6 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 ...
user avatar
  • 18.8k
6 votes

Grover's algorithm: a real life example?

One main assumption to be efficient within a usage of a database is that you can load with a superposition of addresses data from a RAM, also called QRAM (see https://arxiv.org/abs/0708.1879). Then ...
user avatar
  • 61

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