5
$\begingroup$

I am trying to understand Grover's algorithm. I read that this algorithm is able to find an entry in an unsorted list in just $\sqrt N$ steps, and needs only $\log N$ space.

I understand entanglement and superposition, and I also understand most parts of Shor's Algorithm. When it comes to Grover's algorithm, I often read that this algorithm uses an oracle. But as far as I understand, oracles do not really exist. They are used to describe hypothetical nondeterministic machines. But quantum computers do exist. The algorithm running on a real quantum computer will not really use a clairvoyant ghost who knows things nobody can know at this time.

So, how does it work?

I do not want to read scientific papers that deal with all the details. I just want a brief but correct overview.

Let's use an example: All 7 books about Harry Potter contain approximately 1 million words ($N = 1.000.000$). I want to know if the word "teapot" exists in one of the Harry Potter books, and if so, I want to get the position of at least one occurrence within the text.

If the word doesn't exist in the text, it will take me 1 million comparisons on a normal computer, i.e. 1 million steps. Grover will need only $\sqrt N = 1000$ steps to search through a list of $N = 1.000.000$ unsorted words. How?


Addendum

(reaction to comments)

I am not interested in an explanation about how the oracle works. I do not believe in fairies, elves or oracles. I believe in mathematics and physics. Oracles came into computer science when someone wanted to explain how nondeterministic machines like nondeterministic pushdown automatons will work. But nondeterministic machines do not exist in the real world. Even quantum computers aren't nondeterministic. So, there is no need to use fantasy beings with superpowers to explain quantum computers, since quantum computers do exist while wizards, magicians and oracles don't.

What I want is an explanation of grover's algorithm that uses only things that really exist in reality, i.e. quantum bits, superposition, entanglement, unitary operators etc. plus all the classic parts that still will be needed to sum up to the full algorithm.

And please use my Harry Potter example. If it's easier for you, let's assume that the word "teapot" exists exactly one times in the whole story, so that we know that there is exactly 1 needle in the haystack.

One thing that I do not understand, is this: How can the algorithm read all seven harry potter books (the complete haystack) and tell where exactly the word "teapot" is written using a number of steps that is proportional to the square root of the input length? How can the algorithm even read an input of $N$ items in a time proportional to $\sqrt N$?


Addendum II

I have learned form Norbert's Answer that Grover's Algorithm is unable to search for items in a database (like words in a list of words). So, what can it be used for? Norbert suggested, that Grover's Algorithm might give a square-root speed up for brute-force algorithms used to solve NP-Problems.

Traveling Salesmen is a problem in NP. How can you use Grover's Algorithm to find the shortest path?

If Traveling Salesman is not feasible, please use any other NP problem as an example, and please explain, how Grover's Algorithm can be used to solve it.

I still want to have a brief explanation of Grover's Algorithm (i.e. Grover's algorithm in a nutshell) but didn't get a sufficient answer yet.

$\endgroup$
  • $\begingroup$ I added the title to try to be as specific as possible about what you are asking for. If you think that the current title does not accurately reflect what you were trying to ask feel free to change it back $\endgroup$ – glS Aug 16 at 18:55
  • 2
    $\begingroup$ did you see How does an oracle function in Grover's algorithm actually work?, What exactly is an oracle?, and Is there a layman's explanation for why Grover's algorithm works?? If the answers there do not address your doubts, could you add some more detail about what exactly you find unclear? $\endgroup$ – glS Aug 16 at 18:59
  • $\begingroup$ @glS: I did not want to know how oracles works. I wanted an explanation of Grover's Algorithm. If possible, please explain it completely without elves, dwarfs, wizards and oracles. Please use only really existing physics and mathematics. $\endgroup$ – Hubert Schölnast Aug 16 at 20:21
  • $\begingroup$ @Hubert, please read the links first, and have a look quora.com/… for more easy one explanation if those are not enough. $\endgroup$ – mico Aug 17 at 11:04
  • 3
    $\begingroup$ @HubertSchölnast it seems to me that your question stems from a misunderstanding of what an "oracle" is. It is not something that "does not exist". An oracle in this context is simply a gate the inner workings of which are not being taken into consideration for the time being. In other words, it is assumed that performing the operation implemented by the oracle is "free". There are different reasons why one would want to do this. In the case of Grover's, the oracle is not harder to implement than the classical function that checks whether a given input is the one that you are looking for. $\endgroup$ – glS Aug 17 at 13:01
