Adversary Lower Bound for the k-sum Problem

Abstract

We 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.

10 pages, minor changes in v2. Extended and simplified version of an earlier preprint of one of the authors arXiv:1204.5074

Cited by in corpus (3)

• Learning-Graph-Based Quantum Algorithm for k-distinctness
• Dual Polynomials for Collision and Element Distinctness
• On the Power of Non-Adaptive Learning Graphs