Consider the following problem:
- Let $x\in X$ be a uniformly random value.
- Let $O$ be an oracle that measures whether the register $Q$ contains $x$. More precisely, $O$ measures $Q$ using the measurement consisting of projectors $\lvert x\rangle\langle x\rvert$ and $1-\lvert x\rangle\langle x\rvert$, and stores the classical outcome in a one bit register $R$.
- Goal: Find $x$ using $q$ queries to $O$.
Conjecture: The probability of finding $x$ is $O(q/\lvert X\rvert)$.
Is this true? If not, what is the best upper bound for the probability?
Note: If $O$ is a unitary quantum oracle (i.e., a unitary mapping $\lvert x,r\rangle$ to $\lvert x,1-r\rangle$, and $\lvert x',r\rangle$ to $\lvert x',r\rangle$ for $x'\neq x$), we know that the bound is $O(q^2/\lvert X\rvert)$. But that is not the oracle described above.
Note: If $O$ is a classical oracle (i.e., $O$ performs a complete measurement of $X$ in the computational basis), we know that the bound is $q/\lvert X\rvert$. But that is not the bound in our case, either, because our oracle $O$ performs only a partial measurement (namely, whether $X$ contains $\lvert x\rangle$ or not).