Collision problem

From Wikipedia, the free encyclopedia

f:\,\{1,\ldots,n\}\rightarrow\{1,\ldots,n\}

Classical Solution

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 exist. 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.

\Theta(\sqrt{n})


Quantum Solution

To be worked on...


References

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