# Collision 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:[1] given ${\displaystyle n}$ even and a function ${\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 ${\displaystyle f(i)}$ for any ${\displaystyle 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.

## Bayagbag Condition

### Deterministic

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

This is a straightforward application of the pigeonhole principle: if a function is r-to-1, then after ${\displaystyle n/r+1}$ queries we are guaranteed to have found a collision. If a function is 1-to-1, then no collision exists. Thus, ${\displaystyle n/r+1}$ queries suffice. If we are unlucky, then the first ${\displaystyle n/r}$ queries could return distinct answers, so ${\displaystyle 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 ${\displaystyle \Theta ({\sqrt {n}})}$ queries.

## Quantum Solution

The BHT algorithm, which uses Grover's algorithm, solves this problem optimally by only making ${\displaystyle O(n^{1/3})}$ queries to f.