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

Abstract

We give elementary proofs of the $Ω(n^{2/3})$ quantum query lower bound for element distinctness and the $Ω(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.

Can tight quantum query lower bounds for element distinctness and $k$-sum be proved using state comparisons rather than polynomial approximation, negative-weight adversaries, or compressed oracles? This paper gives proofs using basic quantum-state properties and linear algebra, recovering known optimal bounds rather than improving their asymptotic values. For element distinctness on $n$ entries over an alphabet of size at least $n+1$, it proves an $\Omega(n^{2/3})$ bounded-error query lower bound. The argument compares a uniformly random distinct input with inputs obtained by replacing one or two entries by a shared fresh symbol. Distributional symmetry bounds the aggregate squared first-order state differences after $t$ queries by $4t$. A second-order difference then bounds the expected squared separation between distinct and collision-planted inputs by $O(T/n+T^3/n^2)$, forcing the claimed lower bound. For fixed $k\ge2$, the method extends to $k$-sum over a finite abelian group $G$ with $|G|\ge n^k$, giving $\Omega(n^{k/(k+1)})$ queries. Higher-order alternating state differences satisfy $S_{j,t}\le4^j\binom{t}{j}$; planting a solution yields expected squared state separation $O_k(T/n+T^{k+1}/n^k)$. The element-distinctness proof does not cover alphabet size exactly $n$; an extension is stated to require additional complications. The $k$-sum result assumes fixed $k$ and sufficiently large groups. Extensions to $k$-distinctness and superlinear lower bounds for triangle finding remain open directions; for triangle finding, the paper notes the lack of a suitable hard input distribution.