Fetching the paper…
Reading the bibliography…
Attempts to separate the power of classical and quantum models of computation have a long history.
Elementary Hadamard difference sets
J. Dillon · 1975
Earlier work this paper cites.
On “bent” functions
O. S. Rothaus · 1976
Earlier work this paper cites.
The Theory of Error–Correcting Codes
F. J. MacWilliams and N. J. A. Sloane · 1977
Earlier work this paper cites.
Probabilistic computations: toward a unified measure of complexity
A. Yao · 1977
Earlier work this paper cites.
The weights of the orthogonals of the extended quadratic binary Goppa codes
G. Lachaud and J. Wolfmann · 1990
Earlier work this paper cites.
Rapid solution of problems by quantum computation
D. Deutsch and R. Jozsa · 1992
Earlier work this paper cites.
Learning Boolean functions via
Y Mansour · 1994
Earlier work this paper cites.
On the power of quantum computation
D. R. Simon · 1994
Earlier work this paper cites.
Construction of bent functions and balanced Boolean functions with high nonlinearity
H. Dobbertin · 1995
Earlier work this paper cites.
Quantum complexity theory
E. Bernstein and U. Vazirani · 1997
Earlier work this paper cites.
Quantum computations: algorithms and error correction
A. Yu. Kitaev · 1997
Earlier work this paper cites.
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
P. Shor · 1997
Earlier work this paper cites.
Design Theory
Th. Beth, D. Jungnickel, and H. Lenz · 1999
Cited alongside, same era.
On Z 4 Z_{4} -linear Goethals codes and Kloosterman sums
T. Helleseth and V. Zinoviev · 1999
Cited alongside, same era.
Quantum Computation and Quantum Information
M. Nielsen and I. Chuang · 2000
Cited alongside, same era.
Sharp quantum versus classical query complexity separations
N. de Beaudrap, R. Cleve, and J. Watrous · 2002
Cited alongside, same era.
Polynomial-time quantum algorithms for Pell’s equation and the principal ideal problem
S. Hallgren · 2002
Cited alongside, same era.
Quantum lower bound for recursive Fourier sampling
S. Aaronson · 2003
Cited alongside, same era.
Limitations of quantum coset states for graph isomorphism
S. Hallgren, C. Moore, M. Rötteler, A. Russell, and P. Sen · 2006
Later among the works it cites.
Quantum algorithms for learning and testing juntas
A. Atici and R. Servedio · 2007
Later among the works it cites.
Quantum algorithm for a generalized hidden shift problem
A. Childs and W. van Dam · 2007
Later among the works it cites.
Quantum algorithms for hidden nonlinear structures
A. Childs, L. J. Schulman, and U. Vazirani · 2007
Later among the works it cites.
On the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems
A. Childs and P. Wocjan · 2007
Later among the works it cites.
Unconditional lower bounds for learning intersections of halfspaces
A. R. Klivans and A. A. Sherstov · 2007
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
W. van Dam, S. Hallgren, and L. Ip · 2003
Cited alongside, same era.
Hidden translation and orbit coset in quantum computing
K. Friedl, G. Ivanyos, F. Magniez, M. Santha, and P. Sen · 2003
Cited alongside, same era.
Classical and quantum function reconstruction via character evaluation
A. Russell and I. Shparlinski · 2004
Cited alongside, same era.
From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
D. Bacon, A. Childs, and W. van Dam · 2005
Cited alongside, same era.
A subexponential-time quantum algorithm for the dihedral hidden subgroup problem
G. Kuperberg · 2005
Cited alongside, same era.
Hyper-bent functions and cyclic codes
C. Carlet and Ph. Gaborit · 2006
Cited alongside, same era.
The power of strong Fourier sampling: quantum algorithms for affine groups and hidden shifts
C. Moore, D. N. Rockmore, A. Russell, and L. J. Schulman · 2007
Later among the works it cites.
Efficient quantum algorithm for identifying hidden polynomials
Th. Decker, J. Draisma, and P. Wocjan · 2008
Closest in time.
Superpolynomial speedups based on almost any quantum circuit
S. Hallgren and A. Harrow · 2008
Closest in time.
Inverse conjecture for the Gowers norm is false
S. Lovett, R. Meshulam, and A. Samorodnitsky · 2008
Closest in time.
A brief introduction to Fourier analysis on the Boolean cube
R. de Wolf · 2008
Closest in time.
Quantum algorithms for shifted subset problems
A. Montanaro · 2009
Closest in time.