<p>Consider the following problem:</p>

<ul>
<li>Let $x\in X$ be a uniformly random value. </li>
<li>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$.</li>
<li>Goal: Find $x$ using $q$ queries to $O$.</li>
</ul>

<p><strong>Conjecture:</strong> The probability of finding $x$ is $O(q/\lvert X\rvert)$.</p>

<p>Is this true? If not, what is the best upper bound for the probability?</p>

<p><strong>Note:</strong> 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.</p>

<p><strong>Note:</strong> 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).</p>

CC BY-SA 3.0
2017-11-27T18:03:24.370Z
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 
CC BY-SA 3.0
2017-11-29T08:18:31.343Z
The idea came to mind, but I have couldn't think of a way how to do it.
Dominique Unruh
<quantum-computing><quantum-information><query-complexity>
Query complexity of quantum search with measuring oracle
Dominique Unruh
# Query complexity of quantum search with measuring oracle

(Asked by: username_0 on 2017-11-15)

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

**Tags:** quantum-computing, quantum-information, query-complexity
> **Comments:**
> **username_1**: 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|$?  
> **username_0**: The idea came to mind, but I have couldn't think of a way how to do it.  

---

## 0 answers

