Quantum walks for computer scientists

• Main Author: Venegas-Andraca, Salvador Elías.
• Format: Electronic
• Language: English
• Published: San Rafael, Calif. (1537 Fourth Street, San Rafael, CA 94901 USA) : Morgan & Claypool Publishers, c2008.
• Series: Synthesis lectures on quantum computing (Online) ; #1.
• Subjects: Quantum groups.; Random walks (Mathematics)
• Online Access: Abstract with links to full text
• Item Description: Part of: Synthesis digital library of engineering and computer science.; Title from PDF t.p. (viewed on October 15, 2008).; Series from website.
• Physical Description: 1 electronic text (xiv, 119 p. : ill.) : digital file.; Also available in print.
• Format: Mode of access: World Wide Web.; System requirements: Adobe Acrobat Reader.
• Bibliography: Includes bibliographical references (p. 105-118).
• ISBN: 9781598296570 (electronic bk.); 9781598296563 (pbk.)
• Access: Abstract freely available; full-text restricted to subscribers or individual document purchasers.

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 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.