  The dimensionality of the internal coin space of discrete-time quantum walks
has a strong impact on the complexity and richness of the dynamics of quantum
walkers. While two-dimensional coin operators are sufficient to define a
certain range of dynamics on complex graphs, higher dimensional coins are
necessary to unleash the full potential of discrete-time quantum walks. In this
work we present an experimental realization of a discrete-time quantum walk on
a line graph that, instead of two-dimensional, exhibits a four-dimensional coin
space. Making use of the extra degree of freedom we observe multiple ballistic
propagation speeds specific to higher dimensional coin operators. By
implementing a scalable technique, we demonstrate quantum walks on circles of
various sizes, as well as on an example of a Husimi cactus graph. The quantum
walks are realized via time-multiplexing in a Michelson interferometer loop
architecture, employing as the coin degrees of freedom the polarization and the
traveling direction of the pulses in the loop. Our theoretical analysis shows
that the platform supports implementations of quantum walks with arbitrary $4
\times 4$ unitary coin operations, and usual quantum walks on a line with
various periodic and twisted boundary conditions.
