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

The polynomial method in circuit complexity

Richard Beigel · 1993

Earlier work this paper cites.

On span programs

Mauricio Karchmer and Avi Wigderson · 1993

Earlier work this paper cites.

On the power of quantum computation

Daniel R. Simon · 1997

Earlier work this paper cites.

Quantum algorithms revisited

Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca · 1998

Earlier work this paper cites.

Analog analogue of a digital quantum computation

Edward Farhi and Sam Gutmann · 1998

Earlier work this paper cites.

Quantum computation and quantum information

Michael A. Nielsen and Isaac L. Chuang · 2000

Earlier work this paper cites.

Quantum lower bounds by polynomials

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

Earlier work this paper cites.

A characterization of span program size and improved lower bounds for monotone span programs

Anna Gál · 2001

Earlier work this paper cites.

Learning DNF in time 2 O ~ ​ ( n 1 / 3 ) 2^{\tilde{O}(n^{1/3})}

Adam R. Klivans and Rocco A. Servedio · 2001

Earlier work this paper cites.

Quantum lower bounds by quantum arguments

Andris Ambainis · 2002

Earlier work this paper cites.

Optimal black-box secret sharing over arbitrary Abelian groups

Ronald Cramer and Serge Fehr · 2002

Earlier work this paper cites.

Polynomial degree vs. quantum query complexity

Andris Ambainis · 2003

Earlier work this paper cites.

Quantum decision trees and semidefinite programming

Howard Barnum, Michael Saks, and Mario Szegedy · 2003

Earlier work this paper cites.

Exponential algorithmic speedup by quantum walk

Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. Spielman · 2003

Earlier work this paper cites.

A note on monotone complexity and the rank of matrices

Anna Gál and Pavel Pudlák · 2003

Earlier work this paper cites.

Semidefinite programs and combinatorial optimization

László Lovász · 2003

Earlier work this paper cites.

New degree bounds for polynomial threshold functions

Ryan O’Donnell and Rocco A. Servedio · 2003

Cited alongside, same era.

Quantum lower bounds for the collision and the element distinctness problem

Scott Aaronson and Yaoyun Shi · 2004

Cited alongside, same era.

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

Howard Barnum and Michael Saks · 2004

Cited alongside, same era.

Learning intersections and thresholds of halfspaces

Adam R. Klivans, Ryan O’Donnell, and Rocco A. Servedio · 2004

Cited alongside, same era.

Quantum speed-up of Markov chain based algorithms

Original

Mario Szegedy · 2004

Cited alongside, same era.

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

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

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

Later among the works it cites.

A quantum algorithm for the Hamiltonian NAND tree

Edward Farhi, Jeffrey Goldstone, and Sam Gutmann · 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.

Unbounded error quantum query complexity

Original

Ashley Montanaro, Harumichi Nishimura, and Rudy Raymond · 2007

Later among the works it cites.

Hamiltonian oracles

Carlos Mochon · 2007

Later among the works it cites.

private communication, 2008

Andris Ambainis · 2008

Later among the works it cites.