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
We are only allowed to make queries about the value of
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.
Solving the 2-to-1 version deterministically requires
This is a straightforward application of the pigeonhole principle: if a function is r-to-1, then after
queries we are guaranteed to have found a collision.
If a function is 1-to-1, then no collision exists.
queries could return distinct answers, so
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
The BHT algorithm, which uses Grover's algorithm, solves this problem optimally by only making