2
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ I don't quite understand the concern. The "names" are part of the input state, which effectively functions as the database. So input is $\sum_x |x\rangle$, where each value of $x$ corresponds to a database entry, here an (ID,name) pair. The oracle is what "poses the question", meaning it contains the information about the ID you're looking for. So it'll take $|x\rangle$, and output $(-1)^{f(x)}|x\rangle$, where $f(x)=1$ when the ID field of $x$ is the one you're looking for. At the end, you'll get $|x_0\rangle$ where $x_0$ has the correct ID. You read the name, and thus solved the task. $\endgroup$
    – glS ♦
    Commented May 15, 2023 at 12:04
  • $\begingroup$ My concern is this: if we do not load the entire database into the input space but instead use Hadamard gates to get a generic superposition, we do not get any information about the name space. Loading the entire database as the superposition is highly non-trivial and would require us to have some kind of quantum memory, which is a concern entirely on its own. So the algorithm is either trivial, since we do not need an answer to begin with, or it is useless until we have quantum memory. $\endgroup$
    – Animo
    Commented May 16, 2023 at 7:21
  • $\begingroup$ ah, yes, of course. If you want the input to correspond to a database you can't just apply Hadamard operations. You'll effectively need a gate that creates the state encoding the info in the database. Input state will have to be some $\sum_x |x,f(x)\rangle$ with $f(x)$ "name", and you create these in the usual way with some "oracle" gate which knows about the database (as done eg in phase estimation or hidden subgroup problem). These are not in principle complex operations but, of course, you'd need in practice to be able to control large quantum systems to make this work at any useful scale. $\endgroup$
    – glS ♦
    Commented May 16, 2023 at 8:23

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ if we're talking Grover's for database search, the oracle just needs to check the "name field" against a fixed given one, so surely implementing such an oracle isn't hard, no? $\endgroup$
    – glS ♦
    Commented May 16, 2023 at 8:30
  • $\begingroup$ @glS: If you look for one particular item then probably yes. But on the other hand, if we have tens of qubits, there would be need for multiqubit gates composed of several Toffolis. If we use more complex query with several ANDs and ORs (like in SQL), the oracle can become highly complex. $\endgroup$
    – Martin Vesely
    Commented May 16, 2023 at 9:31
  • 1
    $\begingroup$ sure, but wouldn't the complexity be equivalent to the classical counterpart, as discussed eg in quantumcomputing.stackexchange.com/a/176/55? By which I mean the classical algorithm you'd use to check the name field. Also, I might be getting confused about the problem setup here: the quadratic speedup in grover is in the number of oracle calls. So isn't the complexity of the oracle itself besides the point (provided it's feasible, which in this case it is, as much as the classical counterpart is feasible)? $\endgroup$
    – glS ♦
    Commented May 16, 2023 at 9:39
  • $\begingroup$ @glS: I see your point. Oracle is in worst case of same complexity as in classical case but still number of calls is lower, right? I edited the answer in this way. $\endgroup$
    – Martin Vesely
    Commented May 16, 2023 at 9:51

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.