  We outline a theory of symmetry protected topological phases of
one-dimensional quantum walks. We assume spectral gaps around the
symmetry-distinguished points +1 and -1, in which only discrete eigenvalues are
allowed. The phase classification by integer or binary indices extends the
classification known for translation invariant systems in terms of their band
structure. However, our theory requires no translation invariance whatsoever,
and the indices we define in this general setting are invariant under arbitrary
symmetric local perturbations, even those that cannot be continuously
contracted to the identity. More precisely we define two indices for every
walk, characterizing the behavior far to the right and far to the left,
respectively. Their sum is a lower bound on the number of eigenstates at +1 and
-1. For a translation invariant system the indices add up to zero, so one of
them already characterizes the phase. By joining two bulk phases with different
indices we get a walk in which the right and left indices no longer cancel, so
the theory predicts bound states at +1 or -1. This is a rigorous statement of
bulk-edge correspondence. The results also apply to the Hamiltonian case with a
single gap at zero.
