Tatsuya Tate

Quantum walks in one dimension

The notion of quantum walks was originally given as quantum random walks in quantum physics in 1993 and was re-discovered, as in the form recently adopted, in computer science around 2001. It is defined as a unitary operator on a Hilbert space defined over graphs, and it is regarded as a non-commutative version of classical random walks.Non-commutativity affects asymptotic properties of quantum walks which are quite different from classical random walks.
In this talk, after a review on the classical random walks, definitions and simple properties of one-dimensional quantum walks will be given. Some asymptotic results of quantum walks, which are quite different from classical one, will be explained. Recently an algebraic aspect of one-dimensional quantum walks has become considered. A concrete formula for the powers of quantum walks based on the algebraic structure will be explained.