13
$\begingroup$

Grover's algorithm is used, among other things, to search an item $\mathbf{y}$ in an unordered list of items $[\mathbf{x}_0, \mathbf{x}_1, ..., \mathbf{x}_{n-1}]$ of length $n$. Even though there are plenty of questions here regarding this topic, I still miss the point.

Searching in a list, the classical way

Normally, I would design a search function in this way $$ \mathrm{search}([\mathbf{x}_0, \mathbf{x}_1, ..., \mathbf{x}_{n-1}], \mathbf{y}) = i \in \mathbb{N} \quad \text{such that } \mathbf{x}_i = \mathbf{y} $$ So I give the list and the wanted item as inputs, and I receive the position of the item in the list as output. I think I have understood that the information about $\mathbf{y}$ is embedded in the algorithm through the oracle gate $O$, so our function becomes $$ \mathrm{search}_\mathbf{y}([\mathbf{x}_1, \mathbf{x}_2, ..., \mathbf{x}_n] ) = i \in \mathbb{N} \quad \text{such that } \mathbf{x}_i = \mathbf{y} $$ Let's make a practical example. Consider searching the ace of spades $1\spadesuit$ in a sequence of 8 cards from a standard 52-card deck:

shuffled deck

The list of length $8$ is $[ \mathbf{x}_0 = J\clubsuit,$ $ \mathbf{x}_1 = 10\diamondsuit,$ $ \mathbf{x}_2 = 4\heartsuit,$ $ \mathbf{x}_3 = Q\clubsuit,$ $ \mathbf{x}_4 = 3\spadesuit,$ $ \mathbf{x}_5 = 1\spadesuit,$ $ \mathbf{x}_6 = 6\spadesuit, $ $ \mathbf{x}_7 = 6\clubsuit]$.

The wanted element is $\mathbf{x}_5$. I should obtain $\mathrm{search}_{\spadesuit}(cards) = 5$. Each card can be encoded with $\lceil{\log_2 52}\rceil = 6$bits, the list has $8$ elements so we need $6\times 8 = 48$ bits to encode the list. In this case, the oracle $O$ will implement the function: $$f(\mathbf{x}) = \begin{cases} 1, & \mathbf{x} = 1\spadesuit \\ 0, & \text{otherwise} \end{cases}$$

However, the input of Grover's algorithm is not a state of $48$qubits.

(NB: Image of shuffled deck is taken from here)

Grover and its oracle

Several sources (eg. here - graphically explained) says that the inputs of the algorithm are different: the input is a state taken from the search space $S = \{ 0, 1, 2, ..., N \} = \{0, 1, 2, ..., 7 \} $ where $N$ is the number of elements of the list. Each number corrispond to the position of an element in the list.

The input of $\mathrm{search}_{\spadesuit}(\cdot)$ is now a $\lceil \log_2 8 \rceil = 3$qubit vector $|\psi\rangle$, which must be a superposition of all the items in the search space $S$.

We know

  • $|0_{3\text{qubits}}\rangle = |000\rangle$ corrisponds to $J\clubsuit$;
  • $|1_{3\text{qubits}}\rangle = |001\rangle$ corrisponds to $10\diamondsuit$;
  • $|2_{3\text{qubits}}\rangle = |010\rangle$ corrisponds to $4\heartsuit$;
  • $|5_{3\text{qubits}}\rangle = |101\rangle$ corrisponds to $1\spadesuit$ which is the wanted element;
  • and so on...

In this case we have $$\mathrm{search}_{\spadesuit}(|\psi\rangle) = |5_{3\text{qubits}}\rangle$$ But in this case, our oracle would have to implement the function $$f(|\psi\rangle) = \begin{cases} 1, & |\psi\rangle = |5_{3\text{qubits}}\rangle \\ 0, & \text{otherwise} \end{cases}$$

Building the oracle requires us to know that $\spadesuit$ is at position 5. What's the point to execute the algorithm if we have already searched for the element in order to build the oracle?

$\endgroup$
  • $\begingroup$ I also have difficulty understanding the advantage of Grover’s algorithm. Suppose that I have N items in the list. At each call to the Oracle, did it evaluate all N possibilities? Even if the evaluation is very fast but if we still need to iterate over all configurations, then the complexity of Oracle evaluation is O(N). So the Grover’s algorithm doesn’t seem to be faster than dumb search. Is this correct? $\endgroup$ – Sanparith Marukatat Aug 1 '18 at 15:39
  • $\begingroup$ @SanparithMarukatat It's not correct. The items of your list are the terms of the superposition of the state involved in the search. When the Oracle operates on this state, it counts as a single operation. The ability of the Oracle to mark the searched-for term of your superposition is a fundamental part of Grover's insight. To understand Grover's algorithm, I recommend you first understand how this marking off of the desired state happens. Afterwards, make sure to understand the role of the state $|- \rangle$ in the Oracle. $\endgroup$ – R. Chopin Oct 20 '18 at 0:55
  • $\begingroup$ If you understand that, then you should study the operator that is able to increase the amplitude of the desired term in the superposition while at the same time decreasing the amplitude of the undesired terms of the superposition. To me the easiest way to approach Grover's is to look at the inverse-about-mean operator. (Some people take the geometric view, but I don't find it as clear.) $\endgroup$ – R. Chopin Oct 20 '18 at 0:57
