Tight Quantum Lower Bound for k-Distinctness
The paper introduces a new quantum query lower bound framework inspired by Zhandry's technique, which is more general than previous methods. It defines 'knowledge' via Fourier basis expansion and allows arbitrary input distributions. This framework successfully proves a tight quantum query lower bound for the k-Distinctness problem, matching known upper bounds for all $k < 2604.05133/pg1$.