Collision problem

The collision problem is a theoretical question studied in complexity theory, quantum computing and computational mathematics that asks how many queries are needed to determine whether a given function is one-to-one or exactly two-to-one, under the promise that it is one or the other. Its most studied form is the two-to-one version, where an algorithm may query the function at chosen points and must decide, using as few queries as possible, whether every value is hit by a unique input or whether every value is hit by exactly two inputs. The problem is significant because it exposes a real separation between classical and quantum computation: quantum algorithms can solve the collision problem using substantially fewer queries than any classical algorithm requires, making it a standard example used to demonstrate genuine quantum speedups for query-based problems rather than merely conjectured ones.