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

New Journal of Physics

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

Marco Radaelli, Claudia Benedetti, Stefano Olivares

Published Feb 19, 2026• 0 citations
Publisher

Abstract

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.

DOI
10.1088/1367-2630/ae4820

Related papers

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

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 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 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.

arXiv:2103.06463•Mar 11, 2021•0 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

Universal quantum computation by discontinuous quantum walk

Michael S. Underwood, David L. Feder

Quantum walks are the quantum-mechanical analog of random walks, in which a quantum ``walker'' evolves between initial and final states by traversing the edges of a graph, either in discrete steps from node to node or via continuous evolution under the Hamiltonian furnished by the adjacency matrix of the graph. We present a hybrid scheme for universal quantum computation in which a quantum walker takes discrete steps of continuous evolution. This ``discontinuous'' quantum walk employs perfect quantum-state transfer between two nodes of specific subgraphs chosen to implement a universal gate set, thereby ensuring unitary evolution without requiring the introduction of an ancillary coin space. The run time is linear in the number of simulated qubits and gates. The scheme allows multiple runs of the algorithm to be executed almost simultaneously by starting walkers one time step apart.

arXiv:1008.3578•Physical Review A•Oct 7, 2010•56 citations

A limit theorem for a splitting distribution of a quantum walk

Takuya Machida

Discrete-time quantum walks are considered a counterpart of random walks and their study has been getting attention since around 2000. In this paper, we focus on a quantum walk which generates a probability distribution splitting to two parts. The quantum walker with two coin states spreads at points, represented by integers, and we analyze the chance of finding the walker at each position after it carries out a unitary evolution a lot of times. The result is reported as a long-time limit distribution from which one can see an approximation to the finding probability.

arXiv:1704.04554•International Journal of Quantum Information•Apr 1, 2018•2 citations
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.
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.
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 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 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 the quantum-mechanical analog of random walks, in which a quantum ``walker'' evolves between initial and final states by traversing the edges of a graph, either in discrete steps from node to node or via continuous evolution under the Hamiltonian furnished by the adjacency matrix of the graph. We present a hybrid scheme for universal quantum computation in which a quantum walker takes discrete steps of continuous evolution. This ``discontinuous'' quantum walk employs perfect quantum-state transfer between two nodes of specific subgraphs chosen to implement a universal gate set, thereby ensuring unitary evolution without requiring the introduction of an ancillary coin space. The run time is linear in the number of simulated qubits and gates. The scheme allows multiple runs of the algorithm to be executed almost simultaneously by starting walkers one time step apart.
Discrete-time quantum walks are considered a counterpart of random walks and their study has been getting attention since around 2000. In this paper, we focus on a quantum walk which generates a probability distribution splitting to two parts. The quantum walker with two coin states spreads at points, represented by integers, and we analyze the chance of finding the walker at each position after it carries out a unitary evolution a lot of times. The result is reported as a long-time limit distribution from which one can see an approximation to the finding probability.