{"id":"arxiv/2611.01767","url":"https://arxiv.org/abs/2611.01767","tags":["quant-ph","cs.CC"],"score":0,"title":"Quantum Lower Bounds for Collision Problems","domain":"quant-ph","source":"arxiv","authors":["Pan Peng","Jingyu Wu"],"reviews":0,"subject":"quant-ph","summary":"We establish tight lower bounds on the adaptive and non-adaptive quantum query complexities of Promised $k$-to-one Finding on an exactly $k$-to-one input string $x\\in\\mathbb Z_q^n$, for every fixed $k\\ge2$ and every feasible alphabet size $q\\ge n/k$. The lower bounds are $Ω_k(n^{1/2-1/(2(2^k-1))})$ for unrestricted adaptive algorithms and $Ω_k(n^{1-1/k})$ for one-round non-adaptive algorithms. The former matches the adaptive quantum algorithm of Liu and Zhandry [LZ19], whereas the latter matches classical birthday sampling even when the parallel queries are arbitrarily entangled. We also…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-11-01","reactions":{}}