⚛️ quantum physics

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

This paper establishes tight time-space lower bounds for collision finding and element distinctness under label symmetry by developing a space-sensitive compressed oracle technique, proving that any such algorithm requires $T=\Omega(N^{1/3})$ queries and $T^2S=\Omega(N\log N)$ resources, thereby confirming the optimality of existing quantum algorithms like BHT and Ambainis's quantum walk within this class.

Original authors: Frédéric Magniez, Sebastian Zur

Published 2026-09-11

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Frédéric Magniez, Sebastian Zur

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the digital world, security often relies on a simple but powerful idea: making it easy to create a unique digital fingerprint for a piece of data, but nearly impossible to find two different pieces of data that produce the same fingerprint. This is the job of a hash function, a mathematical tool that turns any input into a fixed-size string of characters. If two different inputs create the same output, it is called a collision. Finding such a collision is the starting point for many cyberattacks, so modern cryptography is built on the assumption that finding them is too difficult to be practical.

For decades, scientists have known that a classical computer, the kind we use every day, would need to check a vast number of possibilities to find a collision, a task that grows exponentially harder as the data gets larger. However, the theoretical arrival of quantum computers changed the landscape. These machines use the strange laws of quantum mechanics to explore many possibilities at once. A famous quantum method, known as the BHT algorithm, showed that a quantum computer could find a collision much faster than any classical machine, but with a catch: it required a massive amount of memory to store the results of its calculations. This created a puzzle for researchers. If memory is the bottleneck, how much memory does a quantum computer actually need to keep its speed advantage? Is there a fundamental tradeoff where saving memory forces the computer to slow down, or can it somehow have both speed and efficiency?

A team of researchers at CNRS and Université Paris Cité has now answered this question, but only for a specific and very natural class of quantum strategies. They proved that for any algorithm that treats the output labels of a function as interchangeable—meaning the computer does not care if a result is labeled "A" or "B," only that two results are the same—there is a strict limit on how much memory can be saved without sacrificing speed. Their findings show that to find a collision in a random function, a quantum computer must use a number of steps and a specific amount of memory that are mathematically linked. If the computer tries to use less memory, it must take significantly more steps to succeed. Conversely, if it wants to be fast, it must dedicate a certain amount of memory to the task.

The researchers did not just guess at this limit; they derived it with mathematical certainty for this class of algorithms. They showed that the relationship between time and space is not arbitrary but follows a precise rule. If an algorithm uses a certain number of steps, the memory it requires cannot be arbitrarily small. Specifically, they found that the product of the square of the time taken and the amount of memory used must be at least a certain large number. This result is significant because it matches the performance of the best-known quantum algorithms currently in existence. The famous BHT algorithm and another method based on quantum walks both operate right at this theoretical edge, meaning they are already as efficient as possible within these constraints. No one can invent a better version of these specific types of algorithms that uses less memory while keeping the same speed.

To reach this conclusion, the team developed a new way of looking at how quantum computers store information. Instead of tracking the computer's state as a single snapshot, they viewed it as a constantly evolving cloud of possibilities, a superposition of many different databases. They realized that because the algorithm treats all output labels as equal, the information it holds must be symmetric. By using advanced mathematics to analyze this symmetry, they discovered that a quantum computer with limited memory can only hold onto a very small number of collision-free entries in its database. Once the computer tries to hold more information than its memory allows, the symmetry of the problem forces the information to become garbled or lost. This loss of information is what slows the computer down, creating the unavoidable tradeoff between time and space.

The study also refined the understanding of a specific type of mathematical structure called an arrangement graph, which describes how different sets of data points are connected. The researchers calculated the exact properties of the lowest energy states of these graphs, a detail that had been estimated before but never precisely determined. This precise calculation was the key that unlocked the proof, allowing them to quantify exactly how much information a limited-memory machine could retain.

