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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.