Collision problem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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:[1] 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[edit]

Deterministic[edit]

Solving the 2-to-1 version deterministically requires n/2+1 queries, and in general distinguishing r-to-1 functions from 1-to-1 functions requires n/r+1 queries.

This is a straightforward application of the pigeonhole principle: if a function is r-to-1, then after n/r+1 queries we are guaranteed to have found a collision. If a function is 1-to-1, then no collision exists. Thus,  n/r+1 queries suffice. If we are unlucky, then the first n/r queries could return distinct answers, so  n/r+1 queries is also necessary.

Randomized[edit]

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[edit]

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

References[edit]

  1. ^ Scott Aaronson (2004). Limits on Efficient Computation in the Physical World (PDF).