loading...
Quantum Algorithms for Element Distinctness
Chicago, Illinois June 18-June 21
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2001.93388016th Annual IEEE Conference on Comput ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
Harry Buhrman, Ronald de Wolf, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklos Santha, "Quantum Algorithms for Element Distinctness," Computational Complexity, Annual IEEE Conference on, pp. 0131, 16th Annual IEEE Conference on Computational Complexity (CCC'01), 2001.
 
 
BibTex
x
 
@article{ 10.1109/CCC.2001.933880,
author = {Harry Buhrman and Ronald de Wolf and Christoph Dürr and Mark Heiligman and Peter Høyer and Frédéric Magniez and Miklos Santha},
title = {Quantum Algorithms for Element Distinctness},
journal ={Computational Complexity, Annual IEEE Conference on},
volume = {0},
year = {2001},
isbn = {0-7695-1053-1},
pages = {0131},
doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2001.933880},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Computational Complexity, Annual IEEE Conference on
TI - Quantum Algorithms for Element Distinctness
SN - 0-7695-1053-1
SP
EP
A1 - Harry Buhrman,
A1 - Ronald de Wolf,
A1 - Christoph Dürr,
A1 - Mark Heiligman,
A1 - Peter Høyer,
A1 - Frédéric Magniez,
A1 - Miklos Santha,
PY - 2001
VL - 0
JA - Computational Complexity, Annual IEEE Conference on
ER -
 
Christoph Dürr, Universit? Paris-Sud
Peter Høyer, University of Calgary
Miklos Santha, CNRS-LRI
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, H?yer, 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.
Citation:
Harry Buhrman, Ronald de Wolf, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklos Santha, "Quantum Algorithms for Element Distinctness," ccc, pp.0131, 16th Annual IEEE Conference on Computational Complexity (CCC'01), 2001
Usage of this product signifies your acceptance of the Terms of Use.