Adversary Lower Bound for the k-sum Problem [PDF]
Aleksandrs Belovs, Robert SpalekWe 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. This is an extended and simplified version of an earlier preprint of one of the authors arXiv:1204.5074.View original: http://arxiv.org/abs/1206.6528
No comments:
Post a Comment