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

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

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 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}$$.)

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: