1202.1027 (Oded Regev et al.)

Impossibility of a Quantum Speed-up with a Faulty Oracle    [PDF]

Oded Regev, Liron Schiff

We consider Grover's unstructured search problem in the setting where each
oracle call has some small probability of failing. We show that no quantum
speed-up is possible in this case.

View original: http://arxiv.org/abs/1202.1027