Quantum random walks - an introductory overview <s> A. The discrete model <s> A natural architecture for nanoscale quantum computation is that of a quantum cellular automaton. Motivated by this observation, we begin an investigation of exactly unitary cellular automata. After proving that there can be no nontrivial, homogeneous, local, unitary, scalar cellular automaton in one dimension, we weaken the homogeneity condition and show that there are nontrivial, exactly unitary, partitioning cellular automata. We find a one-parameter family of evolution rules which are best interpreted as those for a one-particle quantum automaton. This model is naturally reformulated as a two component cellular automaton which we demonstrate to limit to the Dirac equation. We describe two generalizations of this automaton, the second, of which, to multiple interacting particles, is the correct definition of a quantum lattice gas. <s> BIB001 </s> Quantum random walks - an introductory overview <s> A. The discrete model <s> Abstract Failure to find homogeneous scalar unitary cellular automata (CA) in one dimension led to consideration of only “approximately unitary” CA - which motivated our recent proof of a No-go Lemma in one dimension. In this note we extend the one dimensional result to prove the absence of nontrivial homogeneous scalar unitary CA on Euclidean lattices in any dimension. <s> BIB002 </s> Quantum random walks - an introductory overview <s> A. The discrete model <s> There are a number of questions in quantum complexity that have been resolved in the time-bounded setting, but remain open in the space-bounded setting. For example, it is not currently known if space-bounded probabilistic computations can be simulated by space-bounded quantum machines without allowing measurements during the computation, while it is known that an analogous statement holds in the time-bounded case. A more general question asks if measurements during a quantum computation can allow for more space-efficient solutions to certain problems. In this paper we show that space-bounded quantum Turing machines can efficiently simulate a limited class of random processes-random walks on undirected graphs-without relying on measurements during the computation. By means of such simulations, it is demonstrated that the undirected graph connectivity problem for regular graphs can be solved by one-sided error quantum Turing machines that run in logspace and require a single measurement at the end of their computations. It follows that symmetric logspace is contained in the quantum analogue of randomized logspace, i.e., SL/spl sube/QR/sub H/L. <s> BIB003 </s> Quantum random walks - an introductory overview <s> A. The discrete model <s> We define and analyze quantum computational variants of random walks on one-dimensional lattices. In particular, we analyze a quantum analog of the symmetric random walk, which we call the Hadamard walk . Several striking differences between the quantum and classical cases are observed. For example, when unrestricted in either direction, the Hadamard walk has position that is nearly uniformly distributed in the range [-t/\sqrt 2, t/\sqrt 2] after t steps, which is in sharp contrast to the classical random walk, which has distance O(\sqrt t) from the origin with high probability. With an absorbing boundary immediately to the left of the starting position, the probability that the walk exits to the left is 2/&pgr , and with an additional absorbing boundary at location n , the probability that the walk exits to the left actually increases, approaching 1/\sqrt 2 in the limit. In the classical case both values are 1. <s> BIB004 </s> Quantum random walks - an introductory overview <s> A. The discrete model <s> We analyse the quantum walk in higher spatial dimensions and compare classical and quantum spreading as a function of time. Tensor products of Hadamard transformations and the discrete Fourier transform arise as natural extensions of the 'quantum coin toss' in the one-dimensional walk simulation, and other illustrative transformations are also investigated. We find that entanglement between the dimensions serves to reduce the rate of spread of the quantum walk. The classical limit is obtained by introducing a random phase variable. <s> BIB005 </s> Quantum random walks - an introductory overview <s> A. The discrete model <s> Recently, it has been shown that one-dimensional quantum walks can mix more quickly than classical random walks, suggesting that quantum Monte Carlo algorithms can outperform their classical counterparts. We study two quantum walks on the n-dimensional hypercube, one in discrete time and one in continuous time. In both cases we show that the quantum walk mixes in (\pi/4)n steps, faster than the O(n log n) steps required by the classical walk. In the continuous-time case, the probability distribution is {\em exactly} uniform at this time. More importantly, these walks expose several subtleties in the definition of mixing time for quantum walks. Even though the continuous-time walk has an O(n) instantaneous mixing time at which it is precisely uniform, it never approaches the uniform distribution when the stopping time is chosen randomly as in [AharonovAKV2001]. Our analysis treats interference between terms of different phase more carefully than is necessary for the walk on the cycle; previous general bounds predict an exponential, rather than linear, mixing time for the hypercube. <s> BIB006 </s> Quantum random walks - an introductory overview <s> A. The discrete model <s> 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. <s> BIB007 </s> Quantum random walks - an introductory overview <s> A. The discrete model <s> Quantum walks are expected to provide useful algorithmic tools for quantum computation. This paper introduces absorbing probability and time of quantum walks and gives both numerical simulation results and theoretical analyses on Hadamard walks on the line and symmetric walks on the hypercube from the viewpoint of absorbing probability and time. Our results may be suggestive in constructing efficient quantum algorithms for combinatorial problems such as SAT. <s> BIB008 </s> Quantum random walks - an introductory overview <s> A. The discrete model <s> 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. <s> BIB009 </s> Quantum random walks - an introductory overview <s> A. The discrete model <s> In this paper we analyze the behavior of quantum random walks. In particular we present several new results for the absorption probabilities in systems with both one and two absorbing walls for the one-dimensional case. We compute these probabilites both by employing generating functions and by use of an eigenfunction approach. The generating function method is used to determine some simple properties of the walks we consider, but appears to have limitations. The eigenfunction approach works by relating the problem of absorption to a unitary problem that has identical dynamics inside a certain domain, and can be used to compute several additional interesting properties, such as the time dependence of absorption. The eigenfunction method has the distinct advantage that it can be extended to arbitrary dimensionality. We outline the solution of the absorption probability problem of a (d-1)-dimensional wall in a d-dimensional space. <s> BIB010
Let us define the formal set-up for a first model, the so called discrete time quantum random walk. Interestingly this model appears already in the works of Feynman  with the discretization of the Dirac equation in mind. In the era of quantum information it was rediscovered in works by Meyer BIB001 BIB002 in connection with quantum cellular automata and by Watrous [9] in the context of halting of quantum Turing machines and in a slightly modified version (with measurements) in BIB003 thinking about space-bounded quantum computation. As a possible computational tool and in a formal way it has been introduced and analysed in 2001 by Aharonov, Ambainis, Kempe and Vazirani  (on general graphs) and by Ambainis et al. BIB004 (on the line). We will define our model in one dimension, on the line or the circle. However the definitions carry over to the general case with slight modifications, which we will mention later. Let H P be the Hilbert space spanned by the positions of the particle. For a line with grid-length 1 this space is spanned by basis states {|i : i ∈ Z}; if we work on a circle of size N we have H P = {|i : i = 0 . . . N − 1}. States in this basis will take the role of the wave function |ψ of Section II with |i corresponding to a particle localized in position i. We will not be concerned any more about the width of the distribution of the wave function -our model describes unitary transformations of states of a finite Hilbert space H and the notion of a particle is only used to guide our intuition from now on. Yet later, when we talk about the physical implementation of the quantum random walk, we will see that we can approximate the states of this mathematical model by particles (atoms, photons, etc.) with wave functions of finite width. The position Hilbert space H P is augmented by a 'coin'-space H C spanned by two basis states {| ↑ , | ↓ }, which take the role of the spin-1 2 space in the previous section. States of the total system are in the space H = H C ⊗ H P as before. The conditional translation of the system (taking the role of exp(−2iS z ⊗ P l)) can be described by the following unitary operation where the index i runs over Z in the case of a line or 0 ≤ i ≤ N − 1 in the case of a circle. In the latter case we always identify 0 and N , so all arithmetic is performed modulo N . S transforms the basis state | ↑ ⊗ |i to | ↑ ⊗ |i + 1 and | ↓ ⊗ |i to | ↓ ⊗ |i − 1 . The first step of the random walk is a rotation in the coin-space, which in analogy to the classical random walk we will call 'coin-flip' C. The unitary transformation C is very arbitrary and we can define a rich family of walks with different behavior by modifying C. For the moment we will want C to be 'unbiased' in the following sense. Assume we would initialize the walk in a localized state |0 with the coin in one of the basis states, say | ↑ . If we chose to measure the coin-register of the walk in the (standard) basis {| ↑ , | ↓ } after one iteration (coin-flip C followed by translation S) we want to obtain the classical probability distribution of the unbiased walk, namely a translation to the right (|1 ) with probability The Quincunx is a device which allows a bead to drop through an array of pins stuck in a board. The pins are equally spaced in a number of rows and when the bead hits a pin it is equally likely to fall to the left or the right. It then lands on a pin in the next row where the process is repeated. After passing through all rows it is collected in a slot at the bottom. The distribution of beads approaches a Gaussian after many rows of pins. to the left (| − 1 ) otherwise. A frequently used balanced unitary coin is the so called Hadamard coin H It is easy to see that the Hadamard coin is balanced: Measuring the coin state in the standard basis gives each of {| ↑ ⊗ |1 , | ↓ ⊗ | − 1 } with probability 1/2. After this measurement there is no correlation between the positions left. If we continued the quantum walk with such a measurement at each iteration we obtain the plain classical random walk on the line (or on the circle). The distribution of this walk can be well illustrated with the help of Galton's board (also called Quincunx) in Fig. 2 . Its limiting distribution on the line (for large number of iterations T ) approaches a Gaussian distribution with mean zero and variance σ 2 = T . On the circle this distribution approaches the uniform distribution (more on convergence of random walks on finite graphs in Sec. IV). In the quantum random walk we will of course not measure the coin register during intermediate iterations, but rather keep the quantum correlations between different positions and let them interfere in subsequent steps. This interference will cause a radically different behavior of the quantum walk  . In particular we will see that the limiting distribution of the walk on the line will not approach a Gaussian and the variance σ 2 will not be linear in the number of steps T . The quantum random walk of T steps is defined as the transformation U T , where U , acting on H = H C ⊗ H P is given by To illustrate the departure of the quantum walk from its classical counterpart let us evolve the walk (without intermediate measurements) for some steps starting in the initial state |Φ in = | ↓ ⊗ |0 and study the induced probability distribution on the positions. This example already shows that the probability distribution induced by the quantum walk differs from the classical one. In Table 3 we list the classical distribution and in Table 4 the corresponding quantum distribution if we measure the position register after T steps. Only the probability at the even points is plotted, since the odd points have probability zero. The dotted line gives a long-wavelength approximation (labeled P slow since it keeps only the slowly varying frequencies  ), clearly showing the bi-modal character of the distribution. Figure 5 shows the probability distribution after T = 100 steps of the quantum walk starting in | ↓ ⊗ |0 . It is evident that the interference pattern of this walk is much more intricate than the Gaussian obtained in the classical case. One can clearly discern a two-peaked distribution. A first thing to notice is that the quantum random walk induces an asymmetric probability distribution on the positions, it is 'drifting' to the left. This asymmetry arises from the fact that the Hadamard coin treats the two directions | ↑ and | ↓ differently; it multiplies the phase by −1 only in the case of | ↓ . Intuitively this induces more cancellations for paths going right-wards (destructive interference), whereas particles moving to the left interfere constructively. There are two ways to mend this asymmetry. Inspecting Eq. (14) which describes the first step of the Hadamard walk starting in | ↑ ⊗ |0 (instead of in |Φ in = | ↓ ⊗ |0 as in Eq. (16)) and iterating the walk in Eq. (14) more we see that the walk starting in | ↑ ⊗ |0 has a drift to the right side, exactly opposite to the walk in Eq. BIB010 . To obtain a symmetric distribution we can start the walk in a superposition of | ↑ and | ↓ and make sure that these two drifts do not interfere with each other. This can be achieved starting in the symmetric state Since the Hadamard walk does not introduce any complex amplitudes the trajectories from | ↑ will stay real and the ones from | ↓ will be purely imaginary; they will hence not interfere with each other, making the total distribution symmetric. Another solution to eliminate asymmetry of the walk The probability distribution obtained from a computer simulation of the Hadamard walk with a symmetric initial condition  . The number of steps in the walk was taken to be 100. Only the probability at the even points is plotted, since the odd points have probability zero. is to use a different (balanced) coin, namely It is not hard to see that this coin treats | ↑ and | ↓ in the same way and does not bias the walk, independently of its initial coin-state. Figure 6 shows the probability distribution on the positions of a symmetric quantum walk. The pattern of the probability distribution is very intricate -a signature of the quantum world. The multitude of oscillations makes it hard to analyze the moments of this walk precisely. Using two different approaches -combinatorial techniques (recursions, path counting -initiated by Meyer BIB001 ) -and a more physical path-integral approach (which expresses the walk in the Fourier domain in terms of integrals that are amenable to asymptotic analysis) Ambainis et al. BIB004 give an asymptotic analysis of the variance of the quantum random walk  . As mentioned before the classical symmetric random walk on the line after T steps has a variance σ 2 = T , so the expected distance from the origin is of order σ = √ T . By contrast it can be shown that the quantum random walk has a variance that scales with σ 2 ∼ T 2 , which implies that the expected distance from the origin is of order σ ∼ T -the quantum walk propagates quadratically faster! Furthermore the walk spreads roughly uniformly over the positions in the interval [− ] as can be seen from Fig. 6 and shown analytically BIB004 . This is again in stark contrast to the classical case in which the distribution is peaked around the origin and drops off exponentially several standard deviations σ away from the origin.  The classical symmetric random walk on the line with one absorbing boundary placed in the origin. The starting point of the walk is in position 1. To uncover more striking differences of the quantum walk we can place it on a bounded line, either one-sided or two-sided BIB004 BIB010 . In other words we can insert one or two absorbing boundaries on the line. Formally an absorbing boundary in position |b corresponds to a partial measurement of the process at every time step. More precisely the unitary step U of the walk will be followed by a measurement M b on the position space H P described by the two projections onto |b and B ⊥ (the space orthogonal to |b ): where p b is the absorption probability and p B ⊥ its complement. For example if the current state of the system before measurement is given by then after the measurement M 0 the state will be | ↑ ⊗|0 with probability 2/7 (in which case we say absorption occurred and stop the walk) or otherwise in the state (−| ↑ ⊗ |1 + 3| ↓ ⊗ |1 ) with probability 5/7. Now define one step of the random walk with absorbing boundaries as U (Eq. (15)) followed by M b (or M b and M b ′ in the case of two absorbing boundaries placed in |b and |b ′ ). If the measurement result of M b (resp. M b ′ ) gives |b (resp. |b ′ ) the walk is stopped, otherwise the next iteration is applied. Let us review what is known about a classical random walk with one absorbing boundary. For concreteness let us assume that the walk is started in position 1 and that the boundary is placed in position b = 0, as in Fig. 7 . It is well known that the probability p to ever get absorbed by the wall in the origin is p = 1. This is very easy to see via a recursive reasoning on p: starting in 1 the walk hits 0 with probability 1/2, in which case it gets absorbed. Otherwise (with probability 1/2) its position is 2. The probability P 20 to ever hit 0 from 2 is the probability p 21 to ever hit 1 from 2 times the probability p 10 to ever hit 0 from 1. Both p 21 and p 10 are equal to p (the walk is homogeneous in space), which leads to the recursion with the solution p = 1. In the classical world a random walk always gets absorbed by a boundary and never escapes to infinity  . Not so for the quantum walk. Careful analysis BIB004 BIB010 shows that the quantum Hadamard walk with absorbing boundary in |0 , starting in the state | ↑ ⊗ |1 has a non-vanishing probability to escape. The probability to be absorbed at |0 turns out to be p quantum = 2/π ≈ 0.63662, which gives an escape probability of ≈ 0.36338. This behavior is general: for different initial states and distance to the boundary the numerical value for the absorption probability p quantum changes, but the escape probability is non-zero and finite in all cases. This is only the tip of the iceberg. After the seminal papers by Ambainis et al. BIB004 and Aharonov et al.  a lot of research has been focused on quantum random walks uncovering more and more results of quantum 'weirdness'. We will survey more of them in the following Section. In the spirit of the random walk on the line we can generalize the definition to quantum random walks on general graphs. Various aspects of quantum random walks on graphs and in higher dimensions have recently been studied in BIB006 BIB007 BIB005 BIB008  BIB009 . To set the stage let us define the random walk for d-regular graphs first. These are graphs with vertex-degree d, i.e. each vertex has d outgoing edges. The coin Hilbert space H C is of dimension d. For every vertex let us internally label all the outgoing edges with j ∈ 1 . . . d such that each edge has a distinct label. Let us call e j v an edge e = (v, w) which on v's end is labeled by j. The state associated with a vertex v pointing along an edge labeled j is |j ⊗ |v (corresponding to | ↑ ⊗ |i on the line or circle). Now we can define a conditional shift operation S S moves the particle from v to w if the edge (v, w) is labeled by j on v's side. If the graph is not d-regular we can still define S in the same way if we let d be the maximum degree of any vertex in the graph. Figure 8 shows a graph and a valid labeling. The coin-flip C is now a d-dimensional unitary transformation, which gives a lot of freedom in the choice of the coin-flip operation. The choice of C will have to be guided by the specifics and symmetries of the random walk we wish to obtain. We have already seen that even in the simple case of a walk on the line the choice of the coin operator can have a serious impact on the shape of the resulting distribution, and this effect is only amplified in higher dimensions (see BIB005 for examples of the effects of various coins on a two-and three-dimensional grid) or on graphs of higher valence (degree). If the graph is not regular, i.e. if the vertices have varying degrees, we can use one of several tricks to define a random walk with a coin. Either we add self-loops to each vertex of degree less than d (d is the maximal degree) 00 00 00 11 11 11 00 00 11 11 00 00 00 11 11 11 00 00 11 11 00 00 11 11 We have added self-loops to the graph to make it regular so that a single 4-dimensional coin can be used. and include them into the labeling (with the same label on both its ends), as in Fig. 8 . The shift applied to a self-loop will just keep the walk in place. Another option is to keep the irregularity of the graph and use different coin operators In that case the coin-operation has to be conditioned on the position of the particle and can no longer be written in the separable form of Eq. (15)  as (C ⊗I). However whenever we can define the corresponding classical walk we are able to define the quantum walk and implement it efficiently on a quantum computer (see Sec. IV). If we wish to retain the property in general graphs that the coin is balanced (i.e. every direction is obtained with equal probability if we measure the coin space) we can use the following coin which generalizes H Here ω = exp(2πi/d) is a d-th root of unity. Clearly the unitary DF T -coin  transforms each direction into an equally weighted superposition of directions such that after measurement each of them is equally likely to be obtained (with probability 1/d). Let us give an example where a non-balanced coin is used. The graph is the hypercube of dimension d. Figure  9 shows the hypercube in 3 dimensions. The vertices of the d-dimensional hypercube can be enumerated by dbit strings of 0's and 1's. Two vertices given by two bitstrings are connected whenever they differ by exactly one bit (e.g. 001101 and 011101). If we define the Hammingdistance d H (x, y) between two bit-strings x and y to be the minimum number of bits that need to be flipped to obtain y from x; then the hypercube connects all vertices of Hamming distance d H = 1. The number of 1's in a bit-string is called its Hamming weight. Note that the labeling of the edges of the hypercube can be chosen such that for each edge the labels from both sides coincide  . The classical simple random walk on the hypercube (where in each step a neighboring vertex is chosen with probability 1/d) has a high symmetry. If we start the walk in the vertex 00 . . . 0, for example, then all d vertices of Hamming weight 1 can be interchanged without modifying the random walk. Similarly all vertices of equal distance to the starting vertex, i.e. of equal Hamming weight, can be interchanged without changing the walk. This implies that all vertices of same Hamming weight have the same weight in the probability distribution of the random walk. This allows us to 'cumulate' all the vertices of same Hamming weight into a single vertex and to reduce the symmetric random walk on the hypercube to a biased random walk on the line, as is shown in Figure  10 for the hypercube of dimension 3. Such a reduction to the line will substantially simplify the analysis of the random walk when we are interested in questions like the speed of propagation of the random walk to his opposite corner. If we wish to retain this symmetry property for the quantum random walk it can be shown BIB006 that the only coins that are unitary and permutation symmetric are of the following form where a and b are real, 1 − If we start the quantum walk in an equal superposition of all the directions and measure the coin space H C after each iteration the resulting (classical) walk will have a higher propensity to go back and forth on the same edge than to switch directions. However the permutation invariance will allow us to reduce the quantum walk on the hypercube to a quantum walk on the line. This would not be possible if we used the d-dimensional DF T -coin, for example. We will return to this graph in Sec. IV.