Fetching the paper…
Reading the bibliography…
We prove a tight quantum query lower bound $\Omega(n^{k/(k+1)})$ for the problem of deciding whether there exist $k$ numbers among $n$ that sum up to a prescribed number, provided that the alphabet size is sufficiently large.
Quantum lower bounds by polynomials
R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf · 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.
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
Earlier work this paper cites.
Polynomial degree and lower bounds in quantum complexity: Collision and element distinctness with small range
A. Ambainis · 2005
Earlier work this paper cites.
Quantum algorithms for subset finding
A. Childs and J. Eisenberg · 2005
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.
Quantum walk algorithm for element distinctness
A. Ambainis · 2007
Cited alongside, same era.
Negative weights make adversaries stronger
P. Høyer, T. Lee, and R. Špalek · 2007
Cited alongside, same era.
Merkle puzzles in a quantum world
G. Brassard, P. Høyer, K. Kalach, M. Kaplan, S. Laplante, and L. Salvail · 2011
Later among the works it cites.
Quantum query complexity of the state conversion problem
T. Lee, R. Mittal, B. Reichardt, R. Špalek, and M. Szegedy · 2011
Later among the works it cites.
Reflections for quantum query algorithms
B. Reichardt · 2011
Later among the works it cites.
Adversary lower bound for element distinctness
A. Belovs · 2012
Closest in time.
Learning-graph-based quantum algorithm for k k -distinctness
A. Belovs · 2012
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Closest in time.
Personal communication, 2012
K. Kalach · 2012
Closest in time.