26

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 returns True for one of its possible inputs, and False for all the others. The job of the algorithm is to find the one that returns True. To do this we express ...


25

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 ‘database lookup’, which would necessitate storing the entire database as a quantum circuit somehow, but rather a function such as \begin{equation*} x \...


22

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 $|\text{alive}\rangle$ state: the state preparation channel. In other words, we have to get a new cat. Let us represent the states of the cat on the Bloch sphere ...


21

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 were really the first instances that showed particularly valuable types of speed-up with a quantum computer (e.g. the presumed exponential improvement for Shor) ...


14

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 can think that 3 bits encode the position in the list of the card you are searching; then you don't know the position, but the oracle knows. So if you are ...


13

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 extent explained in Kaye, Laflamme and Mosca (KLM), but let me elaborate on the most important details here. Let $n$ be a natural number, $N = 2^n$, and suppose ...


11

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 classical solution takes one function evaluation, so there is no speedup. Both inputs are not solutions. No matter how many iterations you do, Grover's algorithm is ...


10

$\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>}\newcommand{\proj}[1]{\left|#1\right>\left<#1\right|}$ Since the original question was about a layman's description, I offer a slightly different solution ...


10

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 examples. I've been working with the Microsoft Q# Database Search sample. It simply searches for a specific index/key in the database, which is not very useful. ...


9

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 paper by Roland and Cerf. This agrees with the equivalence between adiabatic and gate-based quantum computation that you mentioned. (One minor correction to ...


9

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 $F(x)$. Define a unitary $U_a$ whose operation is $$U_a:|0\rangle|0\rangle\mapsto\frac{1}{2^{n/2}}\sum_x|x\rangle(\sqrt{1-F(x)}|0\rangle+\sqrt{F(x)}|1\rangle).$...


9

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, say 2/3. Exact is the keyword for deterministic quantum algorithms, such as in this paper Exact quantum algorithms have advantage for almost all Boolean ...


8

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 mathematics. It's also called the BHT algorithm. Introduction: The collision problem most often refers to the 2-to-1 version which was described by ...


8

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 $|x\rangle$: $\langle x|\psi\rangle\neq 0$. we can implement an operation $U_1=-(\mathbb{I}-2|\psi\rangle\langle\psi|)$ we can implement an operation $U_2=\...


8

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 Grover's algorithm is an algorithm because we cannot prove it terminates with the correct answer in a finite number of steps. (Otherwise, what part of the ...


8

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. Probably, you want to talk about the relatively small fraction of cases in which the function $f(x)$ has some reasonably compact description. In that case, you should ...


8

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. Since toggling the $|+\rangle$ state has no effect, this deactivates the oracle when the control is set. Here's this technique applied to a simple comparison ...


8

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 only flip the target qubit if exactly one of the other qubits it 1. You should be able to do this using C4XGate. This would look something like from qiskit....


8

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 improve the gate count to $O(n)$ if you're willing to use more ancilla qubits, by using a recursive strategy where you classify the first half and second half of ...


8

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 apply the Grover iterator. Then, you'd have a second register of at least 3 qubits. You construct the search oracle by evaluating the matrix multiplication on the ...


7

$\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 function that, given any element $\boldsymbol x_k$, checks whether $\boldsymbol x_k$ is the element we are looking for, say $\xtarget$. To do this, the oracle ...


6

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 assumption that one is able to perform a querying operation of the form $$|i\rangle\mapsto(-1)^{f(x_i)}|i\rangle,$$ where $i$ is the index in the database, and $x_i$ ...


6

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 with different sorts of resources. From search problems, you can also define decision problems, which allows you to relate search problems to the usual classes ...


6

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 assume you have one state for the address, one state for the value, and a load operation, which loads the value of the corresponding address into the value ...


6

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^{\otimes n}U_S, $$ starting from an initial state $(H|0\rangle)^{\otimes n}$. This takes time $\Theta(\sqrt{N})$. (I'm using $\mathbb{I}_n$ to denote the $2^n\...


6

You need to convert the oracle to hold the database too, as a result, the general Oracle (Phase Inversion) will have two sub-oracles take a look the figure. The first sub-oracle that have to prepared is the memory circuit, in contrast to QRAM which stores quantum data (state) in its body, this memory (array) circuit is prepared to store only classical ...


6

You are right to recognize the complexity of building the oracle to use it with Grover's search - it is indeed the tricky part of solving the problem, and indeed a lot of sources don't consider this complexity. I like to think about the oracle as a tool to recognize the answer, not to find it. For example, if you're looking to solve a SAT problem, the ...


6

The problem is with your initial assumption: the oracle for Grover's is based on a function f(value)=0/1, where 1 indicates that the value meets your search criteria and 0 indicates that it doesn't. This means that you do have to build a new oracle for each different search, but not for each different database. That said, Grover's algorithm and a quantum ...


6

This can work. There's no reliance on powers of two or anything like that in the basic conception of the algorithm. If $S$ is a subset of computational basis states with $N$ elements and you have a superposition: $$\left |\phi\right> = \frac{1}{\sqrt{N}}\sum_{x \in S}\left|x\right>$$ then basically all you need to do is change the classic Grover ...


6

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 initially did the algorithm, I called this the diffusion transform because I was familiar with classical diffusion and this is what this transform accomplished -...


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