Fetching the paper…
Reading the bibliography…
We prove tight $\Omega(n^{1/3})$ lower bounds on the quantum query complexity of the Collision and the Set Equality problems, provided that the size of the alphabet is large enough.
Representation theory of finite groups and associative algebras
C. W. Curtis and I. Reiner · 1962
Earlier work this paper cites.
Linear Representations of Finite Groups
J.-P. Serre · 1977
Earlier work this paper cites.
The Representation Theory of the Symmetric Group
G. James and A. Kerber · 1981
Earlier work this paper cites.
Quantum cryptanalysis of hash and claw-free functions
G. Brassard, P. Høyer, and A. Tapp · 1998
Earlier work this paper cites.
Quantum lower bounds by polynomials
R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf · 2001
Earlier work this paper cites.
The symmetric group: representations, combinatorial algorithms, and symmetric functions
B. E. Sagan · 2001
Earlier work this paper cites.
Quantum lower bounds by quantum arguments
A. Ambainis · 2002
Earlier work this paper cites.
Complexity measures and decision tree complexity: a survey
H. Buhrman and R. de Wolf · 2002
Earlier work this paper cites.
Quantum lower bounds for the collision and the element distinctness problems
Y. Shi · 2002
Earlier work this paper cites.
Polynomial degree vs. quantum query complexity
A. Ambainis · 2003
Earlier work this paper cites.
Quantum lower bounds for the collision and the element distinctness problems
S. Aaronson and Y. Shi · 2004
Cited alongside, same era.
A polynomial quantum query lower bound for the set equality problem
G. Midrijānis · 2004
Cited alongside, same era.
Quantum lower bound for the collision problem with small range
S. Kutin · 2005
Cited alongside, same era.
On the power of Ambainis lower bounds
S. Zhang · 2005
Cited alongside, same era.
All quantum adversary methods are equivalent
R. Špalek and M. Szegedy · 2006
Cited alongside, same era.
Negative weights make adversaries stronger
P. Høyer, T. Lee, and R. Špalek · 2007
Cited alongside, same era.
Learning-graph-based quantum algorithm for k k -distinctness
A. Belovs · 2012
Later among the works it cites.
Span programs for functions with constant-sized 1-certificates
A. Belovs · 2012
Later among the works it cites.
Span-program-based quantum algorithm for evaluating formulas
B. W. Reichardt and R. Špalek · 2012
Later among the works it cites.
How to construct quantum random functions
M. Zhandry · 2012
Later among the works it cites.
Adversary lower bound for the k k -sum problem
A. Belovs and R. Špalek · 2013
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
The need for structure in quantum speedups
S. Aaronson and A. Ambainis · 2011
Cited alongside, same era.
Quantum query complexity of state conversion
T. Lee, R. Mittal, B. W. Reichardt, R. Špalek, and M. Szegedy · 2011
Cited alongside, same era.
Reflections for quantum query algorithms
B. W. Reichardt · 2011
Cited alongside, same era.
Adversary lower bound for element distinctness
A. Belovs · 2012
Cited alongside, same era.
T. Lee and J. Roland · 2013
Closest in time.
Adversary lower bound for the orthogonal array problem
R. Špalek · 2013
Closest in time.
On the power of non-adaptive learning graphs
A. Belovs and A. Rosmanis · 2014
Closest in time.
A note on the quantum collision and set equality problems
M. Zhandry · 2015
Closest in time.