2
$\begingroup$

I will attempt here to address the question of how Grover's algorithm would work, for the specific task of searching a target entry (let's say a word) in a database of such entries (shall we call it a book?). There have already been plenty of discussions about the general structure of the algorithm (e.g. Is there a layman's explanation for why Grover's algorithm works?, How does the Grover diffusion operator work and why is it optimal?, Why does Grover's search invert about the mean?), as well as how to use it to speed-up finding solutions to NP problems (e.g. here you can find an explicit circuit to apply Grover to a specific 3SAT problem, and here is a breakdown of the steps to apply Grover to a generic SAT problem, and here is a discussion on how to make a SAT problem into an oracle), so I won't focus on these points here.

The specific application of Grover to database searching has also been discussed e.g. in (Grover's algorithm: where is the list?), (How is the Grover-Algorithm applied to a database?), (Does the oracle in Grover's algorithm need to contain information about the entirety of the database?) and (Grover's algorithm: what to input to Oracle?). This answer will thus inevitably overlap with bits and pieces scattered around between those various posts.


Setup: the classical problem

Consider the following classical problem. We have an indexed list of $N$ words. It is thus easy to retrieve a target word $w_x$ given its index $x=1,...,N$. We want to find the index $x_0$ such that $w_0\equiv w_{x_0}$ is some fixed target word. Classically, being the database unsorted, there isn't much to do other than just try each $x$ until $w_x$ is found to be equal to $w_0$.

NOTE: Here, $x$ represents the index of an entry $w_x$. This means that what is usually denoted with $x$ when discussing Grover's algorithm, becomes here $w_x$ instead.

Querying the database

Going quantum, the first thing we need to do is figure out how to handle the database. Grover's algorithm requires as input a superposition state of the form $$|D\rangle=\frac{1}{\sqrt N}\sum_x |x,w_x\rangle\in\mathcal H_{\text{index}}\otimes \mathcal H_{\text{entry}},\tag A$$ where $|x\rangle$ is the index of the corresponding "word" entry $|w_x\rangle$.

Note that generating (A) from a corresponding classical database is highly nontrivial, as it amounts to being able to query the (usually classical) database as if it was a quantum state. One possibility that has been put forward is to use a "QRAM" with input $|+\rangle\equiv\sum_x |x\rangle$ to "load" the database into a superposition (see e.g. this answer), but I don't think the actual feasibility of this is fully understood, as of yet.

Anyhow, for this answer, let's assume that this problem has somehow been solved. We can thus use a query operator $\mathcal Q$ which implements the evolution $$\mathcal Q|x,0\rangle\mapsto|x,w_x\rangle,$$ so that $\mathcal Q|+,0\rangle=|D\rangle$.

We can equivalently write $|D\rangle$ as $$|D\rangle=\sin\alpha|x_0,w_0\rangle+\cos\alpha|X_\perp\rangle,$$ for some $\alpha\in\mathbb R$ (where $\alpha\equiv\arcsin(1/\sqrt N)$), where $|x_0,w_0\rangle$ is the target index/word pair, and $|X_\perp\rangle$ is everything else. We don't need to worry about what $|X_\perp\rangle$ actually looks like, it is enough to know that it is orthogonal to $|x_0,w_0\rangle$.

Apply the oracle

The next step is to apply the oracle operation. In this case this is pretty straightforward: we want to implement the mapping $\mathrm{Orac}_{w_0}:|w\rangle\mapsto(-1)^{\delta_{w=w_0}}|w\rangle$ on the $\mathcal H_{\text{entry}}$ register. We can obtain this operation, for example, by using a pair of additional ancilla registers, and implementing $\mathrm{Orac}_{w_0}$ as the reversible version of the classical circuit implementing the mapping $$\mathrm{Orac}_{w_0}(|w\rangle\otimes|w_0\rangle\otimes |s\rangle) \mapsto |w\rangle\otimes|w_0\rangle\otimes|s\oplus \delta_{w=w_0}\rangle.$$ Then, using as input $|s\rangle=|-\rangle\equiv\frac{1}{\sqrt2}(|0\rangle-|1\rangle)$ gives $$\mathrm{Orac}_{w_0}(|w\rangle\otimes|w_0\rangle\otimes |-\rangle) =(-1)^{\delta_{w=w_0}} (|w\rangle\otimes|w_0\rangle\otimes|-\rangle),$$ so that we can just write $\mathrm{Orac}_{w_0}|w\rangle=(-1)^{\delta_{w=w_0}}|w\rangle$ without worrying about the extra registers. Equivalently, we can write $\mathrm{Orac}_{w_0}=I-2\mathbb P(|w_0\rangle)$ (using the notation $\mathbb P(|\psi\rangle)\equiv|\psi\rangle\!\langle\psi\rvert$).

At this stage, the evolving state is thus $|\Psi_1\rangle\equiv N^{-1/2}\sum_x(-1)^{\delta_{w_x,w_0}}|x,w_x\rangle,$ or equivalently, $$|\Psi_1\rangle=-\sin\alpha|x_0,w_0\rangle+\cos\alpha|X_\perp\rangle.$$ Something that will be useful in the next step is that we can also write $$|\Psi_1\rangle=\cos(2\alpha)|D\rangle+\sin(2\alpha)|D_\perp\rangle,$$ where $|D_\perp\rangle\equiv -\cos(\alpha)|x_0,w_0\rangle + \sin(\alpha)|X_\perp\rangle$.

Diffusion step

The next step is to apply the "diffusion operator" $R_D\equiv 2|D\rangle\!\langle D|-I$ in the space $\mathcal H_{\text{index}}\otimes\mathcal H_{\text{entry}}$. This operator is such that $R_D|D\rangle=|D\rangle$, but $R_D=-1$ on the rest of the space. Equivalently, $R_D|X\rangle=(-1)^{1-\delta_{X,D}}|X\rangle$.

Doing this is actually a bit tricky, as it requires knowledge of $|D\rangle$, and therefore of the database. The only way I can think of to do it is using $\mathcal Q$ and $\mathcal Q^\dagger$. More specifically, we need $R_D=\mathcal QH^{(1)}\mathcal C^{(2)} H^{(1)}\mathcal Q^\dagger$, where $H^{(1)}$ is the Hadamard on the index register, and $\mathcal C$ denotes the reversible version of a classical circuit mantaining the sign of $|\boldsymbol 0,\boldsymbol 0\rangle$ and changing the sign of the rest of the basis states. Indeed, consider the action of such $R_D$ on an input state:

  1. If the input is $|D\rangle$, then we have $\mathcal C^{(2)} H^{(1)}\mathcal Q^\dagger|D\rangle=\mathcal C^{(2)} H^{(1)}|+,\boldsymbol 0\rangle=\mathcal C^{(2)} |\boldsymbol 0,\boldsymbol 0\rangle = |\boldsymbol 0,\boldsymbol 0\rangle$, and thus $R_D|D\rangle=|D\rangle$.
  2. If instead the input is some $|X\rangle$ orthogonal to $|D\rangle$, then $R_D|X\rangle=\mathcal Q H^{(2)}\mathcal C^{(1)}\sum_{Y\neq(0,0)}|Y\rangle=-|X\rangle$.

With this, we are pretty much done. Applying $R_D$ to $|\Psi_1\rangle$ gives $$|\Psi_2\rangle\equiv R_D|\Psi_1\rangle= \cos(2\alpha)|D\rangle-\sin(2\alpha)|D_\perp\rangle =\sin(3\alpha)|x_0,w_0\rangle+\cos(3\alpha)|X_\perp\rangle.$$

The rest of the algorithm then proceeds as usual: we go back and repeat oracle and diffusion steps $\mathcal O(\sqrt N)$ times before measuring. For further details about how the combined action of oracle and diffusion steps results in an effective rotation of $2\alpha$ in state space you can have a look at this other answer of mine.

$\endgroup$
3
$\begingroup$

As this seems a recurring question, let me repeat my answer from Physics.SE:

This seems to be a common misunderstanding about Grover's algorithm. It is not about querying a magically encoded database. Rather, you have an efficiently computable function $f(x)\in\{0,1\}$ and you want to find some $x_0$ for which $f(x_0)=1$. Since you know how to realize $f(x)$ (i.e., you have a circuit), you can run $f$ on a quantum computer and use Grover to find such an $x_0$. This function can be seen as returning entries of a "database", which is encoded in a specific function, though I don't particularly like this picture.

The relevance is in the fact that a large number of interesting problems (namely, the class NP) are such that solutions might be hard to find, but they are easy to verify. Thus, Grover gives a square-root speed-up on any brute-force method to solve such a problem (i.e., any method which does not make use of any special structural property of $f$).

Differently speaking, Grover's algorithm is not, I repeat not, about searching Harry Potter books or the like. It is about speeding up finding solutions of unstructured NP problems (or problems where one does not know the structure), i.e. where the validity of a solution can be checked. This is often called a "search problem", but is has nothing to do with "databases" as we would usually think of them, and is thus not applicable to Harry Potter.

$\endgroup$
  • $\begingroup$ Ok, thank you very much for this answer. It is a bit surprising to me, since everyone (exactly 100%) who tried to explain this algorithm to me before, came up with the picture of searching an item in a database. Your answer is much more plausible! But then I have another question: Traveling Salesman, 3-SAT, Sudoku, Rubik's Cube, Integer Factorization and many more are problems in NP. How can Grover's Algorithm be used to solve one of those problems? $\endgroup$ – Hubert Schölnast Aug 18 at 7:13
  • $\begingroup$ Let me ask different: Which concrete problem can be solved with Grover's algorithm on a quantum machine faster than with a classical algorithm on a classical computer? $\endgroup$ – Hubert Schölnast Aug 18 at 7:17
  • $\begingroup$ @HubertSchölnast I have no idea why people explain this as "database search". -- Whenever you have an NP-problem and solve it by brute force (try all potential solutions), Grover will give you a quadratic speedup. Of course, many problems have much better heuristic (or even deterministic) solvers than brute force search. - The other thing is that Grover is used as a plug-in in other quantum algorithms. $\endgroup$ – Norbert Schuch Aug 18 at 10:57
  • 1
    $\begingroup$ "but is has nothing to do with "databases" as we would usually think of them, and is thus not applicable to Harry Potter" why not though? Isn't searching from a database an instance of an NP problem? Of course this is assuming that one has the whole database loaded in a quantum memory, or a way to "quantum query" a classical database, but provided that this is the case, you can solve the problem of finding the position of a target word in a book (database of words) with quadratic speed-up $\endgroup$ – glS Aug 18 at 14:36
  • $\begingroup$ @glS If you explain me how to encode Harry Potter in an efficiently computable function (this is, f(x) gives the letter at position x), I'm with you. However, this is not what we usually have for a database (or what most people would even call a database), and this is why I think this way of presenting it is highly misleading. Do you have any details as to how Harry Potter could be loaded into a quantum memory, and how this could be queried? (Maybe you have something specific in mind when you say "Quantum Memory".) $\endgroup$ – Norbert Schuch Aug 18 at 14:40
1
$\begingroup$

From a software developer point of view, an Oracle is like a blackbox of function to be called. For the traveling salesman problem, if you have $n$ cities, there are up to $m=\frac{n^2-n}{2}$ direct routes between two cities, an Oracle can tell whether any subset of the $m$ routes is a valid path (visit each city exactly once) and the total path length is less than a given $x$. Even though classic method does call such naive Oracle directly, the best known algorithm requires $O(2^n)$ operations.

Now one can apply Grover‘s algorithm a few times. For the first time, classically find a path visiting each city at least once, let $x$ be the length of this path. If Grover‘s algorithm succeeds, use the length of the found path as $x$ for the next round. The total number of rounds shall be small (though I personally have not search diligently for a confirmation). Alternatively, one can at least use binary search of $x$. Since there are at most $m^n$ valid paths, we need at most $n\log{m}=O(n\log{n})$ rounds. Each round takes $O(2^\sqrt{n})$, hence total cost is $O(2^\sqrt{n} n\log{n})$, still much smaller than the classic one. Additional analysis probably will reduce the number of rounds.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.