⚛️ quantum physics

Quantum Lower Bounds for Collision Problems

This paper establishes tight quantum query lower bounds for finding and testing collisions in $k$ -to-one functions, demonstrating that adaptive algorithms are limited by $\Omega_k(n^{1/2-1/(2(2^k-1))})$ while one-round non-adaptive algorithms face a stronger $\Omega_k(n^{1-1/k})$ barrier even with entangled parallel queries, thereby matching known upper bounds and resolving a longstanding open question regarding non-adaptive $k$ -to-one testing.

Original author: Pan Peng, Jingyu Wu

Published 2026-11-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original author: Pan Peng, Jingyu Wu

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 author. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of computing, some problems are easy to solve if you have a map, but nearly impossible if you are navigating by feel alone. This is the realm of query complexity, a field that measures how many times a computer must peek at a hidden list of data to find a specific answer. Imagine a massive library where every book has a secret code on its spine, and you are looking for a group of books that all share the exact same code. In a standard library, finding such a match is difficult because the codes are scattered randomly. But in the quantum world, where computers can exist in many states at once, the rules of the game change. Scientists have long wondered if quantum computers could find these hidden matches significantly faster than classical machines, and whether the speed comes from the machine's ability to process information in parallel or from its ability to learn from each step and adjust its strategy for the next.

A team of researchers has now settled a long-standing debate about this specific type of search problem, known as finding a "collision" in a string of data. They proved that while quantum computers do offer a speed advantage, that advantage is strictly limited by how the computer is allowed to ask its questions. If the computer is forced to ask all its questions at once, in a single burst of parallel effort, it gains almost no advantage over a classical computer. The quantum speedup only appears when the computer is allowed to be adaptive: to ask a question, see the answer, and then use that information to decide what to ask next. The researchers demonstrated that without this step-by-step learning, even the most powerful quantum strategies fail to beat the efficiency of simple random sampling.

The problem they studied involves a string of data where every value appears exactly a fixed number of times, say $k$ times. The goal is to find the specific group of positions where these matching values sit. For a long time, it was known that a classical computer needs to check a certain number of positions to find a match, a number that grows based on the total size of the data and the group size. Quantum researchers had previously developed a clever method that used fewer checks by building up small matches and then combining them, but it was unclear if this method was the absolute best possible, or if a different, more parallel approach could do even better. The new study establishes a hard limit, proving that no quantum algorithm can beat the known best method unless it is allowed to adapt its questions based on previous answers.

To reach this conclusion, the researchers constructed a mathematical model that treats the hidden data as a shuffled deck of cards. They simulated the process of a quantum computer trying to learn about this deck by asking questions. They found that when the computer asks all its questions simultaneously, the information it gathers is scattered and incomplete. Even though the quantum computer can hold many possibilities in its memory at once, the act of asking questions in parallel prevents it from connecting the dots between the answers. The researchers showed that the probability of the computer accidentally stumbling upon a full set of matching values in one go is so low that it cannot be improved upon, no matter how the quantum states are entangled or how the final measurement is performed.

The study also addressed a related question: can a quantum computer tell the difference between a list where every item is unique and a list where items repeat in groups, without actually finding the repeating groups? This is a simpler task, often called a testing problem. The researchers proved that even for this easier job, a quantum computer that asks all its questions at once cannot do better than a classical computer that simply picks random items and checks for duplicates. This result resolves a question that had been open for over a decade, confirming that the power of quantum parallelism has a hard ceiling when it comes to detecting these specific patterns.

The key to their proof was a technique that tracks exactly what the computer "knows" after each question. Instead of looking at the computer's complex internal state, they mapped the information onto a simple database of recorded answers. They showed that for a quantum computer to succeed, this database must eventually contain a complete set of matching positions. By carefully calculating how fast this database can grow, they demonstrated that without the ability to adjust questions based on previous answers, the database fills up too slowly to find a match within a reasonable number of steps. The only way to speed up the process is to let the computer use the results of one question to guide the next, effectively turning a blind search into a guided hunt.

This work does not just say what is possible; it explicitly rules out the idea that a single layer of parallel quantum queries could solve these problems efficiently. It confirms that the sequential nature of the best-known quantum algorithms is not a flaw in their design, but a fundamental requirement of the problem itself. The researchers' findings provide a clear boundary for the capabilities of quantum computers in this domain, showing that the "quantum advantage" is real but conditional. It depends entirely on the ability to learn and adapt, a feature that remains the most powerful tool in the quantum arsenal for solving these types of search puzzles.

Technical Summary: Quantum Lower Bounds for Collision Problems

1. Problem Statement

This paper investigates the quantum query complexity of collision problems under the exact $k$ -to-one promise. Given oracle access to a string $x \in \mathbb{Z}_q^n$ where $n = kN$ , the input is promised to be exactly $k$ -to-one: every symbol appearing in $x$ appears exactly $k$ times. The paper addresses two primary problems:

Promised $k$ -to-one Finding: The task is to output all $k$ positions forming a single block of equal values (a full $k$ -collision). This differs from random-function multicollision finding, where outputs may have arbitrary multiplicities.
$k$ -to-one Testing: A decision problem distinguishing between an injective input (all values distinct) and an exactly $k$ -to-one input.

The authors analyze these problems in two distinct quantum query models:

Adaptive: The algorithm may use information from previous oracle calls to determine subsequent queries.
Non-adaptive (One-round): The algorithm makes all queries in a single parallel layer. While queries within the layer may be arbitrarily entangled, no information from the layer can influence the preparation of a second layer.

2. Methodology

The proofs rely on a harmonic framework for analyzing quantum algorithms accessing a uniform random permutation, which is used to generate the hard input distributions.

2.1. Hard Distribution Construction

