28

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 ...


26

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

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. ...


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

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

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

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 ...


7

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 quantum phase flip. So essentially you only have to build a circuit that implements that classical logic plus some gates to do the phase flip. Option A: Via ...


6

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 possible inputs (i.e. encoded in 3 (qu)bits), and the oracle does all the computation that you need on the fly. So, the moment you try to evaluate the oracle for some ...


6

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\rangle=|x\rangle|y\oplus f(x)\rangle, $$ where $f(x)$ returns 1 if $x$ is the marked item. However, we always use this in a particular way, inputting $(|0\...


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

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

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

It doesn't have to be an inversion about the mean. Let $R$ be the "reflect-a-vector operator", meaning $$R(v) = I - 2 |v\rangle \langle v|$$ Grover's algorithm works by starting in some state $|d\rangle$ and then alternating two reflection operations, $R(s)$ and $R(d)$, where $s$ is the solution vector and $d$ is a "diffusion vector". The choice of $d$ ...


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 ...


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