  Hitting times are the average time it takes a walk to reach a given final
vertex from a given starting vertex. The hitting time for a classical random
walk on a connected graph will always be finite. We show that, by contrast,
quantum walks can have infinite hitting times for some initial states. We seek
criteria to determine if a given walk on a graph will have infinite hitting
times, and find a sufficient condition, which for discrete time quantum walks
is that the degeneracy of the evolution operator be greater than the degree of
the graph. The set of initial states which give an infinite hitting time form a
subspace. The phenomenon of infinite hitting times is in general a consequence
of the symmetry of the graph and its automorphism group. Using the irreducible
representations of the automorphism group, we derive conditions such that
quantum walks defined on this graph must have infinite hitting times for some
initial states. In the case of the discrete walk, if this condition is
satisfied the walk will have infinite hitting times for any choice of a coin
operator, and we give a class of graphs with infinite hitting times for any
choice of coin. Hitting times are not very well-defined for continuous time
quantum walks, but we show that the idea of infinite hitting-time walks
naturally extends to the continuous time case as well.

Quantum Physics