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.
Categories: quant-ph