2017/03/31 by Radhakrishnan Balu, Chaobin Liu, Salvador E. Venegas-Andraca +1 · 10 citations
Computer Science · Physics and Astronomy · #Complexity and Algorithms in Graphs #Discrete phase-type distribution #Limiting #Markov chain #Markov chain mixing time #Markov process #Probability distribution #Quantum Computing Algorithms and Architecture #Quantum walk #Quantum-Dot Cellular Automata #Random walk #Stationary distribution #Stochastic matrix #quant-ph
paper · pdf · doi:10.1088/1751-8121/aa99c7
published in Journal of Physics A Mathematical and Theoretical 51(3), 035301 (Institute of Physics)
openalex created_date 2017/03/23 · openalex publication_date 2017/11/10 · arxiv created 2017/12/16 · arxiv updated 2017/12/19 · openalex updated_date 2026/08/05
Abstract We analyze the probability distributions of the quantum walks induced from Markov chains by Szegedy (2004). The first part of this paper is devoted to the quantum walks induced from finite state Markov chains. It is shown that the probability distribution on the states of the underlying Markov chain is always convergent in the Cesaro sense. In particular, we deduce that the limiting distribution is uniform if the transition matrix is symmetric. In the case of a non-symmetric Markov chain, we exemplify that the limiting distribution of the quantum walk is not necessarily identical with the stationary distribution of the underlying irreducible Markov chain. The Szegedy scheme can be extended to infinite state Markov chains (random walks). In the second part, we formulate the quantum walk induced from a lazy random walk on the line. We then obtain the weak limit of the quantum walk. It is noted that the current quantum walk appears to spread faster than its counterpart-quantum walk on the line driven by the Grover coin discussed in literature. The paper closes with an outlook on possible future directions.