While the proof applies to a specific class of algorithms where the output labels are treated as interchangeable, the researchers argue that this restriction is not a weakness. In the real world, the labels on a hash function's output usually have no intrinsic meaning; they are just arbitrary symbols. Therefore, any algorithm that tries to treat one label differently from another would be relying on a coincidence rather than a fundamental property of the problem. The fact that the most efficient known algorithms already fit this description suggests that the tradeoff found by the researchers is likely the ultimate limit for quantum collision finding.

This work provides a clear boundary for the future of quantum cryptography. It tells us that to break current hash-based security systems, a quantum computer will not just need to be fast; it will also need to be large. The memory requirements are not just a technical hurdle but a fundamental law of the problem. This insight helps security experts understand how to design systems that remain safe even in a future where powerful quantum computers exist. By knowing exactly how much memory is needed to break a code, we can choose security parameters that are large enough to make the attack impossible, even for a machine with the best possible quantum strategy. The paper closes a major chapter in the theory of quantum algorithms, turning a long-standing open question into a solved equation for a broad and important class of problems.

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

Problem Statement

The paper addresses a fundamental open problem in quantum query complexity: determining the optimal tradeoff between the number of queries ( $T$ ) and the amount of memory ( $S$ ) required to find a collision in a uniformly random function $f: [M] \to [N]$ .

While the BHT algorithm [BHT97] achieves a query complexity of $O(N^{1/3})$ using $O(N^{1/3})$ classical memory with quantum access (QRACM), and a logarithmic-space Grover search requires $O(\sqrt{N})$ queries, the precise relationship between $T$ and $S$ for intermediate space regimes has remained unresolved. Specifically, it is unknown whether an algorithm can find a collision with significantly fewer queries than $O(N^{1/3})$ if it is allowed more space, or conversely, if it can succeed with logarithmic space without the quadratic penalty of Grover's search.

The authors focus on the class of label-symmetric algorithms. An algorithm is label-symmetric if its strategy treats the output labels of the function as interchangeable; formally, its behavior is invariant under any permutation of the range $[N]$ . This restriction is motivated by the fact that both the uniform input distribution and the collision condition are inherently invariant under range relabeling, suggesting that treating specific labels differently offers no intrinsic advantage.

Methodology

The proof combines three primary technical ingredients:

The Compressed Oracle Technique:
The authors utilize the compressed oracle technique (originally by Zhandry [Zha19] and adapted for collision finding by Hamoudi and Magniez [HM23]). In this framework, the algorithm's knowledge of the random function is represented not as a classical table, but as a superposition of "databases." Initially, the database contains only empty cells ( $\perp$ ). As the algorithm makes queries, the superposition evolves to include entries $(x, f(x))$ . The progress of the algorithm is tracked by the amplitude of the state on databases containing at least one collision.
Label Symmetry and Representation Theory:
The core innovation is the integration of label symmetry into the compressed oracle analysis. The authors analyze the reduced state of the input register, $\rho_I$ . For a label-symmetric algorithm using $S$ qubits, the Schmidt rank of the joint state is at most $2^S$ . Consequently, the orbit of any vector in the support of $\rho_I$ under the symmetric group $S_N$ (permuting range labels) spans a space of dimension at most $2^S$ .
The authors define a subspace of "collision-free compressed databases" with $s$ occupied entries, denoted as $C^\perp_s \cap W^{\otimes s}$ , where $C^\perp_s$ represents states with distinct values and $W^{\otimes s}$ represents states compatible with the compressed oracle (orthogonal to the "all-zero" Fourier state).
Spectral Analysis of Arrangement Graphs:
To bound the dimension of the space $C^\perp_s \cap W^{\otimes s}$ , the authors relate it to the kernel of a deletion map $D$ , which is shown to be the $(-s)$ -eigenspace of an arrangement graph $A_{N,s}$ . The vertices of this graph are injective $s$ -tuples, and edges connect tuples differing in exactly one coordinate.
Using representation theory of the symmetric group, the authors prove that for $N \ge 2s$ , the $(-s)$ -eigenspace decomposes into irreducible representations (Specht modules) of shape $(N-s, \mu)$ . Crucially, they establish that the dimension of these representations grows rapidly with $N$ and $s$ , specifically exceeding $2^S$ whenever $s > 2S / \log_2 N$ .
Furthermore, the authors sharpen previous spectral results for these graphs, identifying the exact spectral gap above the least eigenvalue as $N - 2s + 2$ . This gap controls the discrepancy between the projection onto collision-free states and the projection onto valid compressed database states.

