Adversary Lower Bound for the k-sum Problem

2012/06/27 by Aleksandrs Belovs, Belovs, Aleksandrs, Robert Spalek +1 · 1 citation
Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph) #cs.CC #quant-ph

paper · pdf · doi:10.48550/arxiv.1206.6528

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

arxiv created 2012/08/09 · arxiv updated 2012/08/13

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. This is an extended and simplified version of an earlier preprint of one of the authors arXiv:1204.5074.

Citations

• Adversary Lower Bound for Element Distinctness

Cited by

• On the Power of Non-Adaptive Learning Graphs

Related

• Adversary Lower Bound for the Orthogonal Array Problem
• Tight Quantum Lower Bound for Approximate Counting with Quantum States
• Adversary Lower Bounds for the Collision and the Set Equality Problems
• A Quantum Approach to Subset-Sum and Similar Problems
• Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems