# Collision problem

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Collision_problem
> Markdown URL: https://mediated.wiki/source/Collision_problem.md
> Source: https://en.wikipedia.org/wiki/Collision_problem
> Source revision: 1351325255
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Theoretical problem

Not to be confused with [Collision detection problem](/source/Collision_detection_problem).

The **r-to-1 collision problem** is an important theoretical problem in [complexity theory](/source/Computational_complexity_theory), [quantum computing](/source/Quantum_computing), and [computational mathematics](/source/Computational_mathematics). The collision problem most often refers to the 2-to-1 version:[1] given n {\displaystyle n} even and a function f : { 1 , … , n } → { 1 , … , n } {\displaystyle f:\,\{1,\ldots ,n\}\rightarrow \{1,\ldots ,n\}} , we are promised that f is either [1-to-1](/source/One-to-one_function) or 2-to-1. We are only allowed to make queries about the value of f ( i ) {\displaystyle f(i)} for any i ∈ { 1 , … , n } {\displaystyle 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 n 2 + 1 {\textstyle {\frac {n}{2}}+1} queries, and in general distinguishing r-to-1 functions from 1-to-1 functions requires n r + 1 {\textstyle {\frac {n}{r}}+1} queries.

This is a straightforward application of the [pigeonhole principle](/source/Pigeonhole_principle): if a function is r-to-1, then after n r + 1 {\textstyle {\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, n r + 1 {\textstyle {\frac {n}{r}}+1} queries suffice. If we are unlucky, then the first n / r {\displaystyle n/r} queries could return distinct answers, so n r + 1 {\textstyle {\frac {n}{r}}+1} queries is also necessary.

### Randomized

If we allow randomness, the problem is easier. By the [birthday paradox](/source/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 Θ ( n ) {\displaystyle \Theta ({\sqrt {n}})} queries.

## Quantum solution

The [BHT algorithm](/source/BHT_algorithm), which uses [Grover's algorithm](/source/Grover's_algorithm), solves this problem optimally by only making O ( n 1 / 3 ) {\displaystyle O(n^{1/3})} queries to *f*. The matching lower bound of Ω ( n 1 / 3 ) {\displaystyle \Omega (n^{1/3})} was proved by Aaronson and Shi using the polynomial method.[2]

## References

1. **[^](#cite_ref-1)** [Scott Aaronson](/source/Scott_Aaronson) (2004). ["Limits on Efficient Computation in the Physical World"](http://www.scottaaronson.com/thesis.pdf) (PDF).

1. **[^](#cite_ref-2)** Aaronson, Scott; Shi, Yaoyun (2004). ["Quantum lower bounds for the collision and the element distinctness problems"](https://dl.acm.org/doi/10.1145/1008731.1008735). *Journal of the ACM*. **51** (4): 595–605. [doi](/source/Doi_(identifier)):[10.1145/1008731.1008735](https://doi.org/10.1145%2F1008731.1008735). [ISSN](/source/ISSN_(identifier)) [0004-5411](https://search.worldcat.org/issn/0004-5411).

---
Adapted from the Wikipedia article [Collision problem](https://en.wikipedia.org/wiki/Collision_problem) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Collision_problem?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.