Elementary proofs of quantum lower bounds for element distinctness and k-sum

2026-10-26 · arXiv Quantum Physics

arXiv:2610.32693v1 Announce Type: new

Abstract: We give elementary proofs of the $\Omega(n^{2/3})$ quantum query lower bound for element distinctness and the $\Omega(n^{k/(k+1)})$ lower bound for the $k$-sum problem, for fixed $k$ and sufficiently large groups. The proofs use only basic properties of quantum states and linear algebra, analyzing the differences of algorithm states on different inputs.

原文链接：https://arxiv.org/abs/2610.32693

查看更多资讯请见 AI 行业资讯。