  Quantum walks have emerged as an interesting approach to quantum information
processing, exhibiting many unique properties compared to the analogous
classical random walk. Here we introduce a model for a discrete-time quantum
walk with memory by endowing the walker with multiple recycled coins and using
a physical memory function via a history dependent coin flip. By numerical
simulation we observe several phenomena. First in one dimension, walkers with
memory have persistent quantum ballistic speed up over classical walks just as
found in previous studies of multi-coined walks with trivial memory function.
However, measurement of the multi-coin state can dramatically shift the mean of
the spatial distribution. Second, we consider spatial entanglement in a
two-dimensional quantum walk with memory and find that memory destroys
entanglement between the spatial dimensions, even when entangling coins are
employed. Finally, we explore behaviour in the presence of spatial randomness
and find that in contrast to single coined walks, multi-coined walks do not
localise and in fact a memory function can speed up the walk relative to a
fully decohered multi-coin walker with trivial memory. We explicitly show how
to construct linear optics circuits implementing the walks, and discuss
prospects for classical simulation.
