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_30: We show that the hitting time of the discrete time quantum random walk on the n-bit hypercube from one corner to its opposite is polynomial in n. This gives the first exponential quantum-classical gap in the hitting time of discrete quantum random walks. We provide the framework for quantum hitting time and give two alternative definitions to set the ground for its study on general graphs. We then give an application to random routing.
@cite_35: Quantum walks are quantum counterparts of Markov chains. In this article, we give a brief overview of quantum walks, with emphasis on their algorithmic applications.
@cite_7: We construct a black box graph traversal problem that can be solved exponentially faster on a quantum computer than on a classical computer. The quantum algorithm is based on a continuous time quantum walk, and thus employs a different technique from previous quantum algorithms based on quantum Fourier transforms. We show how to implement the quantum walk efficiently in our black box setting. We then show how this quantum walk solves our problem by rapidly traversing a graph. Finally, we prove that no classical algorithm can solve the problem in subexponential time.
@cite_21: In this note, we discuss a general definition of quantum random walks on graphs and illustrate with a simple graph the possibility of very different behavior between a classical random walk and its quantum analog. In this graph, propagation between a particular pair of nodes is exponentially faster in the quantum case. PACS: 03.67.Hk
@cite_1: Grover's quantum search algorithm provides a way to speed up combinatorial search, but is not directly applicable to searching a physical database. Nevertheless, Aaronson and Ambainis showed that a database of N items laid out in d spatial dimensions can be searched in time of order radical (N) for d>2, and in time of order radical (N) poly(log N) for d=2. We consider an alternative search algorithm based on a continuous-time quantum walk on a graph. The case of the complete graph gives the continuous-time search algorithm of Farhi and Gutmann, and other previously known results can be used to show that radical (N) speedup can also be achieved on the hypercube. We show that full radical (N) speedup can be achieved on a d-dimensional periodic lattice for d>4. In d=4, the quantum walk search algorithm takes time of order radical (N) poly(log N), and in d<4, the algorithm does not provide substantial speedup.
@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_2: Quantum random walks on graphs have been shown to display many interesting properties, including exponentially fast hitting times when compared with their classical counterparts. However, it is still unclear how to use these novel properties to gain an algorithmic speedup over classical algorithms. In this paper, we present a quantum search algorithm based on the quantum random-walk architecture that provides such a speedup. It will be shown that this algorithm performs an oracle search on a database of N items with O( radical (N)) calls to the oracle, yielding a speedup similar to other quantum search algorithms. It appears that the quantum random-walk formulation has considerable flexibility, presenting interesting opportunities for development of other, possibly novel quantum algorithms.
@cite_34: Many interesting computational problems can be reformulated in terms of decision trees. A natural classical algorithm is to then run a random walk on the tree, starting at the root, to see if the tree contains a node @math level from the root. We devise a quantum-mechanical algorithm that evolves a state, initially localized at the root, through the tree. We prove that if the classical strategy succeeds in reaching level @math in time polynomial in @math then so does the quantum algorithm. Moreover, we find examples of trees for which the classical algorithm requires time exponential in @math but for which the quantum algorithm succeeds in polynomial time. The examples we have so far, however, could also be solved in polynomial time by different classical algorithms.
@cite_25: This article aims to provide an introductory survey on quantum random walks. Starting from a physical effect to illustrate the main ideas we will introduce quantum random walks, review some of their properties and outline their striking differences to classical walks. We will touch upon both physical effects and computer science applications, introducing some of the main concepts and language of present day quantum information science in this context. We will mention recent developments in this new area and outline some open questions.
Quantum walks. There has been considerable amount of research on quantum walks (surveyed in @cite_25 ) and their applications (surveyed in @cite_35 ). Applications of walks @cite_35 mostly fall into two classes. The first class is exponentially faster hitting times @cite_21 @cite_7 @cite_30 . In these applications, quantum walks are used to find a certain vertex exponentially faster than classically. (The first results @cite_34 @cite_21 @cite_30 were quantum walk algorithms that are exponentially faster than classical algorithms based on classical random walks. The most recent result @cite_7 is a quantum walk algorithm which is exponentially faster than any classical algorithm.) Our result is quite different from those, both in the problem that we consider and the way how we solve. While polynomial speedup achieved in our paper is smaller than exponential speedup in @cite_7 , our result has the advantage that we solve a natural problem which has been widely studied in both classical and quantum computing. The second class is quantum walk search algorithms @cite_2 @cite_1 @cite_32 .