Quantum Lower Bound for the Collision Problem
| dc.creator | Aaronson, Scott | |
| dc.date | 2001-11-20 | |
| dc.date.accessioned | 2026-07-07T06:03:03Z | |
| dc.date.available | 2026-07-07T06:03:03Z | |
| dc.description | The collision problem is to decide whether a function X:{1,..,n}->{1,..,n} is one-to-one or two-to-one, given that one of these is the case. We show a lower bound of Theta(n^{1/5}) on the number of queries needed by a quantum computer to solve this problem with bounded error probability. The best known upper bound is O(n^{1/3}), but obtaining any lower bound better than Theta(1) was an open problem since 1997. Our proof uses the polynomial method augmented by some new ideas. We also give a lower bound of Theta(n^{1/7}) for the problem of deciding whether two sets are equal or disjoint on a constant fraction of elements. Finally we give implications of these results for quantum complexity theory. | |
| dc.description | 10 pages plus 4 page appendix, no figures. Submitted to STOC'2002 | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0111102 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0111102 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/89846 | |
| dc.subject | Quantum Physics | |
| dc.subject | Computational Complexity | |
| dc.title | Quantum Lower Bound for the Collision Problem | |
| dc.type | text |