Quantum computation, one of the latest joint ventures between physics and the theory of computation, is a scientific field whose main goals include the development of hardware and algorithms based on the quantum mechanical properties of those physical systems used to implement such algorithms. Solving difficult tasks (for example, the Satisfiability Problem and other NP-complete problems) requires the development of sophisticated algorithms, many ofwhich employ stochastic processes as their mathematical basis. Discrete random walks are a popular choice among those stochastic processes. Inspired on the success of discrete random walks in algorithm development, quantum walks, an emerging field of quantum computation, is a generalization of random walks into the quantum mechanical world. The purpose of this lecture is to provide a concise yet comprehensive introduction to quantum walks. Table of Contents: Introduction / Quantum Mechanics / Theory of Computation / Classical Random Walks / Quantum Walks / Computer Science and Quantum Walks / Conclusions

} where each of the states is selected with probability n1 . We do not know what state was chosen to prepare | , but we do know that only preparations |ψ i , i ∈ {1, 2, . . . , n}, are allowed. In this case, a convenient representation for | is the associated density operator ρˆ = n1 nk=1 |ψ k ψ|. 2.2.2 Evolution of a Closed Quantum System Postulate 2 (Unitary operator version). The evolution of a closed quantum system with state vector | is described by a unitary transformation Uˆ (Def.

2008 Probability of finding walker at location n book_index 0.07 0.06 0.05 0.04 0.03 0.02 0.01 (c) 0 −100 −50 0 Position 50 100 FIGURE 5.2: Graph (a) was computed using coin initial state |ψ 0 = |0 c ⊗ |0 p . Graphs (b) and √ √ (c) had |ψ = √12 (|0 c + i|1 c ) ⊗ |0 p and |ψ = 0.85|0 c − 0.15|1 c ) ⊗ |0 p as coin initial states, respectively. Note that symmetry in the probability distribution can be achieved by using coin initial states with either complex or real relative phase factors

e d is the ith basis vector of the n-dimensional hypercube. So, the quantum walk on the hypercube proposed in [155] can be written as |ψ t = Uˆ t |ψ 0 ˆ Gˆ ⊗ Iˆn )]t |ψ = [ S( 0 (5.36) for a given initial state |ψ 0 . Using a Fourier transform approach as in [113], it was proved in [155] that Theorem 12. For the discrete quantum walk defined in Eq. (5.36), its instantaneous mixing time (Def. 5.1.2) is given by t = kπ n, i.e. t = O(n), with = O(n−7/6 ) for all odd k. 4 Reference [155] has

of sophisticated algorithms, many of which employ stochastic processes as their mathematical basis. Discrete random walks are a popular choice among those stochastic processes. Inspired on the success of discrete random walks in algorithm development, quantum walks, an emerging field of quantum computation, is a generalization of random walks into the quantum mechanical world. The purpose of this lecture is to provide a concise yet comprehensive introduction to quantum walks. KEYWORDS Quantum

doi:10.1103/PhysRevA.69.012310 [171] P. L. Knight, E. Rold´an, and J. E. Sipe, “Quantum walk on the line as an interference phenomenon,” Phys. Rev. A, Vol. 68, p. 020301, 2003. doi:10.1103/PhysRevA.68.020301 [172] P. L. Knight, E. Rold´an, and J. E. Sipe, “Optical cavity implementations of the quantum walk,” Opt. Commun., Vol. 227, pp. 147–157, 2003. doi:10.1016/j.optcom.2003.09.024 [173] P. L. Knight, E. Rold´an, and J. E. Sipe, “Propagating quantum walks: the origin of interference structures,”