Fetching the paper…
Reading the bibliography…
The formula-evaluation problem is defined recursively.
Lower bounds on probabilistic linear decision trees
Marc Snir · 1985
Earlier work this paper cites.
Probabilistic Boolean decision trees and the complexity of evaluating game trees
Michael Saks and Avi Wigderson · 1986
Earlier work this paper cites.
Size-depth tradeoffs for algebraic formulae
Nader H. Bshouty, Richard Cleve, and Wayne Eberly · 1991
Earlier work this paper cites.
Randomized vs. deterministic decision tree complexity for read-once boolean functions
Rafi Heiman and Avi Wigderson · 1991
Earlier work this paper cites.
On the Monte Carlo decision tree complexity of read-once formulae
Miklos Santha · 1991
Earlier work this paper cites.
On read-once threshold formulae and their randomized decision tree complexity
Rafi Heiman, Ilan Newman, and Avi Wigderson · 1993
Earlier work this paper cites.
On span programs
Mauricio Karchmer and Avi Wigderson · 1993
Earlier work this paper cites.
Size-depth tradeoffs for Boolean formulae
Maria Luisa Bonet and Samuel R. Buss · 1994
Earlier work this paper cites.
A fast quantum mechanical algorithm for database search
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 vs. classical communication and computation
Harry Buhrman, Richard Cleve, and Avi Wigderson · 1998
Earlier work this paper cites.
Bounds for small-error and zero-error quantum algorithms
Harry Buhrman, Richard Cleve, Ronald de Wolf, and Christof Zalka · 1999
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.
Quantum lower bounds by quantum arguments
Andris Ambainis · 2002
Cited alongside, same era.
Creating superpositions that correspond to efficiently integrable probability distributions
Lov K. Grover and Terry Rudolph · 2002
Cited alongside, same era.
Tradeoffs in the quantum search algorithm
Lov K. Grover · 2002
Cited alongside, same era.
Quantum complexities of ordered searching, sorting, and element distinctness
Peter Høyer, Jan Neerbek, and Yaoyun Shi · 2002
Cited alongside, same era.
Classical and Quantum Computation
Alexei Yu. Kitaev, Alexander H. Shen, and Mikhail N. Vyalyi · 2002
Cited alongside, same era.
Polynomial degree vs. quantum query complexity
Andris Ambainis · 2003
Cited alongside, same era.
Tight adversary bounds for composite functions
Peter Høyer, Troy Lee, and Robert Špalek · 2005
Later among the works it cites.
On the power of Ambainis’s lower bounds
Shengyu Zhang · 2005
Later among the works it cites.
Source codes of semidefinite programs for ADV ±
Peter Høyer, Troy Lee, and Robert Špalek · 2006
Later among the works it cites.
The quantum adversary method and classical formula size lower bounds
Sophie Laplante, Troy Lee, and Mario Szegedy · 2006
Later among the works it cites.
All quantum adversary methods are equivalent
Robert Špalek and Mario Szegedy · 2006
Later among the works it cites.
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
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Quantum decision trees and semidefinite programming
Howard Barnum, Michael Saks, and Mario Szegedy · 2003
Cited alongside, same era.
Quantum search on bounded-error inputs
Peter Høyer, Michele Mosca, and Ronald de Wolf · 2003
Cited alongside, same era.
Two applications of information complexity
T. S. Jayram, Ravi Kumar, and D. Sivakumar · 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.
Lower bounds for randomized and quantum query complexity using Kolmogorov arguments
Sophie Laplante and Frédéric Magniez · 2004
Cited alongside, same era.
Later among the works it cites.
A nearly optimal discrete query quantum algorithm for evaluating NAND formulas
Andris Ambainis · 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.
Span-program-based quantum algorithm for evaluating formulas
Ben W. Reichardt and Robert Špalek · 2008
Later among the works it cites.
The quantum query complexity of certification
Andris Ambainis, Andrew M. Childs, François Le Gall, and Seiichiro Tani · 2009
Closest in time.
An efficient circuit for the quantum walk update rule
Chen-Fu Chiang, Daniel Nagaj, and Pawl Wocjan · 2009
Closest in time.
Ben W. Reichardt · 2009
Closest in time.
Faster quantum algorithm for evaluating game trees
Ben W. Reichardt · 2009
Closest in time.