Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Quantum and Classical Random Walks

Tristan Anthony Dobrian

Published Sep 1, 2019• 0 citations
OpenAlex

Abstract

This is a comprehensive and self-contained introduction to the math that underlies classical random walks and quantum random walk simulations.

Related papers

Quantum stochastic walks: A generalization of classical random walks and quantum walks

Alán Aspuru‐Guzik

Bulletin of the American Physical Society•Mar 17, 2010•0 citations

Quantum random walks: an introductory overview

Julia Kempe

Contemporary Physics•Jan 1, 2009•166 citations

Quantum walks with tuneable self-avoidance in one dimension

Elizabeth Camilleri, Peter P. Rohde, Jason Twamley

Quantum walks exhibit many unique characteristics compared to classical random walks. In the classical setting, self-avoiding random walks have been studied as a variation on the usual classical random walk. Here the walker has memory of its previous locations and preferentially avoids stepping back to locations where it has previously resided. Classical self-avoiding random walks have found numerous algorithmic applications, most notably in the modelling of protein folding. We consider the analogous problem in the quantum setting - a quantum walk in one dimension with tunable levels of self-avoidance. We complement a quantum walk with a memory register that records where the walker has previously resided. The walker is then able to avoid returning back to previously visited sites or apply more general memory conditioned operations to control the walk. We characterise this walk by examining the variance of the walker's distribution against time, the standard metric for quantifying how quantum or classical a walk is. We parameterise the strength of the memory recording and the strength of the memory back-action on the walker, and investigate their effect on the dynamics of the walk. We find that by manipulating these parameters, which dictate the degree of self-avoidance, the walk can be made to reproduce ideal quantum or classical random walk statistics, or a plethora of more elaborate diffusive phenomena. In some parameter regimes we observe a close correspondence between classical self-avoiding random walks and the quantum self-avoiding walk.

arXiv:1401.1869•Scientific Reports•Apr 25, 2014•10 citations

Matrix‐valued Szegő polynomials and quantum random walks

Maŕıa José Cantero, L. Moral, F. Alberto Grünbaum +1 more

Abstract We consider quantum random walks (QRW) on the integers, a subject that has been considered in the last few years in the framework of quantum computation. We show how the theory of CMV matrices gives a natural tool to study these processes and to give results that are analogous to those that Karlin and McGregor developed to study (classical) birth‐and‐death processes using orthogonal polynomials on the real line. In perfect analogy with the classical case, the study of QRWs on the set of nonnegative integers can be handled using scalar‐valued (Laurent) polynomials and a scalar‐valued measure on the circle. In the case of classical or quantum random walks on the integers, one needs to allow for matrix‐valued versions of these notions. We show how our tools yield results in the well‐known case of the Hadamard walk, but we go beyond this translation‐invariant model to analyze examples that are hard to analyze using other methods. More precisely, we consider QRWs on the set of nonnegative integers. The analysis of these cases leads to phenomena that are absent in the case of QRWs on the integers even if one restricts oneself to a constant coin. This is illustrated here by studying recurrence properties of the walk, but the same method can be used for other purposes. The presentation here aims at being self‐contained, but we refrain from trying to give an introduction to quantum random walks, a subject well surveyed in the literature we quote. For two excellent reviews, see [1, 9]. See also the recent notes [20]. © 2009 Wiley Periodicals, Inc.

arXiv:0901.2244•Communications on Pure and Applied Mathematics•Dec 29, 2009•105 citations

Random Walks: A Review of Algorithms and Applications

Feng Xia, Jiaying Liu, Hansong Nie +3 more

A random walk is known as a random process which describes a path including a succession of random steps in the mathematical space. It has increasingly been popular in various disciplines such as mathematics and computer science. Furthermore, in quantum mechanics, quantum walks can be regarded as quantum analogues of classical random walks. Classical random walks and quantum walks can be used to calculate the proximity between nodes and extract the topology in the network. Various random walk related models can be applied in different fields, which is of great significance to downstream tasks such as link prediction, recommendation, computer vision, semi-supervised learning, and network embedding. In this article, we aim to provide a comprehensive review of classical random walks and quantum walks. We first review the knowledge of classical random walks and quantum walks, including basic concepts and some typical algorithms. We also compare the algorithms based on quantum walks and classical random walks from the perspective of time complexity. Then we introduce their applications in the field of computer science. Finally we discuss the open issues from the perspectives of efficiency, main-memory volume, and computing time of existing algorithms. This study aims to contribute to this growing area of research by exploring random walks and quantum walks together.

