Quantum random walks - an introductory overview <s> I. OVERVIEW <s> An inexpensive faucet aerator is provided by three molded parts and a thin metal cup that holds two of the molded parts in assembled relationship. The first molded part is an elongated annulus provided with upstream and downstream recesses separated by an inner ring that helps to break up the liquid flow and serves as an abutment to support a second molded, jet-forming, part in the upstream recess and is arranged to be engaged by the third, molded, part located in the downstream recess and aiding in defining air intake means to the aerator. <s> BIB001 </s> Quantum random walks - an introductory overview <s> I. OVERVIEW <s> Quantum cryptography could well be the first application of quantum mechanics at the individual quanta level. The very fast progress in both theory and experiments over the recent years are reviewed, with emphasis on open questions and technological issues. <s> BIB002
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 BIB001 . New ideas include quantum cryptography [2, BIB002 and quantum computation. In 1994 Peter Shor  discovered a quantum algorithm to factor numbers efficiently (that is in time that grows only polynomial with the length of the number to be factored), which 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 the physical devise that is carrying it ('Information is physical') has firmly settled among them and has led to fascinating new insights. Acquaintance with the basic notions of each of these fields seems instrumental in the understanding of modern quantum information processing. In this article we will follow the trajectory of one of the many surprising aspects of quantum information; it is dedicated to quantum random walks. We will give a thorough introduction to the necessary terminology without overburdening the reader with unnecessary mathematics. Starting with a very intuitive and physical example we will step by step introduce the language and notation of present day quantum information science. We will present the necessary background from computer science needed for a physicist to understand and appreciate the developments and results, assuming some rudimentary background of quantum mechanics, but no knowledge of computer science or quantum information theory. An excellent comprehensive introduction to quantum information and computation can be found in BIB001 . In this journey at the interface of several traditional disciplines we will follow quantum random walks both through physics and computer science. This tour through quantum information science will allow us to survey some of its most pertinent concepts and ideas today, like quantum algorithms, quantum computing machines, speedups, physical implementation, quantum circuits and decoherence. It will be our mission to show how physical phenomena translate into new computer science algorithms and vice versa. The idea is that a reader familiar with the standard idiom of quantum mechanics but unaccustomed to the language of 'qubits' and 'gates' will learn about quantum information science while learning about quantum random walks and their fascinating behavior. We will survey some recent developments and results omitting most proofs but trying to develop an intuition. This article aims to bring the interested reader to a point where he or she can read and understand current research articles on the topic and develop an understanding for the interesting problems and open questions in the area. The structure of this article is as follows: First we give some physical intuition for random walks, providing a general flavor of the phenomenon in a physical setting (Section II). This is followed by a more rigorous definition together with some necessary terminology to introduce the two main models of quantum random walks in Section III. We then present some computer science and probability background and mention some of the important algorithmic results stemming from quantum random walks in Section IV. Section V switches back to physics and studies how these random walks could be implemented in some real physical system. Finally we deal with the more philosophical question of how the classical world emerges from quantum behavior via decoherence using random walks as our example (Section VI). All along the way we will outline open questions and future directions.