9
$\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?

Improve this question
$\endgroup$
3
  • $\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 ♦
    Commented Jun 4, 2019 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$
    – Foxhole
    Commented Jun 4, 2019 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$
    – Foxhole
    Commented Jun 4, 2019 at 20:21

4 Answers 4

Reset to default
6
$\begingroup$

Grover's algorithm does not have an advantage when searching an unordered database, because encoding the oracle into a circuit requires $\tilde \Omega(n)$ operations. You can prove this with a simple circuit counting argument. If the circuit had size $O(n^{0.99})$ then there would be fewer distinct circuits than distinct oracles. So the actual operational complexity is $\tilde \Omega(n^{1.5})$, even though the query complexity is $O(n^{0.5})$.

Grover's algorithm only has an advantage when the thing you are searching over is abstract, like possible solutions to a SAT problem, as opposed to literally stored in hardware somewhere, like a database.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I don't quite understand what you are saying. What does "fewer distinct circuits than distinct oracles" mean? There is only one oracle, encoding the function that checks whether a given input is the one you are looking for. Also, if I understand you, you are counting the process of loading a classical database into a quantum state as part of the cost, correct? Also, I guess $n$ is the number of elements in the database here. Why should building the oracle require a number of operations scaling with $n$? $n$ elements should correspond to $O(\log_2 n)$ qubits on which it would have to act $\endgroup$
    – glS ♦
    Commented Oct 10, 2019 at 11:32
  • $\begingroup$ @glS There are $2^{w 2^n}$ mappings from an $n$ bit address into $w$ bit data. Every one of them must have a distinct circuit. Every time you add an operation to a circuit there are $n^{O(1)}$ choices to pick from. Solve for $W$ in $(n^{O(1)})^M = 2^{(2^n)}$. Even if you limit to the $n$ one-hot oracles, avoiding the counting thing, you will need to iterate over the classical data as part of constructing the quantum circuit. I guess philosophically speaking I'm objecting to the use of the RAM model when comparing such wildly disparate computing types. $\endgroup$
    – Craig Gidney
    Commented Oct 10, 2019 at 18:03
  • $\begingroup$ still don't get it, sorry. If I use $w$ bit data (i.e. each db entry takes $w$ bits), then I can fit $2^w$ words into $w$ qubits, right? You are counting the number of possible ways to map an $n$-qubit state into $w$ output bits(?) Why does this matter here? I'm looking for a specific state (or a state satisfying a specific criterion), so I need a single circuit, why should counting the number of possible circuits matter?With the RAM thing do you mean that you are objecting the feasability of having as input a superposition over all the db entries? (also is there a typo with $M$ and $W$?) $\endgroup$
    – glS ♦
    Commented Oct 10, 2019 at 18:47
  • $\begingroup$ in summary, what I'm trying to say is that it would be great if you could expand this answer. There seems to be useful information in here. Is this kind of counting argument from somewhere? I haven't seen it before $\endgroup$
    – glS ♦
    Commented Oct 10, 2019 at 18:49
  • $\begingroup$ @gIS See the wikipedia article on circuit complexity en.wikipedia.org/wiki/Circuit_complexity#History . No, you can't fit $w 2^w$ queryable bits of data into $w$ qubits. You can fit $w$ retrievable bits into $w$ qubits. That's Holevo's theorem: en.wikipedia.org/wiki/Holevo%27s_theorem . $\endgroup$
    – Craig Gidney
    Commented Oct 10, 2019 at 19:04
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.

Improve this answer
$\endgroup$
1
  • $\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$
    – Foxhole
    Commented Jun 4, 2019 at 18:41
6
$\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.

Improve this answer
$\endgroup$
2
  • $\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$
    – Foxhole
    Commented Jun 4, 2019 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$
    – Foxhole
    Commented Jun 4, 2019 at 18:34
1
$\begingroup$

Grover's algorithm is a (quantum-)circuit-SAT solver. I suppose it could also be a literal black box solver, but it would only work with black boxes that don't decohere your entangled input state, and I'm having trouble believing that such things exist.

I don't know why Grover or anyone else ever called it a database search algorithm. You can of course give it a circuit that implements a set membership test, with some of the inputs hardwired to the key you're looking up and the rest representing the output value, and call it a database search. But you could do the same thing with a classical SAT solver and no one calls them database search algorithms to my knowledge. And for Grover (or classical SAT solvers) to be competitive on this type of problem, the "database" has to be fundamentally unindexable, which means it's too large to be indexable, which means it isn't actually stored anywhere, which makes it in my opinion not a database (and not data).

Finding an efficient circuit implementing a given function is an important and interesting problem, but it's also incredibly broad; it includes much of what's called computer science. I don't see what can be said about it in the context of Grover's algorithm that wouldn't apply equally in any other context. Grover's algorithm just takes an optimized circuit once you've found it and evaluates it about √N times. The circuit does need to be reversible, making it somewhat different from the usual classical circuits, but that's still not directly related to Grover.

In summary, I think that people don't talk about finding the oracle circuit because it's not actually related to the quantum algorithm (despite Grover's paper's title) and because it's such a complex and far-reaching topic that no treatment could do it justice anyway.

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.