Encyclopedia

Collision problem

Theoretical problem

Wikipedia contributorsAdapted for Fathomly · View authors

1 min read
Source updated April 27, 2026

The r-to-1 collision problem is an important theoretical problem in complexity theory, quantum computing, and computational mathematics. The collision problem most often refers to the 2-to-1 version: given $n$ even and a function $f:\,\{1,\ldots ,n\}\rightarrow \{1,\ldots ,n\}$ , we are promised that f is either 1-to-1 or 2-to-1. We are only allowed to make queries about the value of $f(i)$ for any $i\in \{1,\ldots ,n\}$ . The problem then asks how many such queries we need to make to determine with certainty whether f is 1-to-1 or 2-to-1.

01Classical solutions

Deterministic

Solving the 2-to-1 version deterministically requires ${\textstyle {\frac {n}{2}}+1$ queries, and in general distinguishing r-to-1 functions from 1-to-1 functions requires ${\textstyle {\frac {n}{r}}+1$ queries.

This is a straightforward application of the pigeonhole principle: if a function is r-to-1, then after ${\textstyle {\frac {n}{r}}+1$ queries we are guaranteed to have found a collision. If a function is 1-to-1, then no collision exists. Thus, ${\textstyle {\frac {n}{r}}+1$ queries suffice. If we are unlucky, then the first $n/r$ queries could return distinct answers, so ${\textstyle {\frac {n}{r}}+1$ queries is also necessary.

Randomized

If we allow randomness, the problem is easier. By the birthday paradox, if we choose (distinct) queries at random, then with high probability we find a collision in any fixed 2-to-1 function after $\Theta ({\sqrt {n}})$ queries.

02Quantum solution

The BHT algorithm, which uses Grover's algorithm, solves this problem optimally by only making $O(n^{1/3})$ queries to f. The matching lower bound of $\Omega (n^{1/3})$ was proved by Aaronson and Shi using the polynomial method.

Watch videos about Collision problemExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Collision problem”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.