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
hitting time H0,n given by  book_index MOCL009.cls September 13, 2008 12:6 CLASSICAL RANDOM WALKS 4.3 55 STOCHASTIC ALGORITHMS BASED ON CLASSICAL DISCRETE RANDOM WALKS Our motivation for studying random walks is to understand how such stochastic processes can be used to build algorithms. In this section we show how discrete random walks are used to solve two different instances of the SAT problem (Def. 3.4.7). Algorithms that use stochastic processes to find a solution, i.e.
distributions cover the same number of positions (in this case, even positions from −100 to 100. If the quantum walk had MOCL009.cls 12:6 QUANTUM WALKS FOR COMPUTER SCIENTISTS Hadamard walk Number of steps: 100. Initial conditions: |0〉c ⊗ |0〉p 0.14 Probability of locating walker at position n 66 September 13, 2008 0.12 0.1 0.08 0.06 0.04 0.02 0 −100 −50 0 Position 50 100 Hadamard walk Number of steps= 100. Initial conditions: |1>c ⊗ |0>p. 0.14 Probability of locating walker at
012320, 2008. doi:10.1103/PhysRevA.78.012320  Advanced Research and Development Activity, “Qist: a quantum information science and technology roadmap,” 2004.  ERA-Pilot, “Quantum information processing and communication strategic report version 1.4,” 2007.  J. Joo, Y. L. Lim, A. Beige, and P. L. Knight, “Single-qubit rotations in 2d optical lattices with multi-qubit addressing,” Phys. Rev. A, Vol. 74, p. 042344, 2006. doi:10.1103/PhysRevA.74.042344  B. P. Lanyon, T. J. Weinhold, N.
593, 2005.  M. Szegedy, “Quantum speed-up of Markov chain algorithms,” in Proc. 45th IEEE Symp. on the Foundations of Computer Science, Vol. 2004, pp. 32–41. doi:10.1109/FOCS.2004.53  F. Magniez, A. Nayak, J. Roland, and M. Santha, “Search via quantum walk,” in Proc. 39th ACM Symp. on Theory of Computing, 2007.  A. Ambainis, “Quantum walks and their algorithmic applications,” Int. J. Quantum Inform., Vol. 1(4), pp. 507–518, 2003. doi:10.1142/S0219749903000383  R. D. Somma, S.
nondeterministic models of computation. We also introduce some formal elements of algorithmic complexity (mainly, measures used to quantify the performance of an arbitrary algorithm), followed by the topic of NP-completeness, one of the central themes in Complexity Theory, together with an example of NP-completeness: the satisfiability (SAT) problem. Finally, we provide a brief review on the links between physics and the theory of computation and give the definitions of Probabilistic and Quantum