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:, we are promised that f is either 1-to-1. 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

queries.

This is a straightforward application of the pigeonhole principle queries is also necessary.

Randomized

If we allow randomness, the problem is easier. By the birthday paradox queries.

Quantum solution

The BHT algorithm, which uses Grover's algorithm queries to f was proved by Aaronson and Shi using the polynomial method.

References