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$?
Asked
Active
Viewed 483 times
2 Answers
5
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}$.)
Adam Zalcman
- 22,278
- 3
- 34
- 83
3
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:
Mariia Mykhailova
- 9,010
- 1
- 12
- 39