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:1410.7034 · Physical Review A

Relation between random walks and quantum walks

Stefan Boettcher, Stefan Falkner, Renato Portugal

Published May 29, 2015• 23 citations
arXivHTMLPDF

Abstract

Based on studies of four specific networks, we conjecture a general relation between the walk dimensions ${d}_{w}$ of discrete-time random walks and quantum walks with the (self-inverse) Grover coin. In each case, we find that ${d}_{w}$ of the quantum walk takes on exactly half the value found for the classical random walk on the same geometry. Since walks on homogeneous lattices satisfy this relation trivially, our results for heterogeneous networks suggest that such a relation holds irrespective of whether translational invariance is maintained or not. To develop our results, we extend the renormalization-group analysis (RG) of the stochastic master equation to one with a unitary propagator. As in the classical case, the solution $\ensuremath{\rho}(x,t)$ in space and time of this quantum-walk equation exhibits a scaling collapse for a variable ${x}^{{d}_{w}}/t$ in the weak limit, which defines ${d}_{w}$ and illuminates fundamental aspects of the walk dynamics, e.g., its mean-square displacement. We confirm the collapse for $\ensuremath{\rho}(x,t)$ in each case with extensive numerical simulation. The exact values for ${d}_{w}$ themselves demonstrate that RG is a powerful complementary approach to study the asymptotics of quantum walks that weak-limit theorems have not been able to access, such as for systems lacking translational symmetries beyond simple trees.

DOI
10.1103/physreva.91.052330

Related papers

Renormalization of the unitary evolution equation for coined quantum walks

Stefan Boettcher, Shanshan Li, Renato Portugal

Abstract We consider discrete-time evolution equations in which the stochastic operator of a classical random walk is replaced by a unitary operator. Such a problem has gained much attention as a framework for coined quantum walks that are essential for attaining the Grover limit for quantum search algorithms in physically realizable, low-dimensional geometries. In particular, we analyze the exact real-space renormalization group (RG) procedure recently introduced to study the scaling of quantum walks on fractal networks. While this procedure, when implemented numerically, was able to provide some deep insights into the relation between classical and quantum walks, its analytic basis has remained obscure. Our discussion here is laying the groundwork for a rigorous implementation of the RG for this important class of transport and algorithmic problems, although some instances remain unresolved. Specifically, we find that the RG fixed-point analysis of the classical walk, which typically focuses on the dominant Jacobian eigenvalue λ 1 , with walk dimension d w R W = log 2 ⁡ λ 1 , needs to be extended to include the subdominant eigenvalue λ 2 , such that the dimension of the quantum walk obtains d w Q W = log 2 ⁡ λ 1 λ 2 . With that extension, we obtain analytically previously conjectured results for d w Q W of Grover walks on all but one of the fractal networks that have been considered.

arXiv:1609.00756•Journal of Physics A Mathematical and Theoretical•Jan 31, 2017•5 citations

Analysis of coined quantum walks with renormalization

Stefan Boettcher, Shanshan Li

We introduce a framework to analyze quantum algorithms with the renormalization group (RG). To this end, we present a detailed analysis of the real-space RG for discrete-time quantum walks on fractal networks and show how deep insights into the analytic structure as well as generic results about the long-time behavior can be extracted. The RG flow for such a walk on a dual Sierpinski gasket and a Migdal-Kadanoff hierarchical network is obtained explicitly from elementary algebraic manipulations, after transforming the unitary evolution equation into Laplace space. Unlike for classical random walks, we find that the long-time asymptotics for the quantum walk requires consideration of a diverging number of Laplace poles, which we demonstrate exactly for the closed-form solution available for the walk on a one-dimensional loop. In particular, we calculate the probability of the walk to overlap with its starting position, which oscillates with a period that scales as ${N}^{{d}_{w}^{Q}/{d}_{f}}$ with system size $N$. While the largest Jacobian eigenvalue ${\ensuremath{\lambda}}_{1}$ of the RG flow merely reproduces the fractal dimension, ${d}_{f}={log}_{2}{\ensuremath{\lambda}}_{1}$, the asymptotic analysis shows that the second Jacobian eigenvalue ${\ensuremath{\lambda}}_{2}$ becomes essential to determine the dimension of the quantum walk via ${d}_{w}^{Q}={log}_{2}\sqrt{{\ensuremath{\lambda}}_{1}{\ensuremath{\lambda}}_{2}}$. We trace this fact to delicate cancellations caused by unitarity. We obtain identical relations for other networks, although the details of the RG analysis may exhibit surprisingly distinct features. Thus, our conclusions---which trivially reproduce those for regular lattices with translational invariance with ${d}_{f}=d$ and ${d}_{w}^{Q}=1$---appear to be quite general and likely apply to networks beyond those studied here.

arXiv:1704.04692•Physical Review A•Jan 12, 2018•18 citations

Renormalization and scaling in quantum walks

Stefan Boettcher, Stefan Falkner, Renato Portugal

