Quantum random walks - an introductory overview <s> B. Continuous time quantum random walk <s> 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 $n$ 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 $n$ in time polynomial in $n,$ then so does the quantum algorithm. Moreover, we find examples of trees for which the classical algorithm requires time exponential in $n,$ 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. <s> BIB001 </s> Quantum random walks - an introductory overview <s> B. Continuous time quantum random walk <s> 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 <s> BIB002 </s> Quantum random walks - an introductory overview <s> B. Continuous time quantum random walk <s> 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. <s> BIB003
The discrete time model of quantum random walks is only one way to intersperse quantum effects with random walks. Another route to generalize the phenomenon described in Section II has been taken by Farhi et al. in 1998 [24, 25] . At the outset this approach seems very far from the discrete time random walk we have described above. Later, similarities will appear, however. The continuous time random walk takes place entirely in the position space H P . No coin space is needed and no coin is flipped. The intuition behind this model comes from continuous time classical Markov chains. Let us illustrate this with the simple classical random walk on a graph with vertex set V . A step in the classical random walk can be described by a matrix M which transforms the probability distribution over V . The entries M i,j give the probability to go from i to j in one step of the walk. . . , p t |V | ) be the probability distribution over the vertices of V at time T . Then which means The entries of M ij are non-zero only if there is a nonzero probability to go from i to j, i.e. when i and j are connected. The entry M ij is the probability to go from i to j and is equal to  It transforms an initial state p 0 = (1, 0, . . . , 0), corresponding to a starting position of 0, to p Table 3 . The process given by the iterations of M transforms the state at integer times only. To make the process continuous in time we can assume that transitions can occur at all times and the jumping rate from a vertex to its neighbor is given by γ, a fixed, time-independent constant. This means that transitions between neighboring nodes occur with probability γ per unit time. The infinitesimal generator matrix H of such a process is given by BIB003 If p i (t) denotes the probability to be at vertex i at time t then the transitions in analogy to Eq. (24) can be described by a differential equation FIG. 11: The graph G4. Two binary trees of n = 4 levels are glued together at their leafs in a symmetric fashion BIB002 . Solving the equation we obtain p(t) = exp(−Ht) p(0) in analogy to Eq. BIB002 . Note the similar structure of H and M . In the theory of classical Markov chains many connections between the discrete and continuous time model can be made and many of the quantities of interest, like mixing times (see Sec. IV B) and absorption probability, have similar behavior in both cases  . The idea of Farhi and Gutmann BIB001 was to carry this construction over to the quantum case. Their key idea is that the generator matrix will become the Hamiltonian of the process generating an evolution U (t) as If we start in some initial state |Ψ in , evolve it under U for a time T and measure the positions of the resulting state we obtain a probability distribution over the vertices of the graph as before. With this definitions in place Farhi and Gutmann BIB001 study the penetration of graphs by the quantum random walk. In BIB002 a finite graph is given where classical and quantum walks give an exponential separation in expected hitting time  . We will give this example here to illustrate yet another aspect of the difference of classical and quantum random walks, this time regarding the expected hitting time of certain nodes in a graph. The expected hitting time between two points S and T in a graph is the time it takes the random walk on average to reach T starting at S. The graph G n consists of two n-level binary trees glued together at their leafs as seen in Figure  11 . We start the random walk at the root of the left tree. Rather than the hitting time we study a slightly modified related quantity: the probability of hitting the root of the other (right) tree as a function of time. In other words, we are interested in how long it takes to propagate from the leftmost vertex to the rightmost vertex as a function of n. Consider the classical random walk first. The vertices of G n can be grouped in columns indexed by j ∈ {0, 1, . . . , 2n}. Column 0 contains the root of the left tree, column 1 contains the two vertices connected to that root, etc. Note that column n contains the 2 n vertices in the middle of the graph and column 2n is the root at the right. As before in the example of the hypercube (Fig. 10 ) the symmetry of the walk allows us to reduce it to a random walk on a line. We need only keep track of the probabilities of being in the columns. In the left tree, for 0 < j < n, the probability of stepping from column j to column j + 1 is twice as great as the probability of stepping from column j to column j − 1. However, in the right tree, for n < j < 2n, the probability of stepping from column j to column j + 1 is half as great as the probability of stepping from column j to column j − 1. This means that if you start at the left root, you quickly move to the middle of the graph, but then it takes a time exponential in n to reach your destination. More precisely, starting in column 0, the probability of being in column 2n after any number of steps is less than 2 −n . This implies that the probability of reaching column 2n in a time that is polynomial in n must be exponentially small as a function of n. We now analyze the quantum walk on G n BIB002 starting in the state corresponding to the left root and evolving with the Hamiltonian given by BIB003 . With this initial state, the symmetries of H keep the evolution in a (2n + 1)-dimensional subspace of the (2 n+1 + 2 n − 2)-dimensional Hilbert space. This subspace is spanned by states |j (where 0 ≤j ≤ 2n), the uniform superposition over all vertices in column j, that is, where In this basis, the non-zero matrix elements of H are which is depicted in Figure 12 (for n = 4) as a quantum random walk on a line with 2n + 1 vertices. As a first attempt to solve this reduced problem we can approximate the walk on this finite line by a walk on an infinite and furthermore homogeneous line by extending the Hamiltonian and replacing all diagonal entries of 2 by 3 as seen in Figure 13 . Solving this modified problem is the lore of a quantum physicist and the solution can readily be given in terms of Bessel functions (see BIB003 for a much more complete The elements of the Hamiltonian of the quantum random walk on Gn when reduced to the line for n = 4 BIB002 . For convenience γ is set to 1. treatment). It can be seen that the speed of propagation of the random walk on the infinite homogeneous line is linear in the time T . In other words there are constants a < b such that when T ∈ [an, bn] then the probability to measure the walk a distance 2n + 1 from the staring point (i.e. at the root of the right tree starting from the root of the left tree) is of order 1/ √ n. If we account for the finiteness of the line we are facing the standard quantum mechanical problem of a particle in a square-well potential, which is still not hard to solve. It is not entirely obvious that the finiteness of the line and the 'impurity' at level n do not change this behavior significantly [63] . Numerical studies BIB002 confirm that the linear propagation behavior is not significantly changed. To get a hand on the exact hitting time of this walk very recently BIB003 an upper bound for the propagation time is found. The precise statement is that if a time T is chosen randomly T ∈ [0, n 4 2ǫ ] and the walk is run for a time T , then the probability to measure the state in the root of the right tree is p hit > 1 n (1−ǫ). For algorithmic purposes we can repeat the random walk a polynomial number of times to almost surely find the particle at the right root at least once. We can also implement a discrete time random walk on the graph G n using the 3-dimensional Grover coin G (Eq. (23)) at the vertices of degree 3 and the 2-dimensional one at vertices of degree 2 (which just flips the two directions). Numerical studies [29] indicate that this discrete time random walk shows an extremely similar behavior to its continuous counterpart. In particular it is possible to reduce the walk to a discrete time walk on the line on which the walk propagates in linear time. This is just one example of the similarity of both models, of which there are many others. Before we give more results on the difference in behavior of classical and quantum random walks let us pause for a moment to investigate the importance of random walks for algorithms in computer science.