Quantum complexity of finding collisions in complex functions determined
Tight Quantum Query Bounds for Collision Finding over Arbitrary Bounded Types
Computational Complexity
Summary
This work figures out how hard it is for a quantum computer to find a repeated output value — called a collision — in a function with many inputs, even when the outputs are grouped in complicated ways. The authors find the precise number of queries a quantum algorithm must make to solve this problem depending on how the outputs are distributed, resolving a previously open question. They develop new mathematical tools to prove these limits and also design algorithms that match these limits exactly. Their results connect different known quantum problems, improving understanding of quantum search tasks.
What this means in practice
- •For quantum algorithm designers: Use precise quantum query limits to optimize algorithms for detecting repeated outputs in complex functions, avoiding inefficiencies in query resources.
- •For quantum cryptographers: Understand the quantum difficulty of finding collisions in structured functions, informing security assessments of cryptographic hash functions against quantum attacks.
A theory result. No direct application yet.
Authors
Tianci Peng, Shiqi Hou, Xiaoyang Dong
Abstract
We determine the bounded-error quantum query complexity of finding one $r$-collision in an $N$-input function of prescribed type, which specifies all equality-class sizes. For every fixed maximum class size and collision order, we give a tight bound as the maximum of scales determined by the numbers of classes of size at least $2,\ldots,r$. The lower bound holds for a uniformly random function of that type, and a matching algorithm succeeds on every such function. No intermediate class size is required to occur, and every feasible output alphabet is allowed. The characterization connects the abundant-collision regime associated with set equality to the sparse-target regime of $k$-distinctness. In particular, finding the unique $(k+1)$-collision in type $(k^n,k+1)$ has complexity $Θ_k(N^{3/4-1/[4(2^{k+1}-1)]})$, where $N=kn+k+1$, resolving an open problem of Belovs. For the lower bound, we introduce a filtered compressed permutation oracle that projects onto a harmonic database subspace after each complete function query. Its $O(T/N)$ comparison error over $T$ queries overcomes the square-root limitation of the unfiltered process. Hidden capacity extensions and moment estimates retain the populations at each intermediate collision order. Matching upper bounds use sampled collision lists and colored adaptive learning graphs, with a coherent decision-to-search conversion that avoids logarithmic overhead. We also give an alternative nested quantum-walk algorithm for three-collision search, matching the bound up to polylogarithmic factors.