The quantum query complexity of read-many formulas

A Boolean function

E. I. Nechiporuk · 1966

Earlier work this paper cites.

Complexity of the realization of a linear function in the class of Π \Pi -circuits

V. M. Khrapchenko · 1971

Earlier work this paper cites.

Quantum mechanics helps in searching for a needle in a haystack

Lov K. Grover · 1996

Earlier work this paper cites.

Strengths and weaknesses of quantum computing

Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani · 1997

Earlier work this paper cites.

Quantum lower bounds by polynomials

Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf · 1998

Earlier work this paper cites.

Tight bounds on quantum searching

Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp · 1998

Earlier work this paper cites.

Quantum vs. classical communication and computation

Harry Buhrman, Richard Cleve, and Avi Wigderson · 1998

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

Earlier work this paper cites.

Quantum search on bounded-error inputs

Peter Høyer, Michele Mosca, and Ronald de Wolf · 2003

Earlier work this paper cites.

Quantum lower bounds for the collision and the element distinctness problems

Scott Aaronson and Yaoyun Shi · 2004

Earlier work this paper cites.

A lower bound on the quantum query complexity of read-once functions

Howard Barnum and Michael Saks · 2004

Cited alongside, same era.

Quantum query complexity for some graph problems

Aija Berzina, Andrej Dubrovsky, Rusins Freivalds, Lelde Lace, and Oksana Scegulnaja · 2004

Cited alongside, same era.

Quantum query complexity of some graph problems

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

Cited alongside, same era.

On the power of Ambainis lower bounds

S. Zhang · 2004

Cited alongside, same era.

Polynomial degree and lower bounds in quantum complexity: Collision and element distinctness with small range

Andris Ambainis · 2005

Cited alongside, same era.

Quantum lower bound for the collision problem with small range

Samuel Kutin · 2005

Cited alongside, same era.

Any AND-OR formula of size N N can be evaluated in time N 1 / 2 + o ⁡ ( 1 ) N^{1/2+o(1)} on a quantum computer

Andris Ambainis, Andrew M. Childs, Ben W. Reichardt, Robert Špalek, and Shengyu Zhang · 2007

Later among the works it cites.

Quantum query complexity of boolean functions with small on-sets

Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, and Shigeru Yamashita · 2008

Later among the works it cites.

Unitals in Projective Planes

Susan Barwick and Gary Ebert · 2008

Later among the works it cites.

A quantum algorithm for the Hamiltonian NAND tree

Edward Farhi, Jeffrey Goldstone, and Sam Gutmann · 2008

Later among the works it cites.

Discrete-query quantum algorithm for NAND trees

Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David Yonge-Mallo · 2009

Later among the works it cites.

Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function