Differences between Quantum Walks and Classical Random Walks in Limit Distributions

Yutaka Shikano, Andrei Yu. Khrennikov, Gregg S. Jaeger +2 more

Jin-Fu Chen, Yu-Han Ma, Chang-Pu Sun

Quantum walk (QW), which is considered as the quantum counterpart of the classical random walk (CRW), is actually the quantum extension of CRW from the single-coin interpretation. The sequential unitary evolution engenders correlation between different steps in QW and leads to a non-binomial position distribution. In this paper, we propose an alternative quantum extension of CRW from the ensemble interpretation, named quantum random walk (QRW), where the walker has many unrelated coins, modeled as two-level systems, initially prepared in the same state. We calculate the walker’s position distribution in QRW for different initial coin states with the coin operator chosen as Hadamard matrix. In one-dimensional case, the walker’s position is the asymmetric binomial distribution. We further demonstrate that in QRW, coherence leads the walker to perform directional movement. For an initially decoherenced coin state, the walker’s position distribution is exactly the same as that of CRW. Moreover, we study QRW in 2D lattice, where the coherence plays a more diversified role in the walker’s position distribution.

Norio Konno, Hyun Jae Yoo

Andrew M. Childs, Edward Farhi, Sam Gutmann

Norio Konno, Takuya Machida

Recently Mc Gettrick introduced and studied a discrete-time 2-state quantum walk (QW) with a memory in one dimension. He gave an expression for the amplitude of the QW by path counting method. Moreover he showed that the return probability of the walk is more than 1/2 for any even time. In this paper, we compute the stationary distribution by considering the walk as a 4-state QW without memory. Our result is consistent with his claim. In addition, we obtain the weak limit theorem of the rescaled QW. This behavior is strikingly different from the corresponding classical random walk and the usual 2-state QW without memory as his numerical simulations suggested.

Lukas Hantzko, Lennart Binkowski

Abstract We present a comprehensive classification of one-dimensional coined quantum walks on the infinite line, focusing on the spatial probability distributions they induce. Building on prior results, we identify all initial coin states that lead to symmetric quantum walks for arbitrary coins and provide a bijective parametrisation of all symmetric quantum walks modulo distributional equivalence. Extending beyond the symmetric case, we also give a surjective parametrisation of all coined quantum walks under the same equivalence relation, as well as a bijective parametrisation modulo equivalence of their limiting distributions. Furthermore, we derive corrected closed-form expressions for the walk amplitudes, resolving inaccuracies in previous literature, and generalise the approach to the correlated classical random walk. This unified framework enables a direct comparison between quantum and classical dynamics. Additionally, we discuss the asymptotic scaling of variances for both models, identifying quadratic spreading as a hallmark of non-trivial quantum walks and contrasting it with the linear behaviour of classical walks, except at the extremal points of maximal correlation. Finally, we compare the limiting distributions arising from quantum walks with those of the classical case. Graphical abstract - compact classification results for symmetric and general quantum walks, as well as classically correlated random walks - quantum walks spread ballistically while classically correlated random walks approach Gaussian limiting distribution - quantum coin parameter directly influence limiting distribution’s skewness