Impossibility of a Quantum Speed-up with a Faulty Oracle

A fast quantum mechanical algorithm for database search

L. K. Grover · 1996

Earlier work this paper cites.

Strengths and weaknesses of quantum computing

C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani · 1997

Earlier work this paper cites.

Tight bounds on quantum searching

M. Boyer, G. Brassard, P. Høyer, and A. Tapp · 1998

Earlier work this paper cites.

Resilient quantum computation

E. Knill, R. Laflamme, and W. H. Zurek · 1998

Earlier work this paper cites.

Quantum lower bounds by quantum arguments

A. Ambainis · 2000

Earlier work this paper cites.

Dominant gate imperfection in Grover’s quantum search algorithm

G. L. Long, Y. S. Li, W. L. Zhang, and C. C. Tu · 2000

Earlier work this paper cites.

Quantum Computation and Quantum Information

M. Nielsen and I. Chuang · 2000

Earlier work this paper cites.

Quantum lower bounds by polynomials

R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf · 2001

Cited alongside, same era.

Quantum amplitude amplification and estimation

G. Brassard, P. Høyer, M. Mosca, and A. Tapp · 2002

Cited alongside, same era.

Quantum search on bounded-error inputs

P. Høyer, M. Mosca, and R. de Wolf · 2003

Cited alongside, same era.

Effect of unitary noise on Grover’s quantum search algorithm

D. Shapira, S. Mozes, and O. Biham · 2003

Cited alongside, same era.

Effects of a random noisy oracle on search algorithm complexity

N. Shenvi, K. R. Brown, and K. B. Whaley · 2003

Cited alongside, same era.

Quantum search algorithms

A. Ambainis · 2004

Cited alongside, same era.

Robust polynomials and quantum algorithms

General bounds for quantum biased oracles

K. Iwama, R. Raymond, and S. Yamashita · 2005

Later among the works it cites.

Personal communication, 2006

A. Harrow · 2006

Later among the works it cites.

Robust quantum algorithms with ϵ \epsilon -biased oracles

T. Suzuki, S. Yamashita, M. Nakanishi, and K. Watanabe · 2006

Later among the works it cites.

Negative weights make adversaries stronger

P. Høyer, T. Lee, and R. Špalek · 2007

Later among the works it cites.

An introduction to quantum computing

P. Kaye, R. Laflamme, and M. Mosca · 2007

Later among the works it cites.

Search via quantum walk

F. Magniez, A. Nayak, J. Roland, and M. Santha · 2007

Later among the works it cites.