Quantum interpolation of polynomials

A theory of the learnable

L. G. Valiant · 1984

Earlier work this paper cites.

Rapid solution of problems by quantum computation

David Deutsch and Richard Jozsa · 1992

Earlier work this paper cites.

On the degree of polynomials that approximate symmetric boolean functions

Ramamohan Paturi · 1992

Earlier work this paper cites.

On the degree of Boolean functions as real polynomials

Noam Nisan and Mario Szegedy · 1994

Earlier work this paper cites.

A fast quantum mechanical algorithm for database search

Lov Grover · 1996

Earlier work this paper cites.

Limit on the speed of quantum computation in determining parity

Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser · 1998

Cited alongside, same era.

Learning DNF over the uniform distribution using a quantum example oracle

Nader H. Bshouty and Jeffrey C. Jackson · 1999

Cited alongside, same era.

Quantum entanglement and the communication complexity of the inner product function

Richard Cleve, Wim van Dam, Michael Nielsen, and Alain Tapp · 1999

Cited alongside, same era.

Quantum lower bounds by quantum arguments

Andris Ambainis · 2002

Cited alongside, same era.

Quantum lower bounds by polynomials

Robert Beals, Howard Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf

Cited in the paper.

Quantum lower bounds for the collision and the element distinctness problems

Scott Aaronson and Yaoyun Shi · 2004

Later among the works it cites.

Quantum lower bound for the collision problem with small range

Samuel Kutin · 2005

Later among the works it cites.

On computation and communication with small bias

Harry Buhrman, Nikolay Vereshchagin, and Ronald de Wolf · 2007

Later among the works it cites.

Negative weights make adversaries stronger

Peter Høyer, Troy Lee, and Robert Špalek · 2007

Later among the works it cites.