# Grover with randomized oracle

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?

• Is $n$ the number of qubits (bits) used for the codomain of $f$? You can always amplify by repeating Grover and try until success. Commented Apr 28 at 23:54
• 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$? Commented Apr 29 at 6:39
• n is the size of the codomain of f. Commented Apr 29 at 17:08
• The range of p is not a concern for me. I want to understand how to do a search with a nonperfect oracle. Commented Apr 29 at 17:11