Adversary Lower Bound for the k-sum Problem

Aleksandrs Belovs
Robert Spalek
Proceeding of 4th Annual ACM Conference on Innovations in Theoretical Computer Science (ITCS'13)(2013), pp. 323-328


We prove a tight quantum query lower bound Ω(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.