Key Contributions and Results

1. Time-Space Lower Bounds for Collision Finding

The paper proves that any label-symmetric algorithm finding a collision in a random function $f: [M] \to [N]$ with constant probability must satisfy:
$T = \Omega(N^{1/3})$
$T^2 S = \Omega(N \log N)$
These bounds are derived by showing that an algorithm with limited space $S$ cannot maintain a large collision-free database in the compressed oracle model. Specifically, the amplitude on databases with $s$ entries is suppressed if $s$ exceeds the threshold $2S / \log_2 N$ , because the corresponding subspace requires more qubits than available to represent the necessary symmetry orbits.

2. Tightness of the Bounds

The authors demonstrate that these lower bounds are tight by showing they are matched by existing algorithms:

BHT Algorithm: For $M=N$ , the BHT algorithm with table size $r$ uses $T = O(r + \sqrt{N/r})$ queries and $S = O(r \log N)$ space. Setting $r = N^{1/3}$ yields $T = O(N^{1/3})$ and $T^2 S = O(N \log N)$ .
Ambainis's Quantum Walk: For the search version of Element Distinctness on $f: [n] \to [n^2]$ , the quantum walk algorithm satisfies $T = \Omega(n^{2/3})$ and $T^2 S = \Omega(n^2 \log n)$ .

3. Extension to Element Distinctness

As a direct consequence, the paper establishes the optimal tradeoff for the search version of Element Distinctness (finding a collision in a non-injective function $f: [n] \to [n^2]$ ):
$T = \Omega(n^{2/3})$
$T^2 S = \Omega(n^2 \log n)$
The authors note that while the decision version of Element Distinctness (deciding injectivity) has the same asymptotic bounded-error quantum query complexity as the search version, their lower bound is explicitly proven for the search version where the full collision triple $(x_1, x_2, y)$ must be output. This result matches the performance of Ambainis's algorithm, proving its optimality within the class of label-symmetric algorithms for the search problem.

4. Technical Advance: Arrangement Graph Spectrum

The paper provides a refined spectral analysis of arrangement graphs $A_{N,s}$ . It identifies the exact least eigenvalue ( $-s$ ) and the exact spectral gap ( $N - 2s + 2$ ) for the regime $N \ge 2s$ . This result improves upon previous bounds by Chen, Ghorbani, and Wong [CGW13] and Araujo and Bratten [AB17], providing the precise gap necessary to bound the projection errors in the time-space tradeoff proof.

Significance and Claims

The authors claim to resolve the optimal query-space tradeoff for collision finding and the search version of Element Distinctness within the class of label-symmetric algorithms. They argue that this restriction is natural because the problem instances (uniform distribution and collision condition) are themselves label-symmetric.

The paper explicitly states that removing the label-symmetry assumption remains a major open problem. While symmetrizing an arbitrary algorithm is possible, standard methods require storing a random permutation, which consumes $\Theta(N \log N)$ space and thus invalidates the space parameter $S$ tracked by the lower bound. The authors note that a space-preserving symmetrization argument or a proof avoiding symmetry altogether would be required to extend these results to all quantum algorithms.

The work highlights the critical role of memory in quantum algorithms, particularly for problems like collision finding where the quantum speedup is heavily dependent on the ability to store and access a large database. The results suggest that without sufficient memory (specifically, space scaling with $N^{1/3}$ ), the cubic-root quantum speedup cannot be maintained, and the algorithm is forced toward the quadratic Grover limit.