AI

Adversary Lower Bound for the k-sum Problem

Abstract

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.