Fetching the paper…
Reading the bibliography…
We give a quantum algorithm for evaluating formulas over an extended gate set, including all two- and three-bit binary gates (e.g., NAND, 3-majority).
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.
On the Monte Carlo decision tree complexity of read-once formulae
Miklos Santha · 1991
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.
Lower bounds for monotone span programs
Amos Beimel, Anna Gál, and Mike Paterson · 1995
Earlier work this paper cites.
The complexity of matrix rank and feasible systems of linear equations
Eric Allender, Robert Beals, and Mitsunori Ogihara · 1996
Earlier work this paper cites.
Superpolynomial lower bounds for monotone span programs
László Babai, Anna Gál, and Avi Wigderson · 1996
Earlier work this paper cites.
A fast quantum mechanical algorithm for database search
Lov K. Grover · 1996
Earlier work this paper cites.
Matrix Computations
G. H. Golub and C. F. Van Loan · 1996
Earlier work this paper cites.
Quantum algorithms revisited
Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca · 1998
Earlier work this paper cites.
Optimal black-box secret sharing over arbitrary Abelian groups
Ronald Cramer and Serge Fehr · 2002
Cited alongside, same era.
Tradeoffs in the quantum search algorithm
Lov K. Grover · 2002
Cited alongside, same era.
Polynomial degree vs. quantum query complexity
Andris Ambainis · 2003
Cited alongside, same era.
Quantum decision trees and semidefinite programming
Howard Barnum, Michael Saks, and Mario Szegedy · 2003
Cited alongside, same era.
A note on monotone complexity and the rank of matrices
Anna Gál and Pavel Pudlák · 2003
Cited alongside, same era.
Two applications of information complexity
T. S. Jayram, Ravi Kumar, and D. Sivakumar · 2003
Cited alongside, same era.
Quantum search with variable times
Andris Ambainis · 2006
Later among the works it cites.
Source codes of semidefinite programs for ADV ±
Peter Hoyer, Troy Lee, and Robert Špalek · 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
Closest in time.
A nearly optimal discrete query quantum algorithm for evaluating NAND formulas
Andris Ambainis · 2007
Closest in time.
Discrete-query quantum algorithm for NAND trees
Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David Yeung · 2007
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
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.
Quantum speed-up of Markov chain based algorithms
Mario Szegedy · 2004
Cited alongside, same era.
Tight adversary bounds for composite functions
Peter Hoyer, Troy Lee, and Robert Špalek · 2005
Cited alongside, same era.
On the size of monotone span programs
Ventzislav Nikov, Svetla Nikova, and Bart Preneel · 2005
Cited alongside, same era.
Closest in time.
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
Closest in time.
A quantum algorithm for the Hamiltonian NAND tree
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann · 2007
Closest in time.
Negative weights make adversaries stronger
Peter Hoyer, Troy Lee, and Robert Špalek · 2007
Closest in time.
Search via quantum walk
Frédéric Magniez, Ashwin Nayak, Jérémie Roland, and Miklos Santha · 2007
Closest in time.
Quantum query complexity of up to 4-bit functions
Ben W. Reichardt and Robert Špalek · 2007
Closest in time.