2

I've read a lot about the Grover algorithm, and even got beyond the point of understanding the "magic" beyond the oracle function. What is yet unclear to me is, given an oracle function which searches for the correct input over a certain field (for example, ID), how do we get information about the other fields?

A more detailed example: Let's say I have a database which encodes ID to full names. I want to use Grover's algorithm to search the ID 1111 in the database, and so I provide the following oracle:

$f((ID,name))=\begin{cases}0,ID\neq1111\\1,ID=1111\end{cases}$

Now I use Grover's algorithm, which builds the entire input set and amplifies the amplitude for the correct vector. Allegedly, at least.

My concern is the following:

  • If i do not provide any details about the name, then the entire name space is also a valid solution to return. The name space is not manipulated during the algorithm, and thus I do not get a result which is necessarily in the database.
  • If I do provide details about the name, that defeats the purpose of the search, since I obviously know the answer.
  • If there is some intrinsic relation between the ID field and the name field, then why not use this relation in order to deduce the name from my request instead of performing the query?

I feel like I'm missing the final piece which makes Grover's algorithm as useful as it is claimed to be, but for now it really does feel like either providing a query too broad to get a meaningful answer, or providing an exact query which defeats the purpose of a search.

Thanks in advance.

glS
  • 27,510
  • 7
  • 37
  • 125
Animo
  • 21
  • 2

1 Answers1

3

Your are right that for database search, the Grover algorithm is somehow not practical as pointed out in article Is quantum search practical?

The main issue is construction of an oracle. The oracle can be very deep circuit and its design (which is done classically). On current noisy QPU deep circuits are difficult to run and results can be meaningless.

Concerning the issue "knowing the answer in advance". You are right that under current state of the development, you have to know answer you search for before running the algorithm. This of course does not make sense. However, the algorithm is intended to be used together with quantum memory (which is still a device very far from maturity). Once you have the memory, you can use Grover to search for a key and look at a record associated (entangled) with the key in the memory.

On the other hand, the Grover can be used even now for solving quadratic binary optimization problems problems. See article Grover Adaptive Search.

Martin Vesely
  • 15,244
  • 4
  • 32
  • 75