The authors reduce the collision problems to Permutation Bucket Finding. A uniformly random permutation $\pi \in S_n$ is used to generate a balanced $k$ -to-one input by partitioning the permutation's output slots into $N$ public buckets of size $k$ . The input value at index $i$ is determined by the bucket containing $\pi(i)$ . Finding a full $k$ -collision in the input corresponds to finding all positions mapping to a single bucket in the permutation.

2.2. Compressed Oracle and Encoding

The core technical tool is a compressed permutation oracle based on the work of Carolan [Car26], adapted for exact $k$ -to-one inputs.

Database Representation: The algorithm's knowledge is represented by a database of partial injections (input-output pairs).
Exact Encoding ( $V$ ): The authors construct an isometry $V$ that maps the permutation register to a database register. This encoding preserves the "permutation degree" (related to the number of queries) and utilizes harmonic subspaces (range-harmonic and domain-harmonic) to eliminate redundant directions in the database space (e.g., uniform extensions that carry no new information).
Error Bounds: The paper establishes tight bounds on the difference between the genuine permutation query and a "recording" query that updates the database. Specifically, they bound the error introduced by local recording queries outside the harmonic subspaces, showing it scales as $O(T^2/n)$ for adaptive algorithms and $O(\sqrt{T/n})$ for unprojected comparisons.

2.3. Proof Strategies

Adaptive Lower Bound: The proof adapts the partial-collision hierarchy of Liu and Zhandry [LZ19] to the permutation setting. It tracks the growth of "partial collisions" (buckets with $j$ recorded slots) through successive queries. By setting cutoffs on the number of partial collisions and bounding the amplitude that can cross these thresholds in a single query, they show that building a full $k$ -collision requires a specific number of queries. The proof uses a projected recording process (applying a domain projection $K_D$ after each query) to control simulation error.
Non-adaptive Lower Bound: For one-round algorithms, the gradual construction of collisions is unavailable. Instead, the authors analyze the state after a single parallel query layer directly. They utilize the orthogonality of algorithm vectors inherent in one-round queries (Lemma 3.1) to decompose the state. They then apply a static occupancy bound (Lemma 7.1) to show that the probability of recording a prescribed set of $k$ values in the database is bounded by $O((t/n)^k)$ , where $t$ is the number of queries. This bound holds even for entangled queries.
Decision Lower Bound: For $k$ -to-one Testing, the authors compare the algorithm's reduced states under four distributions: independent labels (Fun/Block $_k$ ) and distinct labels (Inj/Exact $_k$ ). They use the harmonic encoding to bound the trace distance between states with independent labels and those with distinct labels, showing the change is small ( $O(t/\sqrt{q})$ ).

3. Key Contributions and Results

3.1. Adaptive Promised $k$ -to-one Finding

The paper establishes a tight lower bound for adaptive quantum algorithms.

Result: Any quantum algorithm succeeding with constant probability requires $\Omega_k(n^{\alpha_k})$ queries, where $\alpha_k = \frac{1}{2} - \frac{1}{2(2k-1)}$ .
Significance: This matches the upper bound achieved by the adaptive algorithm of Liu and Zhandry [LZ19]. It confirms that the sequential dependence in their algorithm is essential and that no further quantum speedup is possible under the exact $k$ -to-one promise, even with unrestricted adaptivity.

3.2. Non-adaptive Promised $k$ -to-one Finding

The paper establishes a tight lower bound for one-round quantum algorithms.

Result: Any one-round quantum algorithm requires $\Omega_k(n^{1-1/k})$ parallel queries.
Significance: This matches the classical birthday sampling complexity. It demonstrates that entanglement alone in a single query layer is insufficient to achieve the quantum speedup seen in adaptive algorithms. The sequential dependence is a fundamental requirement for the speedup, not merely an artifact of specific algorithm designs.

3.3. Non-adaptive $k$ -to-one Testing

The paper resolves an open question regarding the non-adaptive complexity of distinguishing injective from $k$ -to-one inputs.

Result: Any one-round quantum algorithm requires $\Omega(\sqrt{n/k})$ queries.
Significance: This matches the classical complexity and answers the open question posed by Koiran, Landes, Portier, and Yao [KLPY10] for the case $k=2$ . The proof works for alphabet sizes $q \ge n$ , handling the constraint that distinct labels must be enforced.

4. Significance and Claims

The paper claims to provide a complete characterization of the quantum query complexity for these collision problems under the exact $k$ -to-one promise.

Separation of Models: The results clearly separate the power of adaptivity from the power of quantum coherence. While quantum coherence allows for speedups in adaptive settings (beating the classical $n^{1-1/k}$ barrier), it does not provide an asymptotic advantage in the non-adaptive (one-round) setting.
Optimality: The lower bounds are shown to be tight by matching existing upper bounds (Liu-Zhandry for adaptive, classical sampling for non-adaptive).
Methodological Advancement: The authors introduce a refined harmonic framework for compressed permutation oracles. This framework handles the dependencies inherent in exact $k$ -to-one inputs (where every value must appear exactly $k$ times), a setting where previous compressed oracle techniques for random functions (which assume independence) do not directly apply.
Comparison with Concurrent Work: The paper notes that concurrent work by Carolan and Majenz [CM26] and Kim [Kim26] improves compressed permutation oracle simulations. However, the authors argue their specific application of these tools—particularly the projected forward-query process for adaptive bounds and the static occupancy bound for one-round bounds—yields the tight lower bounds necessary for the exact $k$ -to-one promise.

The paper concludes by identifying open problems, specifically the full round hierarchy for $r \ge 2$ layers and the alphabet-size requirements for Search $k$ -Distinctness, but does not propose solutions to these within the current work.