The notion of quantum walks have been discovered mainly in computer sciences to improve certain search algorithms, and recently they are used in this area, computer simulation, and quantum physics. Although their definition is a non-commutative analogue of the classical random walks, their behavior is quite different from classical random walks.

This talk is concentrated on the one-dimensional case. After some historical remarks, definition and simple properties of one-dimensional quantum walks will be given. Then, some difference between them and classical random walks will be explained. Weak limit formula due to Konno and local asymptotic formulas due to Sunada and the speaker will be introduced. Finally, an algebraic structure behind the quantum walks will be explained.