  Classical random walks on finite graphs have an underrated property: a walk
from any vertex can reach every other vertex in finite time, provided they are
connected. Discrete-time quantum walks on finite connected graphs however, can
have infinite hitting times. This phenomenon is related to graph symmetry, as
previously characterized by the group of direction-preserving graph
automorphisms that trivially affect the coin Hilbert space. If a graph is
symmetric enough (in a particular sense) then the associated quantum walk
unitary will contain eigenvectors that do not overlap a set of target vertices,
for any coin flip operator. These eigenvectors span the Infinite Hitting Time
(IHT) subspace. Quantum states in the IHT subspace never reach the target
vertices, leading to infinite hitting times. However, this is not the whole
story: the graph of the 3D cube does not satisfy this symmetry constraint, yet
quantum walks on this graph with certain symmetric coins can exhibit infinite
hitting times. We study the effect of coin symmetry by analyzing the group of
coin-permutation symmetries (CPS): graph automorphisms that act nontrivially on
the coin Hilbert space but leave the coin operator invariant. Unitaries using
highly symmetric coins with large CPS groups, such as the permutation-invariant
Grover coin, are associated with higher probabilities of never arriving, as a
result of their larger IHT subspaces.
