Collision problem

Not to be confused with Collision detection problem.

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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} even and a function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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.

Classical 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \frac{n}{r} + 1} queries suffice. If we are unlucky, then the first $n/r$ queries could return distinct answers, so Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Theta(\sqrt{n})} queries.

Quantum solution

The BHT algorithm, which uses Grover's algorithm, solves this problem optimally by only making Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n^{1/3})} queries to f.