How can Grover's algorithm be implemented when having a string or other data type as input?

Question

For some reason, I'm having difficulty with a seemingly very basic component of Grover's. When reading most explanations, the problem is framed as "consider an unstructured database of N items. If we are looking for value $\omega$, then the oracle marks the item, the amplitude is increased," and so on. However, my understanding is this, and please correct me:

"Given an unstructured database of N items, a quantum database exists containing N items with indices $|0\rangle ... |N\rangle$. If we are looking for a value $\omega$, an oracle function finds $\omega$ in the database, marks the index $|X\rangle$ for $\omega$, and the algorithm proceeds to increase the amplitude of $|X\rangle$".

In this understanding, the quantum states act as indices for "real" entries in some unstructured database, like names or phone numbers. I am getting confused in that most explanations seem to be

1. Considering a specific quantum state to look for, i.e. $|1001\rangle$.
2. Implementing an oracle specifically for the purpose of marking and amplifying this state, and
3. Showing that the oracle did, in fact, amplify that state.

I would think that the point of the oracle would be to mark whichever state acted as the index for a desired value $\omega$, not the other way around. That being said, how could someone implement this in the context of having a string or other data type as input? I’m more focused on the concept in general, but the issue of data types arises for me necessarily.

I.e., looking for value "1" as $\omega$ in this table:

Index	Value
00>	2
01>	0
10>	3
11>	1

should use the oracle to find 1, mark the state $|11\rangle$, and amplify $|11\rangle$ to act as a return value.

Any advice would be greatly appreciated.

Answer 1

A lot of explanations of Grover's search suffer from the common issue of claiming it's a database search or, worse yet, looking for a hardcoded element. (You have examples of both in your question, so you've already noticed this!)

In reality Grover's search is best thought of as a way of searching for an element that satisfies a certain condition, i.e., inverting a function. The oracle should encode not the answer itself (that would be really weird), but a way to recognize that the bit string presented to it is an answer. You can encode the database into the oracle, but that will be computationally expensive and defeat the purpose of using Grover's search.

Here is the way I usually describe the search problem (the problem solved by the Grover's search algorithm) to avoid the database search analogy.

Here are several questions similar to yours with excellent answers that offer more insight:

• How is the Grover-Algorithm applied to a database?
• In Grover's Algorithm, does the exact solution need to be given to the oracle?
• Grover algorithm for a database search: where is the quantum advantage?