2
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ 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|$? $\endgroup$ – Peter Shor Nov 27 '17 at 18:03
  • $\begingroup$ The idea came to mind, but I have couldn't think of a way how to do it. $\endgroup$ – Dominique Unruh Nov 29 '17 at 8:18

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.