Quantum random walks - an introductory overview <s> VI. DECOHERENCE <s> The quantum random walk has been much studied recently, largely due to its highly nonclassical behavior. In this paper, we study one possible route to classical behavior for the discrete quantum walk on the line: the presence of decoherence in the quantum ''coin'' which drives the walk. We find exact analytical expressions for the time dependence of the first two moments of position, and show that in the long-time limit the variance grows linearly with time, unlike the unitary walk. We compare this to the results of direct numerical simulation, and see how the form of the position distribution changes from the unitary to the usual classical result as we increase the strength of the decoherence. <s> BIB001 </s> Quantum random walks - an introductory overview <s> VI. DECOHERENCE <s> Quantum random walks have been much studied recently, largely due to their highly nonclassical behavior. In this paper, we study one possible route to classical behavior for the discrete quantum random walk on the line: the use of multiple quantum “coins” in order to diminish the effects of interference between paths. We find solutions to this system in terms of the single coin random walk, and compare the asymptotic limit of these solutions to numerical simulations. We find exact analytical expressions for the time-dependence of the first two moments, and show that in the long time limit the “quantum mechanical” behavior of the one-coin walk persists. We further show that this is generic for a very broad class of possible walks, and that this behavior disappears only in the limit of a new coin for every step of the walk. <s> BIB002 </s> Quantum random walks - an introductory overview <s> VI. DECOHERENCE <s> We look at two possible routes to classical behavior for the discrete quantum random walk on the integers: decoherence in the quantum "coin" which drives the walk, or the use of higher-dimensional (or multiple) coins to dilute the effects of interference. We use the position variance as an indicator of classical behavior and find analytical expressions for this in the long-time limit; we see that the multicoin walk retains the "quantum" quadratic growth of the variance except in the limit of a new coin for every step, while the walk with decoherence exhibits "classical" linear growth of the variance even for weak decoherence. <s> BIB003
The world of quantum mechanics shows all kinds of counter intuitive signs. Yet in the classical world of our daily experience we rarely see a cat that is in a superposition of dead and alive. The emergence of the classical world from an underlying quantum micro-world is a topic of active debate, research and speculation. Usually it is assumed that interaction with a larger environment induces decoherence, which in turn makes the world classical. We will describe how one could imagine that the classical random walk emerges form its quantum counterpart. The crucial difference between the quantum and the classical walk are the quantum coherences, which are present only in the first. So a transition from quantum to classical has to somehow kill these coherences. We have seen in Sec. III that the classical walk can be obtained from the quantum walk if we measure the coin register at every iteration. Another way to obtain the classical walk is to measure the positions at every step. We can now imagine some continuous way to interpolate between non-measuring (the quantum case) and completely measuring (the classical case) and study the transition along this pathway. An intermediate step would be to measure the register (coin or position or both) only with some probability p meas at each step, where p meas = 0 corresponds to the purely quantum and p meas = 1 to the purely classical case. Numerical studies of this transition from quantum to classical have been executed for the circle, line and hypercube by Kendon and Tregenna  and extensive analytical expressions for the walk on the line with decoherence of the coin-space have been obtained by Brun et al. BIB003  . They find that the classical behavior sets in very rapidly. As an indicator we can look at the variance of the walk. In the purely quantum case we have seen that σ 2 ∼ T 2 , whereas in the classical case σ 2 ∼ T . For the walk on the line with coin decoherence Brun et al. BIB003 BIB001 compute the variance as a function of the transition parameter p meas to find that even for very small values of p meas (very 'close' to quantum) the variance is already linear. Kendon's numerical results for both coin and position decoherence confirm that for all p meas > 1/T the behavior of the variance is essentially classical (linear in T ). One could have expected that the variance would level off gradually with increasing p meas , but this does not seem to be the case. There is another interesting option to transition the coined walk between quantum and classical taken by Brun et al. BIB003 BIB002 . Imagine the quantum discrete time random walk with the modification that at each iteration we use a fresh coin Hilbert space to flip our coin. This does not allow the quantum coherences between the coin degrees of freedom to ever interfere and hence the walk behaves like the classical walk. A way to go from quantum to classical would be to use a new coin space only once in a while; a walk alternating between two coinspaces at every step can be thought of close to the quantum walk, a walk with three coin-spaces is already less quantum and so on to the walk with an amount of coin spaces close to T , which is close to classical. It turns out that this way to transition from quantum to classical induces a very different behavior of the variance σ 2 : it stays quadratic in T for a whole range of coin-spaces to become linear only in the limit of one new coin per time step. So the quantum character in this transition is very robust! Kendon and Tregenna's  numerical studies also show that decoherence can improve both convergence to uniform and reliability of hitting. For small p ≪ 1/T (where the walk is already a 'little bit classical') under certain conditions the convergence to uniform on the circle (or line-segment) can be faster than in the purely quantum case. There is certainly a lot more to understand about decoherence in quantum random walks than we do presently -these initial studies seem to unveil just the tip of an enormous iceberg. Conclusion: Starting from a rather simple physical effect we have tried to build up the beautiful framework of quantum random walks. We have presented several rather striking differences in the behavior of these walks as compared to their classical counterparts concerning their distribution, their mixing and hitting properties. With the advent of quantum computation it is our hope that quantum random walks will be utilized to provide new and fast algorithms that can be run on a quantum computer. We have seen that the first steps have been made in this direction, also from the implementation point of view. This area of research is still dotted with open questions and problems and we hope the reader has obtained a good general intuition and overview as to how this exciting field has evolved so far and where it might go.