Quantum Lower Bound for the Collision Problem

Details Quantum Lower Bound for the Collision Problem Quantum Lower Bound for the Collision Problem

2001-11-20

arxiv.org/abs/quant-ph/0111102v1

Physics

Quantum Physics

10 pages plus 4 page appendix, no figures. Submitted to STOC'2002

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Quantum Lower Bound for the Collision Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantum Lower Bound for the Collision Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Lower Bound for the Collision Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-275465