4
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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:

$\endgroup$

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.