Elementary proofs of quantum lower bounds for element distinctness and k-sum
Andris Ambainis, Martins Kokainis
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.
quant-pharXiv:2610.32693•Oct 26, 2026•0 citations