Minimal resources for exact simulation of quantum walks

Quantum walks are stochastic processes generated by a quantum evolution mechanism, allowing for speed-up in spreading and hitting-time performance with respect to their classical counterparts. Investigating the role of the memory effects for these models, we address the problem of finding the minimal linear system that exactly reproduces the evolution of the output distribution of a quantum walk. After adapting the classical approach to our setting, we investigate analytically and numerically the structural complexity of quantum walks, both in general and in particular examples. Lastly, we focus on Grover’s algorithm, a quantum computing search algorithm that can be re-framed as a quantum walk, showing that it allows for a dramatic reduction in its representation.