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 $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.

Classical Solution

Clearly, for the 2-to-1 version, we would need to make at most $n/2+1$ queries to determine the answer. If the function is 2-to-1, then we know that the image of $\{1,\ldots ,n\}$ under f must contain exactly half of the members of that set. After making $n/2$ distinct queries we therefore have the entire image of f iff it is 2-to-1. The very next distinct query settles it: if we get a number that is already in our image set, then f must be 2-to-1 and if we do not, then f must be 1-to-1.