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:2103.06463

Quantum Walks can Unitarily Represent Random Walks on Finite Graphs

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

Published Mar 11, 2021• 0 citations
arXivHTMLPDF

Abstract

Quantum and random walks have been shown to be equivalent in the following sense: a time-dependent random walk can be constructed such that its vertex distribution at all time instants is identical to the vertex distribution of any discrete-time coined quantum walk on a finite graph. This equivalence establishes a deep connection between the two processes, far stronger than simply considering quantum walks as quantum analogues of classical random walks. The present work strengthens this connection by providing a construction that establishes this equivalence in the reverse direction: a unitary time-dependent quantum walk can be constructed such that its vertex distribution is identical to the vertex distribution of any random walk on a finite graph at all time instants. The construction shown here describes a quantum walk that matches a random walk without measurements at all time steps (an otherwise trivial statement): measurement is performed in a quantum walk that evolved unitarily until a given time $t$ such that its vertex distribution is identical to the random walk at time $t$. The construction procedure is general, covering both homogeneous and non-homogeneous random walks. For homogeneous random walks, unitary evolution implies time dependency for the quantum walk, since homogeneous quantum walks do not converge under arbitrary initial conditions, while a broad class of random walks does. Thus, the absence of convergence demonstrated for quantum walks in its debut comes from both time-homogeneity and unitarity, rather than unitarity alone, and our results shed light on the power of quantum walks to generate samples for arbitrary probability distributions. Finally, the construction here proposed is used to simulate quantum walks that match uniform random walks on the cycle and the torus.

DOI
10.48550/arxiv.2103.06463

Related papers

Using quantum walks to unitarily represent random walks on finite graphs

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

Quantum and random walks have been shown to be equivalent in the following sense: a time-dependent random walk can be constructed such that its vertex distribution at all time instants is identical to the vertex distribution of any discrete-time coined quantum walk on a finite graph. This equivalence establishes a deep connection between the two processes, far stronger than simply considering quantum walks as quantum analogs of classical random walks. The present paper strengthens this connection by providing a construction that establishes this equivalence in the reverse direction: a unitary time-dependent quantum walk can be constructed such that its vertex distribution is identical to the vertex distribution of any random walk on a finite graph at all time instants. The construction shown here describes a quantum walk that matches a random walk without measurements at all time steps (an otherwise trivial statement): measurement is performed in a quantum walk that evolved unitarily until a given time $t$ such that its vertex distribution is identical to the random walk at time $t$. The construction procedure is general, covering both homogeneous and nonhomogeneous random walks. For homogeneous random walks, unitary evolution implies time dependency for the quantum walk, since homogeneous quantum walks do not converge under arbitrary initial conditions, while a broad class of random walks does. Thus, the absence of convergence demonstrated for a quantum walk in its debut comes from both time homogeneity and unitarity, rather than unitarity alone, and our results shed light on the power of quantum walks to generate samples for arbitrary probability distributions. Finally, the construction here proposed is used to simulate quantum walks that match uniform random walks on the cycle and the torus.

Physical Review A•Apr 12, 2024•1 citation

Quantum walks can unitarily match random walks on finite graphs

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

Quantum and random walks were proven to be equivalent on finite graphs by demonstrating how to construct a time-dependent random walk sharing the exact same evolution of vertex probability of any given discrete-time coined quantum walk. Such equivalence stipulated a deep connection between the processes that is far stronger than simply considering quantum walks as quantum analogues of random walks. This article expands on the connection between quantum and random walks by demonstrating a procedure that constructs a time-dependent quantum walk matching the evolution of vertex probability of any given random walk in a unitary way. It is a trivial fact that a quantum walk measured at all time steps of its evolution degrades to a random walk. More interestingly, the method presented describes a quantum walk that matches a random walk without measurement operations, such that the unitary evolution of the quantum walk captures the probability evolution of the random walk. The construction procedure is general, covering both homogeneous and non-homogeneous random walks. For the homogeneous random walk case, the properties of unitary evolution imply that the quantum walk described is time-dependent since homogeneous quantum walks do not converge for arbitrary initial conditions

•Mar 11, 2021•1 citation

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 On Graphs

