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

arXiv:1609.06711 · Physical Review A

Quantum and random walks as universal generators of probability distributions

Miquel Montero

Published Jun 16, 2017• 21 citations
arXivHTMLPDF

Abstract

Quantum walks and random walks bear similarities and divergences. One of the most remarkable disparities affects the probability of finding the particle at a given location: typically, almost a flat function in the first case and a bell-shaped one in the second case. Here I show how one can impose any desired stochastic behavior (compatible with the continuity equation for the probability function) on both systems by the appropriate choice of time- and site-dependent coins. This implies, in particular, that one can devise quantum walks that show diffusive spreading without losing coherence as well as random walks that exhibit the characteristic fast propagation of a quantum particle driven by a Hadamard coin.

DOI
10.1103/physreva.95.062326

Related papers

Quantum Random Walks and Piecewise Deterministic Evolutions

Ph. Blanchard, M.‐O. Hongler

In the continuous space and time limit, we show that the probability density to find the quantum random walk (QRW) driven by the Hadamard "coin" solves a hyperbolic evolution equation similar to the one obtained for a random two-velocity evolution with spatially inhomogeneous transition rates between the velocity states. In spite of the presence of a nonlinear drift term, it is remarkable that the QRW position can easily be described in simple analytical terms. This allows us to derive the quadratic time dependence of the variance typical for the QRW.

Physical Review Letters•Mar 26, 2004•25 citations

Aperiodic Quantum Random Walks

Pedro Ribeiro, P. Milman, Rémy Mosseri

We generalize the quantum random walk protocol for a particle in a one-dimensional chain, by using several types of biased quantum coins, arranged in aperiodic sequences, in a manner that leads to a rich variety of possible wave-function evolutions. Quasiperiodic sequences, following the Fibonacci prescription, are of particular interest, leading to a sub-ballistic wave-function spreading. In contrast, random sequences lead to diffusive spreading, similar to the classical random walk behavior. We also describe how to experimentally implement these aperiodic sequences.

arXiv:quant-ph/0406071•Physical Review Letters•Nov 4, 2004•124 citations

Characterizing the Relationship Between Unitary Quantum Walks and Non-Homogeneous Random Walks

Matheus Guedes de Andrade, Franklin de Lima Marquezino, Daniel R. Figueiredo

Quantum walks on graphs are ubiquitous in quantum computing finding a myriad of applications. Likewise, random walks on graphs are a fundamental building block for a large number of algorithms with diverse applications. While the relationship between quantum and random walks has been recently discussed in specific scenarios, this work establishes a formal equivalence between the two processes on arbitrary finite graphs and general conditions for shift and coin operators. It requires empowering random walks with time heterogeneity, where the transition probability of the walker is non-uniform and time dependent. The equivalence is obtained by equating the probability of measuring the quantum walk on a given node of the graph and the probability that the random walk is at that same node, for all nodes and time steps. The first result establishes procedure for a stochastic matrix sequence to induce a random walk that yields the exact same vertex probability distribution sequence of any given quantum walk, including the scenario with multiple interfering walkers. The second result establishes a similar procedure in the opposite direction. Given any random walk, a time-dependent quantum walk with the exact same vertex probability distribution is constructed. Interestingly, the matrices constructed by the first procedure allows for a different simulation approach for quantum walks where node samples respect neighbor locality and convergence is guaranteed by the law of large numbers, enabling efficient (polynomial-time) sampling of quantum graph trajectories. Furthermore, the complexity of constructing this sequence of matrices is discussed in the general case.

•Jun 29, 2021•0 citations

Quantum Walks

Takuya Machida

Quantum walks are quantum counterparts of random walks. While probability distributions of random walks diffusively spread out as the walkers are updating, quantum walks have ballistic behavior. Some of the ballistic behaviors have been revealed in long-time limit theorems and their probability distributions are all far away from the Gaussian distributions, which are known as limit distributions of random walks. In this chapter, we are going to be seeing limit distributions for a standard quantum walk on the line and two kinds of time-dependent quantum walk on the line.

InTech eBooks•Aug 24, 2016•1 citation

Revisiting one-dimensional discrete-time quantum walks with general coin

Mahesh N. Jayakody, Chandrakala Meena, Priodyuti Pradhan

Quantum walk (QW) is the quantum analog of the random walk. QW is an integral part of the development of numerous quantum algorithms. Hence, an in-depth understanding of QW helps us to grasp the quantum algorithms. We revisit the one-dimensional discrete-time QW and discuss basic steps in detail by incorporating the most general coin operator, constant in both space and time, and a localized initial state using numerical modeling. We investigate the impact of each parameter of the general coin operator on the probability distribution of the quantum walker. We show that by tuning the parameters of the general coin, one can regulate the probability distribution of the walker. We provide an algorithm for the one-dimensional quantum walk driven by the general coin operator. The study on general coin operators also includes the popular coins – Hadamard, Grover, and Fourier.

Physics Open•Nov 10, 2023•9 citations

Limiting distribution of decoherent quantum random walks

