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
Contents
Deterministic
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
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
Quantum Solution
The BHT algorithm, which uses Grover's algorithm, solves this problem optimally by only making