# Is there a lower bound for the decisional Grover search problem?

What is known about the decisional version of the search problem? By decisional version of the search problem, I mean the problem in which you wish to determine whether there are $0$, or exactly $t$ values $x$ for which the black-box function $f$ takes the value $1$. Of course, this problem reduces to the traditional Grover search problem; just find an $x$ such that $f(x)=1$ or run the algorithm so many times as to have a good probability that such an $x$ does not exist. This can be done with $O(\sqrt{N/t})$ oracle queries to the oracle function. However, those two problems are not equivalent or at least I don't see how they could be.

Obviously if those two problems were equivalent, the $\Omega(\sqrt{N/t})$ lower bound for Grover search would translate into a lower bound for the decision version. Are there results of equivalence of the two problems or of lower bounds for the decision problem?

• Why can't you directly apply the original theorem of Bennett, Bernstein, Brassard, and Vazirani to prove the lower bound for the decision problem? – Peter Shor Jan 24 '12 at 20:55
• I did not know about this result. I will have a look at it. – Philippe Lamontagne Jan 24 '12 at 21:21