# Grover's Algorithm on a Database with more than 50% matching entries

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

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$$.
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 ﬁnd 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$$.
• 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. Jul 5, 2020 at 23:51