3
$\begingroup$

The Setup for Grover's Algorithm is the following:
Given an oracle $f_O^{\pm}$ representing a Query on a Database with total $N$ entries $N$ of which $k$ are matching. Grover's Algorithm is used to find with high probability a matching entry $x^*$.

In most papers researching Grover's Algorithm, the underlying assumption is that $k\lt\lt N$. Under the above assumption the optimal number of iterations is estimated to be $\frac{\pi}{4}\sqrt{\frac{N}{k}}$.

My questions is the following - What happens when Grover's Algorithm is applied to a database where this assumption is seriously violated? What's the optimal number of iterations in these cases? What happens in cases where $\frac{k}{N} \ge 0.5$?

$\endgroup$
5
$\begingroup$

A (wonderful) discussion of this problem can be found in Nielsen and Chuang (Sec. 6.1.4 Performance). The number of marked elements is labelled $M$ below (instead of $k$ in your case) and the emphasis is mine.

tl;dr if you know $M \geq N/2$ then just randomly pick an item: this has a success probability at least one-half and only requires one call to the oracle. If it is not known whether $M \geq N/2$, then, double the search space (which can be done by adding a single qubit since $N = 2^n$, where $n$ is the number of qubits) with the new $N$ elements such that none of them are solutions to the search -- as a consequence, the number of marked elements is now less than $N/2$.

Here's the quoted section:

If $M$ is known in advance: What happens when more than half the items are solutions to the search problem, that is, $M \geq N/2$? [...] the number of iterations needed by the search algorithm increases with $M$, for $M \geq N/2$. Intuitively, this is a silly property for a search algorithm to have: we expect that it should become easier to find a solution to the problem as the number of solutions increases. There are at least two ways around this problem. If $M$ is known in advance to be larger than $N/2$ then we can just randomly pick an item from the search space, and then check that it is a solution using the oracle. This approach has a success probability at least one-half, and only requires one consultation with the oracle. It has the disadvantage that we may not know the number of solutions $M$ in advance.

In the case where it isn’t known whether $M \geq N/2$, another approach can be used. [...] The idea is to double the number of elements in the search space by adding $N$ extra items to the search space, none of which are solutions. As a consequence, less than half the items in the new search space are solutions. This is effected by adding a single qubit $|q \rangle$ to the search index, doubling the number of items to be searched to $2N$.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Adding another qubit - wouldn't that result in doubling of M as well? Also our oracle works on logN qubits. How would that work with an extra qubit? $\endgroup$ – vasjain Jul 5 at 23:45
  • $\begingroup$ No, please see the relevant section in the book (or the quote above). We double the search space, yes, but none of the (newly added) $N$ elements are solutions -- therefore, $M$ remains the same. $\endgroup$ – keisuke.akira Jul 5 at 23:51

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.