We show how to extract the scaling behavior of quantum walks using the renormalization group (RG). We introduce the method by efficiently reproducing well-known results on the one-dimensional lattice. For a nontrivial model, we apply this method to the dual Sierpinski gasket and obtain its exact, closed system of RG recursions. Numerical iteration suggests that under rescaling the system length, ${L}^{\ensuremath{'}}=2L$, characteristic times rescale as ${t}^{\ensuremath{'}}={2}^{{d}_{w}}t$, with the exact walk exponent ${d}_{w}={log}_{2}\sqrt{5}=1.1609...$ Despite the lack of translational invariance, this value is very close to the ballistic spreading, ${d}_{w}=1$, found for regular lattices. However, we argue that an extended interpretation of the traditional RG formalism will be needed to obtain scaling exponents analytically. Direct simulations confirm our RG prediction for ${d}_{w}$ and furthermore reveal an immensely rich phenomenology for the spreading of the quantum walk on the gasket. Invariably, quantum interference localizes the walk completely, with a site-access probability that decreases with a power law from the initial site, in contrast to a classical random walk, which would pass all sites with certainty.

arXiv:1311.3369•Physical Review A•Sep 23, 2014•14 citations

Invariance in Quantum Walks

Miquel Montero

In this Chapter, we present some interesting properties of quantum walks on the line.We concentrate our attention in the emergence of invariance and provide some insights into the ultimate origin of the observed behavior.In the first part of the Chapter, we review the building blocks of the quantum-mechanical version of the standard random walk in one dimension.The most distinctive difference between random and quantum walks is the replacement of the random coin in the former by the action of a unitary operator upon some internal property of the later.We provide explicit expressions for the solution to the problem when the most general form for the homogeneous unitary operator is considered, and we analyze several key features of the system as the presence of symmetries or stationary limits.After that, we analyze the consequences of letting the properties of the coin operator change from site to site, and from time step to time step.In spite of this lack of homogeneity, the probabilistic properties of the motion of the walker can remain unaltered if the coin variability is chosen adequately.Finally, we show how this invariance can be connected to the gauge freedom of electromagnetism.

arXiv:1606.06156•InTech eBooks•Aug 24, 2016•1 citation

Renormalization group for quantum walks

Stefan Boettcher, Stefan Falkner, Renato Portugal

We present a detailed introduction to the discrete-time quantum walk problem, in close analogy with the classical ordinary and persistent random walk. This approach facilitates a uniform application of the renormalization group that highlights similarities and differences between the classical and the quantum walk problem. Specifically, we discuss the renormalization group treatment for the mean-square displacement of a walker starting from a single site on the 1d-line for ordinary and persistent random walks and the quantum walk. We outline the significance of universality for quantum walks and the control this might provide for quantum algorithms. We use our RG method to verify that all 2-state quantum walks on the 1d-line are in the same universality class.

