I'm sorry if this is a stupid question. I want to know about the behavior of Grover's algorithm with oracle having a low one-sided probability of error. So if $f(x)=0$ my oracle returns $0$ and if $f(x)=1$ my oracle returns $1$ with probability $1-p$. Is it true that if $p=o(\frac{1}{\sqrt(n)})$, where $n$ is the size of the codomain of $f$ then Grover's algorithm still returns $x$ with constant probability?

  • $\begingroup$ Is $n$ the number of qubits (bits) used for the codomain of $f$? You can always amplify by repeating Grover and try until success. $\endgroup$ Commented Apr 28 at 23:54
  • $\begingroup$ Are you more interested in how a standard implementation of Grover works in this scenario, or whether the algorithm can be modified to work over a much greater range of $p$? $\endgroup$
    – DaftWullie
    Commented Apr 29 at 6:39
  • $\begingroup$ n is the size of the codomain of f. $\endgroup$
    – ivmihajlin
    Commented Apr 29 at 17:08
  • $\begingroup$ The range of p is not a concern for me. I want to understand how to do a search with a nonperfect oracle. $\endgroup$
    – ivmihajlin
    Commented Apr 29 at 17:11


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.