Adversary lower bound for the k-sum problem
Aleksandrs Belovs, Robert Špalek · 2013
We prove a tight quantum query lower bound Omega(nk/(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.