Kai Zhang

The behavior of one-dimensional quantum random walks is strikingly different from that of classical ones. However, when decoherence is involved, the limiting distributions take on many classical features over time. In this paper, we study the decoherence on both position and ``coin'' spaces of the particle. We propose an analytical approach to investigate these phenomena and obtain the generating functions which encode all the features of these walks. Specifically, from these generating functions, we find exact analytic expressions of several moments for the time and noise dependence of position. Moreover, the limiting position distributions of decoherent quantum random walks are shown to be Gaussian in an analytical manner. These results explicitly describe the relationship between the system and the level of decoherence.

arXiv:0804.4311•Physical Review A•Jun 2, 2008•22 citations
Quantum walks and random walks bear similarities and divergences. One of the most remarkable disparities affects the probability of finding the particle at a given location: typically, almost a flat function in the first case and a bell-shaped one in the second case. Here I show how one can impose any desired stochastic behavior (compatible with the continuity equation for the probability function) on both systems by the appropriate choice of time- and site-dependent coins. This implies, in particular, that one can devise quantum walks that show diffusive spreading without losing coherence as well as random walks that exhibit the characteristic fast propagation of a quantum particle driven by a Hadamard coin.
In the continuous space and time limit, we show that the probability density to find the quantum random walk (QRW) driven by the Hadamard "coin" solves a hyperbolic evolution equation similar to the one obtained for a random two-velocity evolution with spatially inhomogeneous transition rates between the velocity states. In spite of the presence of a nonlinear drift term, it is remarkable that the QRW position can easily be described in simple analytical terms. This allows us to derive the quadratic time dependence of the variance typical for the QRW.
We generalize the quantum random walk protocol for a particle in a one-dimensional chain, by using several types of biased quantum coins, arranged in aperiodic sequences, in a manner that leads to a rich variety of possible wave-function evolutions. Quasiperiodic sequences, following the Fibonacci prescription, are of particular interest, leading to a sub-ballistic wave-function spreading. In contrast, random sequences lead to diffusive spreading, similar to the classical random walk behavior. We also describe how to experimentally implement these aperiodic sequences.
Quantum walks on graphs are ubiquitous in quantum computing finding a myriad of applications. Likewise, random walks on graphs are a fundamental building block for a large number of algorithms with diverse applications. While the relationship between quantum and random walks has been recently discussed in specific scenarios, this work establishes a formal equivalence between the two processes on arbitrary finite graphs and general conditions for shift and coin operators. It requires empowering random walks with time heterogeneity, where the transition probability of the walker is non-uniform and time dependent. The equivalence is obtained by equating the probability of measuring the quantum walk on a given node of the graph and the probability that the random walk is at that same node, for all nodes and time steps. The first result establishes procedure for a stochastic matrix sequence to induce a random walk that yields the exact same vertex probability distribution sequence of any given quantum walk, including the scenario with multiple interfering walkers. The second result establishes a similar procedure in the opposite direction. Given any random walk, a time-dependent quantum walk with the exact same vertex probability distribution is constructed. Interestingly, the matrices constructed by the first procedure allows for a different simulation approach for quantum walks where node samples respect neighbor locality and convergence is guaranteed by the law of large numbers, enabling efficient (polynomial-time) sampling of quantum graph trajectories. Furthermore, the complexity of constructing this sequence of matrices is discussed in the general case.
Quantum walks are quantum counterparts of random walks. While probability distributions of random walks diffusively spread out as the walkers are updating, quantum walks have ballistic behavior. Some of the ballistic behaviors have been revealed in long-time limit theorems and their probability distributions are all far away from the Gaussian distributions, which are known as limit distributions of random walks. In this chapter, we are going to be seeing limit distributions for a standard quantum walk on the line and two kinds of time-dependent quantum walk on the line.
Quantum walk (QW) is the quantum analog of the random walk. QW is an integral part of the development of numerous quantum algorithms. Hence, an in-depth understanding of QW helps us to grasp the quantum algorithms. We revisit the one-dimensional discrete-time QW and discuss basic steps in detail by incorporating the most general coin operator, constant in both space and time, and a localized initial state using numerical modeling. We investigate the impact of each parameter of the general coin operator on the probability distribution of the quantum walker. We show that by tuning the parameters of the general coin, one can regulate the probability distribution of the walker. We provide an algorithm for the one-dimensional quantum walk driven by the general coin operator. The study on general coin operators also includes the popular coins – Hadamard, Grover, and Fourier.
The behavior of one-dimensional quantum random walks is strikingly different from that of classical ones. However, when decoherence is involved, the limiting distributions take on many classical features over time. In this paper, we study the decoherence on both position and ``coin'' spaces of the particle. We propose an analytical approach to investigate these phenomena and obtain the generating functions which encode all the features of these walks. Specifically, from these generating functions, we find exact analytic expressions of several moments for the time and noise dependence of position. Moreover, the limiting position distributions of decoherent quantum random walks are shown to be Gaussian in an analytical manner. These results explicitly describe the relationship between the system and the level of decoherence.