Adversary lower bound for the k-sum problem

Abstract

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.