What's the point of Grover's algorithm if we have to search the list of elements to build the oracle?

Question

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 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 $1spadesuit$ in a sequence of 8 cards from a standard 52-card deck:

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

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 $6times 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} = 1spadesuit  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) say that the input of the algorithm is 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 corresponds 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 $|psirangle$, which must be a superposition of all the items in the search space $S$.

We know

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

In this case we have 
$$mathrm{search}_{spadesuit}(|psirangle) = |5_{3text{qubits}}rangle$$
But in this case, our oracle would have to implement the function
$$f(|psirangle) = begin{cases} 1, & |psirangle = |5_{3text{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?

kludg · Accepted Answer

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.

DaftWullie · Answer

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.

Brendan M · Answer

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.

Woody1193 · Answer

Given the oracle you have provided, the search is indeed pointless. However, that oracle misses the point of Grover's algorithm because searching for a card in a deck of cards is not an unstructured search because, as you stated, you already know the order. Ergo, your search is structured. The reason this oracle is used is that it demonstrates how Grover's may be applied without having to discuss an oracle that would make Grover's useful because such an oracle would be more complicated than valuable. Therefore, a better oracle to demonstrate the usefulness of Grover's might be something like:

$$
f(x) = begin{cases} 
         1, & x[0, ldots, 3] + x[4, ldots, 7] = 1010 
         0, & text{otherwise}
end{cases}
$$

What this oracle implies is that you have an 8-qubit search where you take the first four qubits and add them to the second four qubits and flip M if the addition makes 10 (1010 in binary). The difference between this oracle and the one you provided is that this oracle tests a pattern (do the operands add to 10) whereas yours tests equality (is this index 5). This oracle is much more difficult to build but it leverages the true power of Grover's, which is, in essence, a brute-force search where your oracle defines the search space.

Michele Amoretti · Answer

The point is: building a circuit for testing $f(x)$ for being 1 given $x$, is way much simpler than building a circuit for finding $x$ such that $f(x) = 1$.

What's the point of Grover's algorithm if we have to search the list of elements to build the oracle?

Searching in a list, the classical way

Grover and its oracle

5 Answers

Add your own answers!

Ask a Question