Quantum walk algorithm for element distinctness

We use quantum walks to construct a new quantum algorithm for element distinctness and its generalization. For element distinctness (the problem of finding two equal items among N given items), we get an O(N²3/) query quantum algorithm. This improves the previous O(N³4/) quantum algorithm of Buhrman et al. and matches the lower bound by Shi. We also give an O(N^k(k+1)/) query quantum algorithm for the generalization of element distinctness in which we have to find k equal items among N items.