Can I use Grover's algorithm for a function that has multiple arguments which satisfy it?

Question

Let's say we have a function $f(x)$, where $f(011) = 1$, and $f(111) = 1$.

Can I still use Grover's algorithm with this function, and receive the result of either $011$, or $111$?

Answer 1

Yes. In fact, Grover's algorithm generally requires fewer iterations if more than one bitstring satisfies the search condition.

More precisely, suppose we wish to find one of $M$ $n$-bit strings that fulfill a condition encoded by $f$ and assume that $0<M \le \frac{N}{2}$ where $N=2^n$ is the number of all $n$-bit strings. The number $R$ of Grover iterations required is bounded by

$$ R \le \left\lceil\frac{\pi}4\sqrt\frac{N}{M}\right\rceil = O\left(\sqrt{\frac{N}{M}}\right), $$

see inequality $(6.17)$ on page 254 in Nielsen & Chuang. (Note that the above only applies when $M \le \frac{N}{2}$, but we can extend the result to $M > \frac{N}{2}$ at the expense of adding a qubit because then the new $N'=2^{n+1}$ and $M \le N = \frac{N'}{2}$.)

Answer 2

Yes. Grover's algorithm is often described in terms of looking for a single solution, but it is easily generalized to functions with multiple solutions, and numbers of solutions unknown beforehand.

Here is a couple of relevant SE questions:

• What to do when the amount of solutions is not known before applying Grovers Algorithm?
• Grover algorithm for more than one element
• How many iterations does Grover’s search need to find one out of $M$ marked items?