{"id":"arxiv/2610.32693","url":"https://arxiv.org/abs/2610.32693","tags":["quant-ph"],"score":0,"title":"Elementary proofs of quantum lower bounds for element distinctness and k-sum","domain":"quant-ph","source":"arxiv","authors":["Andris Ambainis","Martins Kokainis"],"reviews":0,"subject":"quant-ph","summary":"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.","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-10-23","reactions":{}}