Szegedy Walk Unitaries for Quantum Maps

Understand

Szegedy developed a generic method for quantizing classical algorithms based on random walks [Proceedings of FOCS, 2004, pp.

• 32-41].
• A major contribution of his work was the construction of a walk unitary for any reversible random walk.
• Such unitary posses two crucial properties: its eigenvector with eigenphase $0$ is a quantum sample of the limiting distribution of the random walk and its eigenphase gap is quadratically larger than the spectral gap of the random walk.