Name
Abstract | ||
|---|---|---|
Abstract: We present several applications of quantum amplitude amplification to finding claws and collisions in ordered or unordered functions. Our algorithms generalize those of Brassard, Hyer, and Tapp, and imply an O(N^{3/4} log N) quantum upper bound for the element distinctness problem in the comparison complexity model. This contrasts with \Theta(N log N) classical complexity. We also prove a lower bound of \Omega(\sqrt N) comparisons for this problem and derive bounds for a number of related problems. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1137/S0097539702402780 | IEEE Conference on Computational Complexity |
Keywords | DocType | Volume |
n log,comparison complexity model,acm sigact news,quantum query complexity,classical complexity,classical world,element distinctness,element distinctness problem,quantum algorithms,derive bound,unordered function,related problem,sqrt n,quantum amplitude amplification,quantum world element distinctness,collision problem,computational complexity,quantum computing,upper bound,quantum mechanics,lower bound | Journal | 34 |
Issue | ISSN | Citations |
6 | 0097-5397 | 45 |
PageRank | References | Authors |
4.05 | 20 | 7 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Harry Buhrman | 1 | 1607 | 117.99 |
| Ronald de Wolf | 2 | 1265 | 86.93 |
| Christoph Dürr | 3 | 592 | 74.64 |
| Mark Heiligman | 4 | 89 | 6.72 |
| Peter H"yer | 5 | 45 | 4.05 |
| Frédéric Magniez | 6 | 570 | 44.33 |
| Miklos Santha | 7 | 728 | 92.42 |