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^ 2 3 ) query quantum algorithm. This improves the previous O(N^ 3 4 ) query quantum algorithm of Buhrman this http URL. (quant-ph 0007016) and matches the lower bound by Shi (quant-ph 0112086). The algorithm also solves the generalization of element distinctness in which we have to find k equal items among N items. For this problem, we get an O(N^ k (k+1) ) query quantum algorithm.
@cite_4: We present a new quantum algorithm that either finds a triangle (a copy of @math ) in an undirected graph @math on @math nodes, or it outputs reject'' if @math is triangle free. The algorithm uses @math queries, and it is based on a new design concept of Ambainis that incorporates the benefits of quantum walks into Grover search. The algorithm both improves on, and is simpler than a recent algorithm of Szegedy which has @math query complexity. The Triangle Problem was first treated in [BDH+01], where an algorithm with @math query complexity was presented (here @math is the number of edges of @math ).
@cite_32: We show how to search N items arranged on a √N × √N grid in time O(√N log N), using a discrete time quantum walk. This result for the first time exhibits a significant difference between discrete time and continuous time walks without coin degrees of freedom. since it has been shown recently that such a continuous time walk needs time Ω(N) to perform the same task. Our result improves on a previous bound for quantum local search by Aaronson and Ambainis. We generalize our result to 3 and more dimensions where the walk yields the optimal performance of O(√N) and give several extensions of quantum walk search algorithms and generic expressions for its performance for general graphs. The coin-flip operation needs to be chosen judiciously: we show that another "natural" choice of coin gives a walk that takes Ω(N) steps. We also show that in 2 dimensions it is sufficient to have a two-dimensional coin-space to achieve the time O(√N log N).
@cite_3: 
Recent developments. After the work described in this paper, the results and ideas from this paper have been used to construct several other quantum algorithms. @cite_4 have used our element distinctness algorithm to give an @math query quantum algorithm for finding triangles in a graph. @cite_32 have used ideas from the current paper to construct a faster algorithm for search on 2-dimensional grid. Childs and Eisenberg @cite_3 have given a different analysis of our algorithm.