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

• URL: http://arxiv.org/abs/2609.10808v1
• Date: Wed, 09 Sep 2026 20:20:17 GMT
• Title: Tight Time-Space Lower Bounds for Collision Finding and Element Distinctness under Label Symmetry
• Abstract summary: We show that an algorithm using $S$ qubits can effectively retain information about only $O(S/log N)$ collision-free database entries.<n>Substituting this estimate into the compressed oracle technique yields the stated tradeoffs.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 such algorithm that makes $T$ queries, uses $S$ qubits, and finds a collision in a uniformly random function $f:[M]\to [N]$ with constant probability satisfies $$T=Ω(N^{1/3}) \qquad\text{and}\qquad T^2S=Ω(N\log 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] \to [n^2]$ must satisfy $$T=Ω(n^{2/3}) \qquad\text{and}\qquad T^2S=Ω(n^2\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.

Related papers

• Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps [28.438129186461598]
  We study the oracle complexity of computing a point with small fixed-point residual $|T(x)-x| leq $, for a general norm $|cdot|$ and a self-map $T$ of a compact convex set.<n>We provide an algorithm that solves such instances for any norm with a weak Rademacher type $q > 1$, with high probability.
  arXiv  Detail & Related papers  (2026-09-08T23:09:39Z)
• A Simple Algorithm for Best Separable State [5.5559749120901385]
  We study the best separable state problem (BSS), which asks for the maximum acceptance probability of a quantum measurement over unentangled states.<n>In classical terms, the goal is to maximize $langle(x otimes y), M (x otimes y)rangle$ over unit vectors $x,y$ where $0 preceq M preceq I$.
  arXiv  Detail & Related papers  (2026-08-10T19:04:15Z)
• Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory [65.64123585249297]
  We prove two lower bounds for the first order complexity of minimizing a $d$-dimensional $1$-Lipschitz convex function over the unit ball with $m$ bits of memory.<n>We first show that any such (possibly randomized) algorithm must make $tilde(fracd2sqrtm)$ oracle queries.<n>For deterministic optimization algorithms, we show that $tilde(mind1.6,fracd8/3m2/3)$ queries are required.
  arXiv  Detail & Related papers  (2026-07-21T00:40:59Z)
• Learning Multinomial Logits in $O(n \log n)$ time [56.23331174813387]
  A Multinomial Logit (MNL) model is composed of a finite universe of items $[n]=1,..., n$, each assigned a positive weight.<n>A query specifies an admissible subset -- called a slate -- and the model chooses one item from that slate with probability proportional to its weight.<n>This query model is also known as the Plackett-Luce model or conditional sampling oracle in the literature.
  arXiv  Detail & Related papers  (2026-01-07T22:07:44Z)
• Actively Learning Halfspaces without Synthetic Data [34.777547976926456]
  We design efficient algorithms for learning halfspaces without point synthesis.<n>As a corollary, we obtain an optimal $O(d + log n)$ query deterministic learner for axis-aligned halfspaces.<n>Our algorithm solves the more general problem of learning a Boolean function $f$ over $n$ elements which is monotone under at least one of $D$ provided orderings.
  arXiv  Detail & Related papers  (2025-09-25T07:39:25Z)
• Local Quantum Search Algorithm for Random $k$-SAT with $Ω(n^{1+ε})$ Clauses [0.0]
  We show that max-k-SSAT is the computational algorithm on average when $m=Omega(n2+delta+epsilon)$ based on the average-case complexity theory. We also prove that max-k-SSAT is on average when $m=Omega(n2+delta+epsilon)$ based on the average-case complexity theory.
  arXiv  Detail & Related papers  (2024-03-05T15:03:47Z)
• Exact Quantum Query Algorithms Outperforming Parity -- Beyond The Symmetric functions [3.652509571098291]
  We first obtain optimal exact quantum query algorithms ($Q_algo(f)$) for a direct sum based class of $Omega left( 2fracsqrtn2 right)$ non-symmetric functions. We show that query complexity of $Q_algo$ is $lceil frac3n4 rceil$ whereas $D_oplus(f)$ varies between $n-1$ and $lceil frac3n4 rce
  arXiv  Detail & Related papers  (2020-08-14T12:17:48Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)
• A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
  Given a discrete probability measure supported on $N$ atoms and a set of $n$ real-valued functions, there exists a probability measure that is supported on a subset of $n+1$ of the original $N$ atoms. We give a simple geometric characterization of barycenters via negative cones and derive a randomized algorithm that computes this new measure by "greedy geometric sampling" We then study its properties, and benchmark it on synthetic and real-world data to show that it can be very beneficial in the $Ngg n$ regime.
  arXiv  Detail & Related papers  (2020-06-02T16:38:36Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution. We show that the constraint of local differential privacy incurs an exponential increase in cost. Our algorithms result in exponential improvements on the round complexity of previous methods.
  arXiv  Detail & Related papers  (2020-02-21T18:30:48Z)
• Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm [100.11971836788437]
  We study the fixed-support Wasserstein barycenter problem (FS-WBP) We develop a provably fast textitdeterministic variant of the celebrated iterative Bregman projection (IBP) algorithm, named textscFastIBP.
  arXiv  Detail & Related papers  (2020-02-12T03:40:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.