{{Short description|Theoretical problem}} {{distinguish|Collision detection 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:<ref>{{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}}</ref> given <math>n</math> even and a function <math>f:\,\{1,\ldots,n\}\rightarrow\{1,\ldots,n\}</math>, 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 <math>f(i)</math> for any <math>i\in\{1,\ldots,n\}</math>. 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 <math display="inline">\frac{n}{2}+1</math> queries, and in general distinguishing r-to-1 functions from 1-to-1 functions requires <math display="inline">\frac{n}{r} + 1</math> queries.
This is a straightforward application of the pigeonhole principle: if a function is r-to-1, then after <math display="inline">\frac{n}{r} + 1</math> queries we are guaranteed to have found a collision. If a function is 1-to-1, then no collision exists. Thus, <math display="inline">\frac{n}{r} + 1</math> queries suffice. If we are unlucky, then the first <math>n/r</math> queries could return distinct answers, so <math display="inline">\frac{n}{r} + 1</math> 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 <math>\Theta(\sqrt{n})</math> queries.
== Quantum solution == The BHT algorithm, which uses Grover's algorithm, solves this problem optimally by only making <math>O(n^{1/3})</math> queries to ''f''. The matching lower bound of <math>\Omega(n^{1/3})</math> was proved by Aaronson and Shi using the polynomial method.<ref>{{cite journal | last1=Aaronson | first1=Scott | last2=Shi | first2=Yaoyun | title=Quantum lower bounds for the collision and the element distinctness problems | journal=Journal of the ACM | volume=51 | issue=4 | date=2004 | issn=0004-5411 | doi=10.1145/1008731.1008735 | pages=595–605 | url=https://dl.acm.org/doi/10.1145/1008731.1008735 | url-access=subscription }}</ref>
== References ==
<references/>
Category:Algorithms Category:Polynomial-time problems