Tight Time-Space Lower Bounds for Collision Finding and Element Distinctness under Label Symmetry

Abstract

How much memory is needed to retain the quantum speedup for collision finding? For a uniformly random function f:[N]→ [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(√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 such algorithm that makes T queries, uses S qubits, and finds a collision in a uniformly random function f:[M]→ [N] with constant probability satisfies T=Ω(N^1/3) and T²S=Ω(Nlog N). For the setting where M=N, these bounds are matched by a space-efficient implementation of the BHT algorithm. As a consequence of our tradeoff, any label-symmetric algorithm for the search version of Element Distinctness on f: [n] → [n²] must satisfy T=Ω(n^2/3) and T²S=Ω(n²log n), matching Ambainis's quantum walk. Thus, both tradeoffs are optimal within the class of label-symmetric algorithms. To prove these results, we develop a space-sensitive version of the compressed oracle technique. The compressed oracle records the information learned by the algorithm in an evolving superposition of databases. Using label symmetry and representation theory, we show that an algorithm using S qubits can effectively retain information about only O(S/log N) collision-free database entries. Substituting this estimate into the compressed oracle technique yields the stated tradeoffs.

Elementary proofs of quantum lower bounds for element distinctness and k-sum
Andris Ambainis, Martins Kokainis
arXiv23 Oct 2026PreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
A Bonded-Particle Discrete-Element Model with Self-Gravity for the Collision and Reaccumulation of Rubble-Pile Asteroids: Formulation and Numerical Protocol
Yohann Trivino
arXiv25 Sep 2026PreprintCC BY 4.0Full textPlanetary science & exoplanets Condensed matterarXiv
Quantum Lower Bounds for Collision Problems
Pan Peng, Jingyu Wu
arXiv1 Nov 2026PreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
Bootstrapping Classical and Quantum Query Lower Bounds for Finding Tarski Fixed Points
Tongyang Li, Weiran Ma, Ziyi Yang +1
arXiv12 Oct 2026PreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
Spatial interference changes the symmetry class of a Josephson element
Takayuki Kubo
arXiv11 Oct 2026PreprintCC BY 4.0Full textCondensed matter Quantum physics & quantum informationarXiv

Cite

BibTeX RIS

BibTeX

@misc{magniez2026tight,
  title = {{Tight Time-Space Lower Bounds for Collision Finding and Element Distinctness under Label Symmetry}},
  author = {Frédéric Magniez and Sebastian Zur},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.10808},
  eprint = {2609.10808},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.10808},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Tight Time-Space Lower Bounds for Collision Finding and Element Distinctness under Label Symmetry
AU  - Frédéric Magniez
AU  - Sebastian Zur
PY  - 2026
DA  - 2026/10/02
PB  - arXiv
DO  - 10.48550/arxiv.2609.10808
UR  - https://arxiv.org/abs/2609.10808
AB  - How much memory is needed to retain the quantum speedup for collision finding? For a uniformly random function f:[N]→ [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(√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 such algorithm that makes T queries, uses S qubits, and finds a collision in a uniformly random function f:[M]→ [N] with constant probability satisfies T=Ω(N^1/3) and T^2S=Ω(Nlog N). For the setting where M=N, these bounds are matched by a space-efficient implementation of the BHT algorithm. As a consequence of our tradeoff, any label-symmetric algorithm for the search version of Element Distinctness on f: [n] → [n^2] must satisfy T=Ω(n^2/3) and T^2S=Ω(n^2log n), matching Ambainis's quantum walk. Thus, both tradeoffs are optimal within the class of label-symmetric algorithms. To prove these results, we develop a space-sensitive version of the compressed oracle technique. The compressed oracle records the information learned by the algorithm in an evolving superposition of databases. Using label symmetry and representation theory, we show that an algorithm using S qubits can effectively retain information about only O(S/log N) collision-free database entries. Substituting this estimate into the compressed oracle technique yields the stated tradeoffs.
ER  -

Abstract

Related

Cite