Dorit Aharonov, Andris Ambainis, Julia Kempe +1 more

We set the ground for a theory of quantum walks on graphs- the generalization of random walks on finite graphs to the quantum world. Such quantum walks do not converge to any stationary distribution, as they are unitary and reversible. However, by suitably relaxing the definition, we can obtain a measure of how fast the quantum walk spreads or how confined the quantum walk stays in a small neighborhood. We give definitions of mixing time, filling time, dispersion time. We show that in all these measures, the quantum walk on the cycle is almost quadratically faster then its classical correspondent. On the other hand, we give a lower bound on the possible speed up by quantum walks for general graphs, showing that quantum walks can be at most polynomially faster than their classical counterparts.

arXiv:quant-ph/0012090•Dec 18, 2000•10 citations

Quantum-driven sampling of the quasi-uniform distribution via quantum walks

Marco Radaelli, Claudia Benedetti, Stefano Olivares

We investigate the use of discrete-time quantum walks to sample from an almost-uniform distribution, in the absence of any external source of randomness. Integers are encoded on the vertices of a cycle graph, and a quantum walker evolves for a fixed number of steps before its position is measured and recorded. The walker is then reset to the measured site, and the procedure is iterated to produce the sequence of random numbers. We show that when the quantum walk parameters, such as the coin operator and initial state, satisfy the conditions of the ergodic theorem for random walks on finite groups, the resulting sequence converges asymptotically to the uniform distribution. Although correlations between successive outcomes are unavoidable, they can be significantly reduced by a suitable choice of the evolution time. By analyzing the iterated convolution of the quantum walk transition probability and exploiting the ergodic theorem, we demonstrate convergence of the marginal distributions toward the uniform distribution in the asymptotic limit.

quant-pharXiv:2511.08293•Nov 12, 2025•0 citations

Quantum-driven sampling of the almost-uniform distribution via quantum walks

Marco Radaelli, Claudia Benedetti, Stefano Olivares

Abstract We investigate the use of discrete-time quantum walks to sample from an almost-uniform distribution, in the absence of any external source of randomness. Integers are encoded on the vertices of a cycle graph, and a quantum walker evolves for a fixed number of steps before its position is measured and recorded. The walker is then reset to the measured site, and the procedure is iterated to generate the sequence of outcomes. We show that when the number of nodes of the graph is odd, i.e. the condition of the ergodic theorem for classical random walks on finite groups are satisfied, the marginal distributions converges to the uniform distribution. Although correlations between successive outcomes are unavoidable, they can be significantly reduced by a suitable choice of the evolution time.

