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?

My understanding about Oracle is,

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

| improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – DaftWullie May 26 '18 at 4:09
  • $\begingroup$ @DaftWullie The issue is that Grover must do a lookup under superposition, and this requires a multiplexer circuit with N AND gates (or other non-Clifford operations). A quantum AND gate (i.e. a Toffoli) has non-negligible cost when performing error correction. This cost is technically also present in the classical machine (i.e. RAM has O(N) AND gates), it just happens to be negligible and even avoidable in that context. $\endgroup$ – Craig Gidney May 28 '18 at 1:35
  • $\begingroup$ I don't understand what you're saying. Would you be able to express a question, and answer it, to show the details? (I don't think I can phrase a good enough question at this point) $\endgroup$ – DaftWullie May 28 '18 at 14:06
  • $\begingroup$ @DaftWullie I think the question would be something like "how do I give a quantum computer read access to a classical database and how expensive is it". $\endgroup$ – Craig Gidney May 28 '18 at 18:37

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.