Unrestricted quantum time–space tradeoff for collision finding
- Field
- Topic
Problem
Does every unrestricted quantum collision-finding algorithm satisfy \(T^2S=\Omega(N\log N)\)?
Let \(f:[N]\to[N]\) be uniformly random and available through a coherent value oracle. An algorithm must output distinct \(x,x'\) with \(f(x)=f(x')\) with probability at least \(2/3\). Let \(T\) be its number of oracle queries and \(S\) its maximum retained workspace in qubits, including quantum memory and classical data retained for later use.
Is the tradeoff
valid without any symmetry restriction? In Eq. (1), the external oracle storage is excluded from \(S\), but query registers and accumulated tables are included.
Source
The question is explicitly posed or retained as open in the cited primary literature [Magniez26]. The statement is rewritten here to make its hypotheses and success criterion self-contained.
Progress
BHT upper bound. Storing a table of \(r\) input–output pairs and applying quantum search gives
\begin{equation} T=O\!\left(r+\sqrt{N/r}\right),\qquad S=O(r\log N). \tag{2} \end{equation}The displayed definitions, constraints, and target bounds are recorded in Eqs. (2).
For \(1\le r\le N^{1/3}\), this matches the conjectured tradeoff. The original BHT work introduced the search-based collision method and its time–space interpolation. [Brassard98], [Magniez26]
2023. Hamoudi and Magniez established a lower bound \(T^3S=\Omega(K^3N)\) for finding \(K\) collision pairs. This does not give the stronger single-collision tradeoff stated here. [Hamoudi23]
September 9, 2026. Magniez and Zur prove the desired bounds for label-symmetric algorithms, whose strategy respects permutations of the function’s output labels. Section 1.4 explicitly leaves removal of this assumption open. Standard symmetrization can require \(\Theta(N\log N)\) additional storage and therefore does not preserve the space parameter. [Magniez26]
Retained as open in the unrestricted model. The newest paper resolves an important restricted case, not the full statement.
Comment
This problem is an explicit open extension of a September 9, 2026 preprint.
This asks whether a quantum algorithm can obtain the full collision speedup while retaining asymptotically less usable information than the known table-based methods. The target concerns memory as well as queries, rather than a new query lower bound in the unlimited-space model.
The symmetry issue is substantive: symmetry of a problem does not guarantee a cost-free symmetric implementation of every algorithm. A useful lower-bound invariant would have to control retained information without assuming that the algorithm ignores the numerical identities of output labels. A counterexample would instead need to exploit those identities in a way that improves the query–memory product, not merely the internal implementation constant.
References
- [Brassard98]
- Gilles Brassard, Peter Høyer, and Alain Tapp. Quantum Algorithm for the Collision Problem. LATIN 1998;(1997).arXiv
- [Magniez26]
- Frédéric Magniez and Sebastian Zur. Tight Time-Space Lower Bounds for Collision Finding and Element Distinctness under Label Symmetry. September 9, 2026, preprint. See Section 1.4 and Theorem 4.18.link
- [Hamoudi23]
- Yassine Hamoudi and Frédéric Magniez. Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs. ACM Transactions on Computation Theory 15(1–2) (2023);arXiv