  We set the ground for a theory of quantum walks on graphs- the generalization
of random walks on finite graphs to the quantum world. Such quantum walks do
not converge to any stationary distribution, as they are unitary and
reversible.
  However, by suitably relaxing the definition, we can obtain a measure of how
fast the quantum walk spreads or how confined the quantum walk stays in a small
neighborhood. We give definitions of mixing time, filling time, dispersion
time. We show that in all these measures, the quantum walk on the cycle is
almost quadratically faster then its classical correspondent. On the other
hand, we give a lower bound on the possible speed up by quantum walks for
general graphs, showing that quantum walks can be at most polynomially faster
than their classical counterparts.
