arXiv:quant-ph/0007016 · SIAM Journal on Computing
Quantum Algorithms for Element Distinctness
Harry Buhrman, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklós Sántha, Ronald de Wolf
Abstract
We present several applications of quantum amplitude amplification for deciding whether all elements in the image of a given function are distinct, for finding an intersection of two sorted tables, and for finding a triangle in a graph. Our techniques generalize and improve those of Brassard, Hoyer, and Tapp [ACM SIGACT News, 28 (1997), pp. 14--19]. This shows that in the quantum world element distinctness is significantly easier than sorting, in contrast to the classical world.