Quantum Walks for Computer Scientists (Synthesis Lectures on Quantum Computing)
Format: PDF / Kindle (mobi) / ePub
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
C could have more than one satisfying truth assignment that could also be found during the computation of algorithm 1. So, Eq. (4.23) represents the worst case as is standard practice in algorithm performance analysis. Using standard methods for difference equations  with α = β = 12 , we find that Eq. (4.23) has solution Ei = 2in − i 2 , therefore En = n2 . Thus, our expected number of steps is n2 regardless our starting point. Finally, using Markov’s inequality (Theorem 1) we find that P (X
the continuous time t and the discrete lattice position n. Then,  uses results from [106, 112] to build a discrete quantum walk represented by the following unitary mapping: ψ R(n, τ + 1) = cos θ ψ R(n − 1, τ ) − i sin θ ψ L (n − 1, τ ), (5.44a) ψ L (n, τ + 1) = cos θ ψ L (n + 1, τ ) − i sin θ ψ L (n + 1, τ ), (5.44b) where ψ R(n, τ ) and ψ L (n, τ ) are complex amplitudes at the discrete time τ and discrete lattice position n. ˆ that allows Strauch’s result focuses on building a unitary
Correction to Quantum Cryptography. Cambridge: Cambridge University Press, 2006.  N. D. Mermin, “From cbits to qbits: teaching computer scientists quantum mechanics,” Am. J. Phys., Vol. 71, pp. 23–30, 2003. doi:10.1119/1.1522741  E. Rieffel and W. Polak, “An introduction to quantum computing for non-physicists,” ACM Comput. Surv., Vol. 32(3), pp. 300–335, 2000. doi:10.1145/367701.367709  B. J. Copeland, The Essential Turing. Oxford: Oxford University Press, 2004.  C. H.
Soshi, and H. J. Yoo, “Quantum walks and reversible cellular automata,” Phys. Lett. A, Vol. 330(6), pp. 408–417, 2004. doi:10.1016/j.physleta.2004.08.025  W. van Dam, “Quantum cellular automata,” M.Sc. thesis, University of Nijmegen, The Netherlands, 1996.  I. Fuss, L. White, P. Sherman, and S. Naguleswaran, “An analytic solution for onedimensional quantum walks,” arXiv:0705.0077v1.  E. Feldman and M. Hillery, “Modifying quantum walks: a scattering theory approach,” J. Phys. A:
cayley graphs,” J. Phys. A: Math. Gen., Vol. 39, pp. 585–599, 2006. doi:10.1088/0305-4470/39/3/011  A. Montanaro, “Quantum walks on directed graphs,” Quantum Inform. Comput., Vol. 7(1), pp. 093–102, 2007.  H. Krovi and T. A. Brun, “Quantum walks on quotient graphs,” Phys. Rev. A, Vol. 75, p. 062332, 2007. doi:10.1103/PhysRevA.75.062332  H. Krovi, “Symmetry in Quantum Walks,” Ph.D. thesis, University of Southern California, 2007.  J. Watrous, “Quantum simulations of classical