# Grover's algorithm: what to input to Oracle?

I am confused about what to input to Oracle in Grover's algorithm.

Don't we need to input what we are looking for and where to find what we are looking for to Oracle, in addition to the superpositioned quantum states?

For example, assume we have a list of people's names {"Alice", "Bob", "Corey", "Dio"}, and we want to find if "Dio" is on the list. Then, Oracle should take $1/2(|00\rangle + |01\rangle + |10\rangle + |11\rangle)$ as an input and output $1/2(|00\rangle + |01\rangle + |10\rangle - |11\rangle)$. I kind of understand that.

But don't we also need to input the word "Dio" and the list {"Alice", "Bob", "Corey", "Dio"} to Oracle? Otherwise, how can Oracle return output? Is it not explicitly mentioned since Oracle is a black box and we do not have to think about how to implement it?

• Oracle has the ability to recognize if the word "Dio" is in the list.
• To do so, Oracle takes the superpositioned quantum states as an input, where each quantum state represents the index of the list.
• So, input $|00\rangle$ to Oracle means, check if the word "Dio" is in the index 0 of the list and return $-|00\rangle$ if yes and return $|00\rangle$ otherwise.
• In our case, Oracle returns $1/2(|00\rangle + |01\rangle + |10\rangle - |11\rangle)$.
• But what about the list and the word?

Although popular explanations of Grover's algorithm talk about searching over a list, in actuality you use it to search over possible inputs 0..N-1 to a function. The cost of the algorithm is $O(\sqrt{N} \cdot F)$ where $N$ is the number of inputs you want to search over and $F$ is the cost of evaluating the function. If you want that function to search over a list, you must hardcode the list into the function.
Hard coding the function to use a list of $N$ items is usually a very bad idea, because it tends to cause $F$ to equal $O(N)$. Which would make the total cost of Grover's algorithm $O(\sqrt{N} \cdot F) = O(\sqrt{N} \cdot N) = O(N^{1.5})$. Which sort of defeats the whole purpose, since $N^{1.5} > N$.
• Would you not input an ordered list, making the lookup much quicker? Of course, you might want to then include the cost of ordering the list, but I guess that still comes out as $O(\sqrt{N}\log(N))$ overall. – DaftWullie May 26 '18 at 4:09