19

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


16

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


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


9

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


8

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


8

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


7

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


7

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


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

$\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

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


6

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


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

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


5

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


5

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


5

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


5

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


5

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


5

There is an algorithm by Dürr and Høyer that seems to solve your problem. This algorithm finds the correct answer in $\mathcal{O}(\sqrt{N})$ time with probability $1/2$. The crux is that they have an oracle which flips the phase of all states with a smaller value than the currently selected one.


5

(Based on the time limitation I assume we're talking about an undergraduate level project, and not something more advanced.) If you look at the questions about Grover's algorithm, you'll notice that a lot of them ask about implementing oracles for interesting tasks - or at least tasks more satisfying than looking for the state $|111\rangle$ :-) One ...


5

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


4

Grover's algorithm is used extensively in quantum cryptography as well. It can be used to solve problems such as the Transcendental Logarithm Problem, Polynomial Root Finding Problem etc.


4

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


4

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\right> = \left|x\right>\,\text{for} \left|x\right>\neq\left|0^{\otimes n}\right>.$$ This shows that $U_0$ can also be written as $U_0 = I-2\left|0^{\...


4

$$ \log_2 604,661,760,000,000,000 \approx 59.07 $$ So use $60$ qubits for the data lines where you will put a uniform superposition. This gives a total of $61$ qubits to run Grover's. $2^{59} = 5.764607523034e+17$ so if you can throw away about $2.8e+16$ possibilities first, you would be able to do it $60$. Edit: As cautioned this is for logical qubits.


4

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


4

I am answering my question. After some google search, I found this image showing CCZ gate by CNOT, T dagger, and T gate. I tried this on IBM Q and it worked. I want to explore why it works but that's another story. For someone who is interested, here is my quantum circuit of Grover's algorithm finding |111> with one iteration.


4

According to this paper, A significant conclusion from this solution is that generically the generalized algorithm also has $O(\sqrt{N/r})$ running time Where 'r' is the number of marked states. By generalized, the authors meant a distribution with arbitrary complex amplitudes. So it seems to answer your question. That the modified initialization would ...


4

Grover focuses on gate costs, while Ambainis focuses on queries. Ambainis solves element distinctness in $O(N^{2/3})$ queries, using $O(N^{2/3})$ memory. If you used that memory to run $O(N^{2/3})$ copies of Grover's algorithm (since each copy needs poly-log space, and I'm being imprecise about logarithmic factors) then each one would search a space of size $...


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