Adversary lower bounds for nonadaptive quantum algorithms

On the time required to check properties of graphs: A problem

A. L. Rosenberg · 1973

Earlier work this paper cites.

On the power of quantum computation

D. R. Simon · 1994

Earlier work this paper cites.

Sampling Algorithms: lower bounds and applications

Z. Bar-Yossef, R. Kumar, and D. Sivakumar · 2001

Earlier work this paper cites.

Quantum lower bounds by polynomials

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

Earlier work this paper cites.

Hidden translation and orbit coset in quantum computing

K. Friedl, G. Ivanyos, F. Magniez, M. Santha, and P. Sen · 2003

Earlier work this paper cites.

Lower bounds for local search by quantum arguments

S. Aaronson · 2004

Cited alongside, same era.

Quantum Lower Bounds for the Collision and the Element Distinctness Problems

S. Aaronson and Y. Shi · 2004

Cited alongside, same era.

Quantum search for multiple items using parallel queries

Lov K. Grover and Jaikumar Radhakrishnan · 2004

Cited alongside, same era.

An algorithmic argument for nonadaptive query complexity lower bounds on advised quantum computation (extended abstract)

Harumichi Nishimura and Tomoyuki Yamakami · 2004

Cited alongside, same era.

Lower bounds on quantum query complexity

Peter Hoyer and Robert Spalek · 2005

Cited alongside, same era.

On the probabilistic query complexity of transitively symmetric problems

P. Koiran, V. Nesme, and N. Portier

Cited in the paper.

Lower bounds for randomized and quantum query complexity using Kolmogorov arguments

S. Laplante and F. Magniez

Cited in the paper.

A quantum lower bound for the query complexity of Simon’s problem

P. Koiran, V. Nesme, and N. Portier · 2005

Later among the works it cites.

All quantum adversary methods are equivalent

Original

R. Spalek and M. Szegedy · 2005

Later among the works it cites.

Polynomial degree vs. quantum query complexity

Andris Ambainis · 2006

Later among the works it cites.

Quantum query complexity of some graph problems

Christoph Dürr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla · 2006

Later among the works it cites.

The quantum query complexity of abelian hidden subgroup problems

P. Koiran, V. Nesme, and N. Portier · 2007

Later among the works it cites.