Quantum random walks - an introductory overview
This article aims to provide an introductory survey on quantum random walks. Starting from a physical effect to illustrate the main ideas we will introduce quantum random walks, review some of their properties and outline their striking differences to classical walks. We will touch upon both physical effects and computer science applications, introducing some of the main concepts and language of present day quantum information science in this context. We will mention recent developments in this new area and outline some open questions. 1. Overview Ever since the discovery of quantum mechanics people have been puzzled by the counter-intuitive character of the laws of nature. Over time we have learned to accept more and more effects that are unimaginable in a classical Newtonian world. Modern technology exploits quantum effects both to our benefit and detriment—among the memorable examples we should cite laser technology and not omit the atomic bomb. In recent years interest in quantum information theory has been generated by the prospect of employing its laws to design devices of surprising power [1]. New ideas include quantum cryptography [2, 3] and quantum computation. In 1994 Shor [4] discovered a quantum algorithm to factor numbers efficiently (that is in time that grows only polynomically with the length of the number to be factored). This has unleashed a wave of activity across a broad range of disciplines: physics, computer science, mathematics and engineering. This fruitful axis of research has uncovered many new effects that are strikingly different from their classical counterparts, both from the physical point of view as well as from a computer science and communication theory perspective. Over time these communities have gained a greater understanding of the concepts and notions of the other. The idea that information cannot be separated from