New Journal of Physics•Feb 19, 2026•0 citations
Quantum and random walks have been shown to be equivalent in the following sense: a time-dependent random walk can be constructed such that its vertex distribution at all time instants is identical to the vertex distribution of any discrete-time coined quantum walk on a finite graph. This equivalence establishes a deep connection between the two processes, far stronger than simply considering quantum walks as quantum analogues of classical random walks. The present work strengthens this connection by providing a construction that establishes this equivalence in the reverse direction: a unitary time-dependent quantum walk can be constructed such that its vertex distribution is identical to the vertex distribution of any random walk on a finite graph at all time instants. The construction shown here describes a quantum walk that matches a random walk without measurements at all time steps (an otherwise trivial statement): measurement is performed in a quantum walk that evolved unitarily until a given time ttt such that its vertex distribution is identical to the random walk at time ttt. The construction procedure is general, covering both homogeneous and non-homogeneous random walks. For homogeneous random walks, unitary evolution implies time dependency for the quantum walk, since homogeneous quantum walks do not converge under arbitrary initial conditions, while a broad class of random walks does. Thus, the absence of convergence demonstrated for quantum walks in its debut comes from both time-homogeneity and unitarity, rather than unitarity alone, and our results shed light on the power of quantum walks to generate samples for arbitrary probability distributions. Finally, the construction here proposed is used to simulate quantum walks that match uniform random walks on the cycle and the torus.
Quantum and random walks have been shown to be equivalent in the following sense: a time-dependent random walk can be constructed such that its vertex distribution at all time instants is identical to the vertex distribution of any discrete-time coined quantum walk on a finite graph. This equivalence establishes a deep connection between the two processes, far stronger than simply considering quantum walks as quantum analogs of classical random walks. The present paper strengthens this connection by providing a construction that establishes this equivalence in the reverse direction: a unitary time-dependent quantum walk can be constructed such that its vertex distribution is identical to the vertex distribution of any random walk on a finite graph at all time instants. The construction shown here describes a quantum walk that matches a random walk without measurements at all time steps (an otherwise trivial statement): measurement is performed in a quantum walk that evolved unitarily until a given time ttt such that its vertex distribution is identical to the random walk at time ttt. The construction procedure is general, covering both homogeneous and nonhomogeneous random walks. For homogeneous random walks, unitary evolution implies time dependency for the quantum walk, since homogeneous quantum walks do not converge under arbitrary initial conditions, while a broad class of random walks does. Thus, the absence of convergence demonstrated for a quantum walk in its debut comes from both time homogeneity and unitarity, rather than unitarity alone, and our results shed light on the power of quantum walks to generate samples for arbitrary probability distributions. Finally, the construction here proposed is used to simulate quantum walks that match uniform random walks on the cycle and the torus.
Quantum and random walks were proven to be equivalent on finite graphs by demonstrating how to construct a time-dependent random walk sharing the exact same evolution of vertex probability of any given discrete-time coined quantum walk. Such equivalence stipulated a deep connection between the processes that is far stronger than simply considering quantum walks as quantum analogues of random walks. This article expands on the connection between quantum and random walks by demonstrating a procedure that constructs a time-dependent quantum walk matching the evolution of vertex probability of any given random walk in a unitary way. It is a trivial fact that a quantum walk measured at all time steps of its evolution degrades to a random walk. More interestingly, the method presented describes a quantum walk that matches a random walk without measurement operations, such that the unitary evolution of the quantum walk captures the probability evolution of the random walk. The construction procedure is general, covering both homogeneous and non-homogeneous random walks. For the homogeneous random walk case, the properties of unitary evolution imply that the quantum walk described is time-dependent since homogeneous quantum walks do not converge for arbitrary initial conditions
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.
We set the ground for a theory of quantum walks on graphs- the generalization of random walks on finite graphs to the quantum world. Such quantum walks do not converge to any stationary distribution, as they are unitary and reversible. However, by suitably relaxing the definition, we can obtain a measure of how fast the quantum walk spreads or how confined the quantum walk stays in a small neighborhood. We give definitions of mixing time, filling time, dispersion time. We show that in all these measures, the quantum walk on the cycle is almost quadratically faster then its classical correspondent. On the other hand, we give a lower bound on the possible speed up by quantum walks for general graphs, showing that quantum walks can be at most polynomially faster than their classical counterparts.
We investigate the use of discrete-time quantum walks to sample from an almost-uniform distribution, in the absence of any external source of randomness. Integers are encoded on the vertices of a cycle graph, and a quantum walker evolves for a fixed number of steps before its position is measured and recorded. The walker is then reset to the measured site, and the procedure is iterated to produce the sequence of random numbers. We show that when the quantum walk parameters, such as the coin operator and initial state, satisfy the conditions of the ergodic theorem for random walks on finite groups, the resulting sequence converges asymptotically to the uniform distribution. Although correlations between successive outcomes are unavoidable, they can be significantly reduced by a suitable choice of the evolution time. By analyzing the iterated convolution of the quantum walk transition probability and exploiting the ergodic theorem, we demonstrate convergence of the marginal distributions toward the uniform distribution in the asymptotic limit.
Abstract We investigate the use of discrete-time quantum walks to sample from an almost-uniform distribution, in the absence of any external source of randomness. Integers are encoded on the vertices of a cycle graph, and a quantum walker evolves for a fixed number of steps before its position is measured and recorded. The walker is then reset to the measured site, and the procedure is iterated to generate the sequence of outcomes. We show that when the number of nodes of the graph is odd, i.e. the condition of the ergodic theorem for classical random walks on finite groups are satisfied, the marginal distributions converges to the uniform distribution. Although correlations between successive outcomes are unavoidable, they can be significantly reduced by a suitable choice of the evolution time.