In the world of computational probing, random walks and quantum walks are two separate but tightly linked paradigms. Classical stochastic processes like random walks are based on the random movement of particles in mathematical space and have been extensively used in data mining, network analysis, computer vision, etc. Quantum walks, by contrast generalize random walks into the quantum realm, taking the benefit of the quantum superposition and interference in order to investigate multiple paths at the same time. Quantum walks provide significant potential for algorithmic development: in quantum computing and communication, and in Scientific modelling and simulation. This paper provides an in-depth survey of random walks and quantum walks, outlining historical context, fundamental principles, applications, challenges, and future prospects. In this paper, motivated by the abstractness of both random walks and quantum walks, we survey the field of computational exploration at large scales, coalescing the myriad notions and difficult challenges addressed by existing research efforts on random and quantum walks, inferring a nuanced and multifaceted view on how both random walks and quantum walks are involved in paving the way to future development in many fields.
In the world of computational probing, random walks and quantum walks are two separate but tightly linked paradigms. Classical stochastic processes like random walks are based on the random movement of particles in mathematical space and have been extensively used in data mining, network analysis, computer vision, etc. Quantum walks, by contrast generalize random walks into the quantum realm, taking the benefit of the quantum superposition and interference in order to investigate multiple paths at the same time. Quantum walks provide significant potential for algorithmic development: in quantum computing and communication, and in Scientific modelling and simulation. This paper provides an in-depth survey of random walks and quantum walks, outlining historical context, fundamental principles, applications, challenges, and future prospects. In this paper, motivated by the abstractness of both random walks and quantum walks, we survey the field of computational exploration at large scales, coalescing the myriad notions and difficult challenges addressed by existing research efforts on random and quantum walks, inferring a nuanced and multifaceted view on how both random walks and quantum walks are involved in paving the way to future development in many fields.
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.
This book explores the intersection of quantum computing and network science. It bridges the theoretical foundations of quantum walk algorithms with their applications in the structural exploration and representation learning of complex networks. Quantum walks, a technology that is pivotal to universal quantum computational models, examines the movement of particles on a graph composed of nodes and links. Quantum superposition enables these particles to traverse these graphs more quickly, while measurement-induced collapse introduces fluctuations, making the identification of critical nodes challenging yet intriguing. At its core, the book explores how quantum walk algorithms can transform the structural and representational analysis of complex networks. It begins by introducing the fundamental concepts of quantum computing and quantum walks, including generalized definitions and the properties of low-dimensional quantum walks. Then, it discusses the implementation of discrete- and continuous-time quantum walks for mining network nodes, links, and subgraphs, as well as their use in network representation learning and graph neural networks. The book will serve as a valuable reference for researchers, students, and educators interested in quantum walks, complex networks, quantum mechanics, and information engineering.
The classical random walk formalism plays an important role in a wide range of applications. Its quantum counterpart, the quantum walk, is proposed as an important theoretical model for quantum computing. By exploiting quantum effects such as superposition, interference, and entanglement, quantum walks and their variations have been extensively studied for achieving computing power beyond that of classical computing and have been broadly used in designing quantum algorithms for algebraic and optimization problems, graph and network analysis, and quantum Hamiltonian and biochemical process simulations. Moreover, quantum walk models have been proven capable of universal quantum computation. Unlike conventional quantum circuit models, quantum walks provide a feasible path for implementing application-specific quantum computing, particularly in the noisy intermediate-scale quantum era. Recently, remarkable progress has been achieved in implementing a wide variety of quantum walks and quantum walk applications, which demonstrates the great potential of quantum walks. In this review, we provide a thorough summary of quantum walks and quantum walk computing, including theories and characteristics, physical implementations, and applications. We also discuss the challenges facing quantum walk computing, which aims to realize a practical quantum computer in the near future.
Quantum computers have sparked significant interest in recent years due to their potential to revolutionize various fields. One area where quantum computing shows great promise is in the study of quantum walks, a quantum counterpart of the classical random walk algorithm that has been foundational in scientific research. While both quantum and classical random walks involve a "walker" moving through a space or graph, quantum walks differ fundamentally due to quantum principles such as superposition, leading to unique behaviors like linear spreading and localization. This thesis investigates the quantum walk simulation, with a particular focus on the Quantum-Walk-Replicating-Random-Walk (QWRW) model. Unlike traditional quantum walks, which sum over all possible paths with complex interference effects, the QWRW approach models the walk as a series of distinct, classical-like steps. This trajectory-based perspective offers a novel way to analyze the walker's position and movement, avoiding the complexities of quantum interference. The QWRW model is particularly valuable in understanding key phenomena of quantum walks, such as linear spreading and localization, by providing insights into the directional properties of quantum walkers. By defining transition probabilities in both space and time, the QWRW model offers a detailed framework for examining the spatial and temporal characteristics of quantum walks, enhancing our understanding of their behavior and potential applications. This study aims to bridge the gap between classical and quantum walks, contributing to the broader field of quantum computing and its practical implications.
Signal processing is important for modern technologies such as digital communication systems and sensor networks, and is used to enhance and optimize the quality of transmitted signals. However, traditional methods and design frameworks are insufficient for the demands of future communication networks, which are expected to be highly complex and constantly changing. Our research focuses on a mathematical model known as a Markov model, which represents a system as a series of states linked by transitions. This model can be applied to various signal processing challenges in telecommunications, such as the modeling of communication channels, sources of information, and the correction of distortion and noise in transmitted signals. We examine the random walk algorithm, a simple and efficient way to simulate the behavior of a Markov chain, as it can provide valuable insights into the performance of communication systems and help to optimize their design. However, it may not be able to accurately model systems with complex transitions or systems that exhibit long-term correlations. In order to address the challenges and limitations of classical random walk, we propose the use of quantum random walk, which is a quantum mechanical version of classical random walk. It describes the motion of particles in a probabilistic way, similar to classical random walk, but with the added complexity of quantum mechanics. We also provide quantum walk algorithm with Hadamard gate implementation for coin operator.
Random walks are fundamental models of stochastic processes with applications in various fields, including physics, biology, and computer science. We study classical and quantum random walks under the influence of stochastic resetting on arbitrary networks. Based on the mathematical formalism of quantum stochastic walks, we provide a framework of classical and quantum walks whose evolution is determined by graph Laplacians. We study the influence of quantum effects on the stationary and long-time average probability distribution by interpolating between the classical and quantum regime. We compare our analytical results on stationary and long-time average probability distributions with numerical simulations on different networks, revealing differences in the way resets affect the sampling properties of classical and quantum walks.