<p>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.</p>

<p>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?</p>

CC BY-SA 3.0
2012-01-24T20:55:18.140Z
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 
CC BY-SA 3.0
2012-01-24T21:21:14.733Z
I did not know about this result. I will have a look at it.
lamontap
<quantum-computing><query-complexity>
Is there a lower bound for the decisional Grover search problem?
lamontap
# Is there a lower bound for the decisional Grover search problem?

(Asked by: username_0 on 2012-01-24)

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?

**Tags:** quantum-computing, query-complexity

> **Comments:**
> **username_1**: Why can't you directly apply the original theorem of Bennett, Bernstein, Brassard, and Vazirani to prove the lower bound for the decision problem?  
> **username_0**: I did not know about this result. I will have a look at it.  

---

## 0 answers

