{"id":"arxiv/2609.10808","url":"https://arxiv.org/abs/2609.10808","tags":["quant-ph","cs.CC","cs.CR","cs.DS"],"score":0,"title":"Tight Time-Space Lower Bounds for Collision Finding and Element Distinctness under Label Symmetry","domain":"quant-ph","source":"arxiv","authors":["Frédéric Magniez","Sebastian Zur"],"reviews":0,"subject":"quant-ph","summary":"How much memory is needed to retain the quantum speedup for collision finding? For a uniformly random function $f:[N]\\to [N]$, the BHT algorithm finds a collision using $O(N^{1/3})$ queries and a quantumly accessible classical table containing $O(N^{1/3})$ input-output pairs, whereas a logarithmic-space Grover search uses $O(\\sqrt N)$ queries. Determining the optimal query-space tradeoff between these extremes remains a major open problem. We resolve this equation within the class of label-symmetric algorithms, which treat the function $f$'s output labels as interchangeable. We prove that…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-09","reactions":{}}