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: given formula_1 even and a function formula_2, 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 formula_3 for any formula_4. 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 formula_5  queries, and in general distinguishing r-to-1 functions from 1-to-1 functions requires formula_6 queries. This is a straightforward application of the pigeonhole principle: if a function is r-to-1, then after formula_6 queries we are guaranteed to have found a collision. If a function is 1-to-1, then no collision exists. Thus, formula_6 queries suffice. If we are unlucky, then the first formula_9 queries could return distinct answers, so formula_6 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 formula_11 queries. Quantum solution. The BHT algorithm, which uses Grover's algorithm, solves this problem optimally by only making formula_12 queries to "f".