Quantum Algorithms for Element Distinctness

Details Quantum Algorithms for Element Distinctness Quantum Algorithms for Element Distinctness

2000-07-06

arxiv.org/abs/quant-ph/0007016v2

Physics

Quantum Physics

15 pages. Supersedes quant-ph/007016v1 and quant-ph/0006136

Scientific paper

We present several applications of quantum amplitude amplification to finding claws and collisions in ordered or unordered functions. Our algorithms generalize those of Brassard, Hoyer, and Tapp, and imply an O(N^{3/4} log N) quantum upper bound for the element distinctness problem in the comparison complexity model (contrasting with Theta(N log N) classical complexity). We also prove a lower bound of Omega(N^{1/2}) comparisons for this problem and derive bounds for a number of related problems.

Affiliated with

Also associated with

No associations

Rating

Quantum Algorithms for Element Distinctness 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 Algorithms for Element Distinctness, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Algorithms for Element Distinctness will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-18044