  Quantum walk acts obviously different from its classical counterpart, but
decoherence will lessen and close the gap between them. To understand this
process, it is necessary to investigate the evolution of quantum walk under
different situation of decoherence. In this article, we study a non-Markovian
decoherent quantum walk on a line. In the short time regime, the behavior of
the walk deviates from both idea quantum walks and classical random walks. The
position variance as a measure of quantum walk starts oscillating from the
first several steps and tends to be linear on time and showing a diffusive
spread in the long time limit, which is caused by the non-Markovian dephasing
affecting on quantum correlations between quantum walker and his coin. We also
study both quantum discord and measurement-induced disturbance as measures of
quantum correlations and observe that both of them oscillate in the short time
regime and tend to be zero in the long time limit. Therefore quantum walk with
non-Markovian decoherence tends to diffusive spreading behavior in the long
time limit, while in the short time regime it oscillates between a ballistic
and diffusive spreading behavior, and the quantum correlation collapses and
revivals due to the memory effect.
