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{{cite web |author = Scott Aaronson |authorlink = Scott Aaronson|title = Limits on Efficient Computation in the Physical World |year = 2004|url = http://www.scottaaronson.com/thesis.pdf}}: given $n$ even and a function $f:\,\{1,\ldots,n\}\rightarrow\{1,\ldots,n\}$ , 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 $f(i)$ for any $i\in\{1,\ldots,n\}$ . 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 $\frac{n}{2}+1$ queries, and in general distinguishing r-to-1 functions from 1-to-1 functions requires $\frac{n}{r} + 1$ queries.

This is a straightforward application of the pigeonhole principle: if a function is r-to-1, then after $\frac{n}{r} + 1$ queries we are guaranteed to have found a collision. If a function is 1-to-1, then no collision exists. Thus, $\frac{n}{r} + 1$ queries suffice. If we are unlucky, then the first $n/r$ queries could return distinct answers, so $\frac{n}{r} + 1$ 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 $\Theta(\sqrt{n})$ queries.

Quantum solution

The BHT algorithm, which uses Grover's algorithm, solves this problem optimally by only making $O(n^{1/3})$ queries to f.

The matching lower bound of $\Omega(n^{1/3})$ was proved by Aaronson and Shi using the polynomial method{{cite web |author = Scott Aaronson and Yaoyun Shi|title = Quantum lower bounds for the collision and the element distinctness problems |year = 2004|url = https://doi.org/10.1145/1008731.1008735}}.

References

Category:Algorithms

Category:Polynomial-time problems