arXiv:2008.03639•IEEE Transactions on Emerging Topics in Computational Intelligence•Nov 25, 2019•329 citations

From quantum graphs to quantum random walks

Gregor Tanner

arXiv:quant-ph/0504224•Springer eBooks•Jun 25, 2006•25 citations
Quantum walks exhibit many unique characteristics compared to classical random walks. In the classical setting, self-avoiding random walks have been studied as a variation on the usual classical random walk. Here the walker has memory of its previous locations and preferentially avoids stepping back to locations where it has previously resided. Classical self-avoiding random walks have found numerous algorithmic applications, most notably in the modelling of protein folding. We consider the analogous problem in the quantum setting - a quantum walk in one dimension with tunable levels of self-avoidance. We complement a quantum walk with a memory register that records where the walker has previously resided. The walker is then able to avoid returning back to previously visited sites or apply more general memory conditioned operations to control the walk. We characterise this walk by examining the variance of the walker's distribution against time, the standard metric for quantifying how quantum or classical a walk is. We parameterise the strength of the memory recording and the strength of the memory back-action on the walker, and investigate their effect on the dynamics of the walk. We find that by manipulating these parameters, which dictate the degree of self-avoidance, the walk can be made to reproduce ideal quantum or classical random walk statistics, or a plethora of more elaborate diffusive phenomena. In some parameter regimes we observe a close correspondence between classical self-avoiding random walks and the quantum self-avoiding walk.
Abstract We consider quantum random walks (QRW) on the integers, a subject that has been considered in the last few years in the framework of quantum computation. We show how the theory of CMV matrices gives a natural tool to study these processes and to give results that are analogous to those that Karlin and McGregor developed to study (classical) birth‐and‐death processes using orthogonal polynomials on the real line. In perfect analogy with the classical case, the study of QRWs on the set of nonnegative integers can be handled using scalar‐valued (Laurent) polynomials and a scalar‐valued measure on the circle. In the case of classical or quantum random walks on the integers, one needs to allow for matrix‐valued versions of these notions. We show how our tools yield results in the well‐known case of the Hadamard walk, but we go beyond this translation‐invariant model to analyze examples that are hard to analyze using other methods. More precisely, we consider QRWs on the set of nonnegative integers. The analysis of these cases leads to phenomena that are absent in the case of QRWs on the integers even if one restricts oneself to a constant coin. This is illustrated here by studying recurrence properties of the walk, but the same method can be used for other purposes. The presentation here aims at being self‐contained, but we refrain from trying to give an introduction to quantum random walks, a subject well surveyed in the literature we quote. For two excellent reviews, see [1, 9]. See also the recent notes [20]. © 2009 Wiley Periodicals, Inc.
A random walk is known as a random process which describes a path including a succession of random steps in the mathematical space. It has increasingly been popular in various disciplines such as mathematics and computer science. Furthermore, in quantum mechanics, quantum walks can be regarded as quantum analogues of classical random walks. Classical random walks and quantum walks can be used to calculate the proximity between nodes and extract the topology in the network. Various random walk related models can be applied in different fields, which is of great significance to downstream tasks such as link prediction, recommendation, computer vision, semi-supervised learning, and network embedding. In this article, we aim to provide a comprehensive review of classical random walks and quantum walks. We first review the knowledge of classical random walks and quantum walks, including basic concepts and some typical algorithms. We also compare the algorithms based on quantum walks and classical random walks from the perspective of time complexity. Then we introduce their applications in the field of computer science. Finally we discuss the open issues from the perspectives of efficiency, main-memory volume, and computing time of existing algorithms. This study aims to contribute to this growing area of research by exploring random walks and quantum walks together.