Journal of Physics Conference Series•Dec 16, 2013•11 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
Based on studies of four specific networks, we conjecture a general relation between the walk dimensions dw{d}_{w}dw​ of discrete-time random walks and quantum walks with the (self-inverse) Grover coin. In each case, we find that dw{d}_{w}dw​ of the quantum walk takes on exactly half the value found for the classical random walk on the same geometry. Since walks on homogeneous lattices satisfy this relation trivially, our results for heterogeneous networks suggest that such a relation holds irrespective of whether translational invariance is maintained or not. To develop our results, we extend the renormalization-group analysis (RG) of the stochastic master equation to one with a unitary propagator. As in the classical case, the solution \ensuremathρ(x,t)\ensuremath{\rho}(x,t)\ensuremathρ(x,t) in space and time of this quantum-walk equation exhibits a scaling collapse for a variable xdw/t{x}^{{d}_{w}}/txdw​/t in the weak limit, which defines dw{d}_{w}dw​ and illuminates fundamental aspects of the walk dynamics, e.g., its mean-square displacement. We confirm the collapse for \ensuremathρ(x,t)\ensuremath{\rho}(x,t)\ensuremathρ(x,t) in each case with extensive numerical simulation. The exact values for dw{d}_{w}dw​ themselves demonstrate that RG is a powerful complementary approach to study the asymptotics of quantum walks that weak-limit theorems have not been able to access, such as for systems lacking translational symmetries beyond simple trees.
Abstract We consider discrete-time evolution equations in which the stochastic operator of a classical random walk is replaced by a unitary operator. Such a problem has gained much attention as a framework for coined quantum walks that are essential for attaining the Grover limit for quantum search algorithms in physically realizable, low-dimensional geometries. In particular, we analyze the exact real-space renormalization group (RG) procedure recently introduced to study the scaling of quantum walks on fractal networks. While this procedure, when implemented numerically, was able to provide some deep insights into the relation between classical and quantum walks, its analytic basis has remained obscure. Our discussion here is laying the groundwork for a rigorous implementation of the RG for this important class of transport and algorithmic problems, although some instances remain unresolved. Specifically, we find that the RG fixed-point analysis of the classical walk, which typically focuses on the dominant Jacobian eigenvalue λ 1 , with walk dimension d w R W = log 2 ⁡ λ 1 , needs to be extended to include the subdominant eigenvalue λ 2 , such that the dimension of the quantum walk obtains d w Q W = log 2 ⁡ λ 1 λ 2 . With that extension, we obtain analytically previously conjectured results for d w Q W of Grover walks on all but one of the fractal networks that have been considered.
We introduce a framework to analyze quantum algorithms with the renormalization group (RG). To this end, we present a detailed analysis of the real-space RG for discrete-time quantum walks on fractal networks and show how deep insights into the analytic structure as well as generic results about the long-time behavior can be extracted. The RG flow for such a walk on a dual Sierpinski gasket and a Migdal-Kadanoff hierarchical network is obtained explicitly from elementary algebraic manipulations, after transforming the unitary evolution equation into Laplace space. Unlike for classical random walks, we find that the long-time asymptotics for the quantum walk requires consideration of a diverging number of Laplace poles, which we demonstrate exactly for the closed-form solution available for the walk on a one-dimensional loop. In particular, we calculate the probability of the walk to overlap with its starting position, which oscillates with a period that scales as NdwQ/df{N}^{{d}_{w}^{Q}/{d}_{f}}NdwQ​/df​ with system size NNN. While the largest Jacobian eigenvalue ${\ensuremath{\lambda}}_{1}$ of the RG flow merely reproduces the fractal dimension, ${d}_{f}={log}_{2}{\ensuremath{\lambda}}_{1}$, the asymptotic analysis shows that the second Jacobian eigenvalue ${\ensuremath{\lambda}}_{2}$ becomes essential to determine the dimension of the quantum walk via ${d}_{w}^{Q}={log}_{2}\sqrt{{\ensuremath{\lambda}}_{1}{\ensuremath{\lambda}}_{2}}$. We trace this fact to delicate cancellations caused by unitarity. We obtain identical relations for other networks, although the details of the RG analysis may exhibit surprisingly distinct features. Thus, our conclusions---which trivially reproduce those for regular lattices with translational invariance with df=d{d}_{f}=ddf​=d and dwQ=1{d}_{w}^{Q}=1dwQ​=1---appear to be quite general and likely apply to networks beyond those studied here.
We show how to extract the scaling behavior of quantum walks using the renormalization group (RG). We introduce the method by efficiently reproducing well-known results on the one-dimensional lattice. For a nontrivial model, we apply this method to the dual Sierpinski gasket and obtain its exact, closed system of RG recursions. Numerical iteration suggests that under rescaling the system length, ${L}^{\ensuremath{'}}=2L$, characteristic times rescale as ${t}^{\ensuremath{'}}={2}^{{d}_{w}}t$, with the exact walk exponent dw=log25=1.1609...{d}_{w}={log}_{2}\sqrt{5}=1.1609...dw​=log2​5​=1.1609... Despite the lack of translational invariance, this value is very close to the ballistic spreading, dw=1{d}_{w}=1dw​=1, found for regular lattices. However, we argue that an extended interpretation of the traditional RG formalism will be needed to obtain scaling exponents analytically. Direct simulations confirm our RG prediction for dw{d}_{w}dw​ and furthermore reveal an immensely rich phenomenology for the spreading of the quantum walk on the gasket. Invariably, quantum interference localizes the walk completely, with a site-access probability that decreases with a power law from the initial site, in contrast to a classical random walk, which would pass all sites with certainty.
In this Chapter, we present some interesting properties of quantum walks on the line.We concentrate our attention in the emergence of invariance and provide some insights into the ultimate origin of the observed behavior.In the first part of the Chapter, we review the building blocks of the quantum-mechanical version of the standard random walk in one dimension.The most distinctive difference between random and quantum walks is the replacement of the random coin in the former by the action of a unitary operator upon some internal property of the later.We provide explicit expressions for the solution to the problem when the most general form for the homogeneous unitary operator is considered, and we analyze several key features of the system as the presence of symmetries or stationary limits.After that, we analyze the consequences of letting the properties of the coin operator change from site to site, and from time step to time step.In spite of this lack of homogeneity, the probabilistic properties of the motion of the walker can remain unaltered if the coin variability is chosen adequately.Finally, we show how this invariance can be connected to the gauge freedom of electromagnetism.
We present a detailed introduction to the discrete-time quantum walk problem, in close analogy with the classical ordinary and persistent random walk. This approach facilitates a uniform application of the renormalization group that highlights similarities and differences between the classical and the quantum walk problem. Specifically, we discuss the renormalization group treatment for the mean-square displacement of a walker starting from a single site on the 1d-line for ordinary and persistent random walks and the quantum walk. We outline the significance of universality for quantum walks and the control this might provide for quantum algorithms. We use our RG method to verify that all 2-state quantum walks on the 1d-line are in the same universality class.
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.