7
$\begingroup$

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 searching the ace of spades, then the oracle knows that the ace of spades is the 6th card (or 5th counting from zero) and implements the function $$ f(\mathbf{x}) = \begin{cases} 1, & \text{if x = 5, or binary '101'} \\ 0, & \text{otherwise} \end{cases}$$

PS: It is better to think about the Grover's algorithm differently: you have an oracle implementing a boolean function which outputs $1$ for a single combination of input bits, otherwise outputs zero, and your task is to find the combination. The problem has the same complexity as searching in an unsorted list or database, that is why the Grover's algorithm is usually described as searching in an unsorted database. But applying the algorithm to a real-world database search indeed raises questions that are beyond the algorithm itself. Grover's algorithm is just searching for what the oracle knows.

$\endgroup$
  • $\begingroup$ Yes sorry, that 6 was from a previous edit $\endgroup$ – incud May 20 '18 at 15:36
  • 2
    $\begingroup$ Thank you for your answer. I fixed the miswriting. What's the point of executing the algorithm if in order to build the oracle I need to know the position of the searched element? $\endgroup$ – incud May 20 '18 at 15:39
  • 1
    $\begingroup$ @incud Indeed it does not make sense. I've updated the answer. $\endgroup$ – kludg May 20 '18 at 16:10
  • $\begingroup$ "Grover's algorithm is just searching for what the oracle knows": not necessarily. The oracle may be checking for only some specific property of the input, so that the result one gets at the end contains more information than that encoded in the oracle itsef. A typical example is searching in a phone book. The oracle "asks" for a record attached to a specific name, but once the correct record is found, one also gains the additional information of the phone number attached to that record, which was not encoded at all in the oracle $\endgroup$ – glS May 24 '18 at 14:08
4
$\begingroup$

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 value $x$, the oracle looks up (in this instance) the card that the value of $x$ corresponds to, and then checks if that card is the marked card. The idea being that each time you call the oracle, it goes through that process once. Overall, you evaluate the function a number of times that's equal to the number of times you call the oracle. The aim of any search algorithm is to call that oracle as few times as possible.

In case this sounds a little circular (given an input $x$, find which card that corresponds to), remember that your look-up table for what $x$ corresponds to what card can be ordered which is a different, simpler, much faster search question.

The key differences in your example compared to a more realistic usage scenario are:

  • The search space is usually massive. There's no realistic prospect of precomputing all values. Indeed, that is exactly what we're trying to avoid.

  • Usually, we don't actually say 'find the ace of spades'. Instead, there's an $f(x)$ that is non-trivial to evaluate to test if $x$ is the 'marked' item or not. The fact that the oracle can take quite a long time to evaluate, even for a single entry, is what makes the oracle the costly part to implement (and all other gates are given for free) and why you need to minimise the number of calls.

So, really, the way a classical search would work on your problem is: pick an $x$ at random. Evaluate $y=f(x)$. If $y=1$, return $x$, otherwise repeat. While the net effect of $f(x)$ is 'is the input $x_0$, the marked entry?', that is not the actual calculation that it does.

$\endgroup$
2
$\begingroup$

The question is ultimately: "What's the point to execute the algorithm if we have already searched for the element in order to build the oracle?"

Whilst somebody prebuilt the oracle, it may not have been the person using the oracle.

Grover's algorithm requires the oracle be queried no more times than $\sqrt{\text{size of list}}$. Naturally we cannot hope respective database lookups, as proposed earlier against which I cannot comment for lack of reputation, on say 5 million keys will return the content we want if our content is not addressed by any of those 5 million keys, but by saying the 9 millionth key, which happens not to be in our sample. How does Grover's algorithm do it then?

We ask the oracle: what is the answer it already has for the question it already has? Even Mateus and Omar would ask the "oracle-for-a-particular-alphabet-symbol" during runtime, what are the position(s) of its symbol in the string that it has already compiled? The oracle will give the answer to our query after only one consultation, but in this story, it cannot for example simply write out the answer as a binary string and send it to us over a classical communication channel. It will hide its answer in a superposition for us to draw it out.

I let fancy or metaphor run away in this next bit: we don't quite hear the answer the first time, and we have to ask the oracle to repeat the same answer over and over again until we are sure what the oracle has said, except we start to hallucinate from misinformation in the diffusion process if we ask too many times.

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