# Query complexity of quantum search with measuring oracle

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).

• Have you thought about whether there is some way to combine Elitzur-Vaidman bomb-testing with Grover's algorithm to do better than $q/|X|$? – Peter Shor Nov 27 '17 at 18:03
• The idea came to mind, but I have couldn't think of a way how to do it. – Dominique Unruh Nov 29 '17 at 8:18