8
$\begingroup$

I have been trying to understand what could be the advantage of using Grover algorithm for searching in an arbitrary unordered database D(key, value) with N values instead of a classical search.

I assumed that the oracle function is a function f(key)=y, where y is the index of the corresponding value in the classical database.

My problem is related to the oracle. The oracle circuit has to be modified for each search is performed in the database because the key is specified in the oracle. Let's assume this is a negligible operation for simplicity.

Supposing that the oracle circuit has to be calculated classically, it would require to produce a circuit which behaves like the function f(key)=y. This function would be obtained in at least O(N) steps (except for some special cases). The oracle function circuit has to be recalculated each time a database entry is being modified/added/removed, with a cost of O(N).

Many papers such as Quantum Algorithm Implementations for Beginners, Quantum Algorithms for Matching and Network Flows seem to not consider the oracle at all.

I don't know if I have to consider a quantum database for obtaining a real advantage or not (this and the unreliability of quantum results convinced me is not a very good idea, but it is just conjecture).

So, where is considered the complexity for building the oracle? Have I misunderstood something?

Is "The oracle function circuit has to be recalculated each time a database entry is being modified/added/removed, with a cost of O(N)" a wrong assumption?

$\endgroup$
  • $\begingroup$ why do you say that "The oracle function circuit has to be recalculated each time a database entry is being modified/added/removed"? The oracle function would just need to be an reversible version of the classical circuit checking whether a given key is the one you are looking for. Changing the number of keys (i.e. what elements are in the database) does not require you to change the structure of the oracle, just like it doesn't require you to change the classical function you would use for a normal search $\endgroup$ – glS Jun 4 at 19:15
  • $\begingroup$ Well, the problem is with "just need to be an reversible version of the classical circuit". If it would have been a trivial 1:1 corrispondance between a classical algorithm and a quantum one, there would be some kind of a compiler from a classical programming language to a quantum circuit. Converting things from classical algorithm "as it is" to quantum ones always seemd to me a bad idea, also because most operations hardly scale (see nCNOT implementation). $\endgroup$ – Moreno G Jun 4 at 19:57
  • $\begingroup$ In the quantum circuit, you have no access to a physical classical database. The "quantum computer" system interacts with : - A circuit scheme description, which is given by (usually) a classical program as input; - The outcomes of the execution as output. During execution, there is no access to other external resources (i'm not sure if this is by design or by limits of the actual technology). So, knowing that the oracle describes both the database and the key, it has to be modified. And this is often a non trivial operation $\endgroup$ – Moreno G Jun 4 at 20:21
6
$\begingroup$

You are right to recognize the complexity of building the oracle to use it with Grover's search - it is indeed the tricky part of solving the problem, and indeed a lot of sources don't consider this complexity.

I like to think about the oracle as a tool to recognize the answer, not to find it. For example, if you're looking to solve a SAT problem, the oracle circuit will encode the Boolean formula for a specific instance of a problem you're trying to solve. The circuit size in this case depends on the size of the formula, and not on the size of the search space. You can find an example of implementing an oracle for an instance of SAT problem in my tutorial.

If you were to use Grover's algorithm for database search, the oracle would have to encode the condition you're searching for, but also the criteria of whether the element is in a database. For example, if you're looking for a name starting with A, the oracle needs to recognize all strings starting with A, but it also needs to recognize which of the strings are present in the database - otherwise the algorithm will yield a random string starting with A, which is probably not what you were looking for. (This was not an issue with the SAT problem example, since any variables assignment that satisfies the formula is a valid variable assignment.)

I don't know of a good example of using Grover's search for searching through an unstructured database - to the best of my understanding this algorithm is suited for searches that have some structure. It is worth checking out other questions on Grover on this site, since a lot of them will consider oracle implementations.

$\endgroup$
  • $\begingroup$ I have some doubts on the existance of a good generic way to build a oracle, otherwise i would expect to find it at least there an oracle implementation. Indeed, it seems that using grover algorithm for searching in a database is a bad application. I fully agree about SAT solving application, it suits much better with what Grover algorithm allows to do. $\endgroup$ – Moreno G Jun 4 at 18:41
5
$\begingroup$

The problem is with your initial assumption: the oracle for Grover's is based on a function f(value)=0/1, where 1 indicates that the value meets your search criteria and 0 indicates that it doesn't. This means that you do have to build a new oracle for each different search, but not for each different database.

That said, Grover's algorithm and a quantum database don't make a good replacement for classical database lookup methods. Take a look at this paper for a discussion of the practicalities of Grover's algorithm in this context.

Grover's algorithm has practical application when generalized to amplitude amplification, which shows up as a component of many other quantum algorithms. Amplitude amplification is a way of improving the success likelihood of a probabilistic quantum algorithm.

$\endgroup$
  • $\begingroup$ "Although Grover’s algorithm satisfies Requirement 2 in principle, satisfying it by a significant margin on the log-scale might be difficult in many cases because a small-circuit implementation of the oracle-function p(x) might not exist or might require an unreasonable effort to find.". This is practically the same conjecture i came up with. What I'd like to know is if database search is a bad application for Grover algorithm or not. Is there any formal proof of what is said up here? $\endgroup$ – Moreno G Jun 4 at 18:33
  • $\begingroup$ Also, that's not entirely true, this implementation does provide the result (could be useful when more than one element is marked) $\endgroup$ – Moreno G Jun 4 at 18:34

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.