Fetching the paper…
Reading the bibliography…
Is there a general theorem that tells us when we can hope for exponential speedups from quantum algorithms, and when we cannot? In this paper, we make two advances toward such a theorem, in the black-box model where most quantum algorithms operate.
Rapid solution of problems by quantum computation
D. Deutsch and R. Jozsa · 1992
Earlier work this paper cites.
On the degree of polynomials that approximate symmetric Boolean functions
R. Paturi · 1992
Earlier work this paper cites.
Quantum complexity theory
E. Bernstein and U. Vazirani · 1993
Earlier work this paper cites.
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
P. W. Shor · 1994
Earlier work this paper cites.
On the power of quantum computation
D. Simon · 1994
Earlier work this paper cites.
A fast quantum mechanical algorithm for database search
L. K. Grover · 1996
Earlier work this paper cites.
Strengths and weaknesses of quantum computing
C. Bennett, E. Bernstein, G. Brassard, and U. Vazirani · 1997
Earlier work this paper cites.
Quantum algorithm for the collision problem
G. Brassard, P. Høyer, and A. Tapp · 1997
Earlier work this paper cites.
Quantum lower bounds by polynomials
R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf · 1998
Earlier work this paper cites.
Complexity limitations on quantum computation
L. Fortnow and J. Rogers · 1999
Earlier work this paper cites.
Quantum lower bounds by quantum arguments
A. Ambainis · 2000
Earlier work this paper cites.
Average-case quantum query complexity
A. Ambainis and R. de Wolf · 2000
Cited alongside, same era.
A dual version of Reimer’s inequality and a proof of Rudich’s conjecture
J. Kahn, M. Saks, and C. Smyth · 2000
Cited alongside, same era.
Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables
Y. Shi · 2000
Cited alongside, same era.
Quantum lower bound for the collision problem
S. Aaronson · 2002
Cited alongside, same era.
Sharp quantum versus classical query complexity separations
J. N. de Beaudrap, R. Cleve, and J. Watrous · 2002
Cited alongside, same era.
Quantum amplitude amplification and estimation
G. Brassard, P. Høyer, M. Mosca, and A. Tapp · 2002
Cited alongside, same era.
Quantum lower bounds for the collision and the element distinctness problems
S. Aaronson and Y. Shi · 2004
Later among the works it cites.
A polynomial quantum query lower bound for the set equality problem
G. Midrijanis · 2004
Later among the works it cites.
Every decision tree has an influential variable
R. O’Donnell, M. E. Saks, O. Schramm, and R. A. Servedio · 2005
Later among the works it cites.
A polynomial quantum algorithm for approximating the Jones polynomial
D. Aharonov, V. Jones, and Z. Landau · 2006
Later among the works it cites.
On the Fourier tails of bounded functions over the discrete cube
I. Dinur, E. Friedgut, G. Kindler, and R. O’Donnell · 2006
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Complexity measures and decision tree complexity: a survey
H. Buhrman and R. de Wolf · 2002
Cited alongside, same era.
Almost-everywhere superiority for quantum polynomial time
E. Hemaspaandra, L. A. Hemaspaandra, and M. Zimand · 2002
Cited alongside, same era.
Reimer’s inequality and Tardos’ conjecture
C. D. Smyth · 2002
Cited alongside, same era.
Quantum property testing
H. Buhrman, L. Fortnow, I. Newman, and H. Röhrig · 2003
Cited alongside, same era.
Quantum algorithms for some hidden shift problems
W. van Dam, S. Hallgren, and L. Ip · 2003
Cited alongside, same era.
A. Harrow, A. Hassidim, and S. Lloyd · 2009
Closest in time.
BQP and the polynomial hierarchy
S. Aaronson · 2010
Closest in time.
Some applications of hypercontractive inequalities in quantum information theory
A. Montanaro · 2012
Closest in time.
A. Bačkurs and M. Bavarian · 2013
Closest in time.
A quantum lower bound for distinguishing random functions from random permutations
H. Yuen · 2013
Closest in time.
A note on the quantum collision problem for random functions
M. Zhandry · 2013
Closest in time.