Quantum walks, the discrete wave equation and Chebyshev polynomials
<|reference_start|>Quantum walks, the discrete wave equation and Chebyshev polynomials: A quantum walk is the quantum analogue of a random walk. While it is relatively well understood how quantum walks can speed up random walk hitting times, it is a long-standing open question to what extent quantum walks can speed up the spreading or mixing rate of random walks on graphs. In this expository paper, inspired by a blog post by Terence Tao, we describe a particular perspective on this question that derives quantum walks from the discrete wave equation on graphs. This yields a description of the quantum walk dynamics as simply applying a Chebyshev polynomial to the random walk transition matrix. This perspective decouples the problem from its quantum origin, and highlights connections to earlier (non-quantum) work and the use of Chebyshev polynomials in random walk theory as in the Varopoulos-Carne bound. We illustrate the approach by proving a weak limit of the quantum walk dynamics on the lattice. This gives a different proof of the quadratically improved spreading behavior of quantum walks on lattices.<|reference_end|>
@article{apers2024quantum,
    title={Quantum walks, the discrete wave equation and Chebyshev polynomials},
    author={Simon Apers and Laurent Miclo},
    journal={arXiv preprint arXiv:2402.07809},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.07809},
    primaryClass={quant-ph cs.DS math.PR}
}