Super-Polynomial Quantum Speed-ups for Boolean Evaluation Trees with Hidden Structure

Built on

Probabilistic computations: Toward a unified measure of complexity
A. C.-C. Yao · 1977
Earlier work this paper cites.
Probabilistic boolean decision trees and the complexity of evaluating game trees
M. Saks and A. Wigderson · 1986
Earlier work this paper cites.
Rapid solution of problems by quantum computation
D. Deutsch and R. Jozsa · 1992
Earlier work this paper cites.
Quantum complexity theory
E. Bernstein and U. Vazirani · 1993
Earlier work this paper cites.
Algorithms for quantum computation: discrete logarithms and factoring
P. W. Shor · 1994
Earlier work this paper cites.

On the power of quantum computation
D. Simon · 1994
Cited alongside, same era.
Quantum lower bounds by polynomials
R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf · 2001
Cited alongside, same era.
Quantum factoring, discrete logarithms, and the hidden subgroup problem
R. Jozsa · 2001
Cited alongside, same era.
Quantum lower bound for recursive fourier sampling
S. Aaronson · 2003
Cited alongside, same era.
A quantum algorithm for the Hamiltonian NAND tree
E. Farhi, J. Goldstone, and S. Gutmann · 2008
Cited alongside, same era.

Superpolynomial speedups based on almost any quantum circuit
S. Hallgren and A. W. Harrow · 2008
Later among the works it cites.
Span-program-based quantum algorithm for evaluating formulas
B. Reichardt and R. S ˇ \check{\rm{S}} palek · 2008
Later among the works it cites.
The need for structure in quantum speedups
S. Aaronson and A. Ambainis · 2009
Later among the works it cites.
The polynomial degree of recursive fourier sampling
B. Johnson · 2011
Closest in time.
Faster quantum algorithm for evaluating game trees
B. W. Reichardt · 2011
Closest in time.