11
$\begingroup$

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?
Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
5
$\begingroup$

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
$\endgroup$
4
  • $\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
    Commented May 26, 2018 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
    Commented May 28, 2018 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
    Commented May 28, 2018 at 14:06
  • 1
    $\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
    Commented May 28, 2018 at 18:37
0
$\begingroup$

Let me try to answer your question with a simple, direct answer:

Q: 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?

No, you only need to have an oracle that outputs a 1 when it is provided with the correct answer and a 0 when provided with an incorrect answer.

If you have a list that has the input names {"Alice", "Bob", "Corey", "Dio"} and you want to recognize the if the word Dio is on the list, then you need a way to encode the list's contents as input for the oracle. So the question is not what is on this list, the question is how many different inputs do you want to be able to encode? What is the total vocabulary?

If there are 4 possible names (Alice, Bob, Corey and Dio), and you want to be able to encode any list with 4 of these names, then your input is four elements of two bits each: abcdefgh and the encoding is Alice=00, Bob=01, Corey=10 and Dio=11. You then would have an oracle that returns 1 if ab=11, cd=11, ef=11 or gh=11.

If the inputs can be any 5-character string, encoded in 8-bit ASCII, then the input to the oracle is going to be $5\times8\times N$ where $N$ is the maximum number of items that might be in your list. So the input could be quite large. However, the Oracle doesn't need to know all possible inputs; it merely needs to return 1 if any of the inputs contain "Dio" in any allowable position.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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