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

Renormalization and scaling in quantum walks

Stefan Boettcher, Stefan Falkner, Renato Portugal

Published Sep 23, 2014• 14 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.90.032324

Related papers

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

Relation between random walks and quantum walks

Stefan Boettcher, Stefan Falkner, Renato Portugal

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.

arXiv:1410.7034•Physical Review A•May 29, 2015•23 citations

QUANTUM WALKS ON SIERPINSKI GASKETS

PEDRO CARLOS S. LARA, RENATO PORTUGAL, Stefan Boettcher

We analyze discrete-time quantum walks on Sierpinski gaskets using a flip-flop shift operator with the Grover coin. We obtain the scaling of two important physical quantities: The mean-square displacement, and the mixing time as function of the number of points. The Sierpinski gasket is a fractal that lacks translational invariance and the results differ from those described in the literature for ordinary lattices. We find that the diffusion scaling depends on the initial location. Averaged over all initial locations, our simulation obtain an exponent very similar to the classical diffusion.

arXiv:1209.2095•International Journal of Quantum Information•Dec 1, 2013•12 citations

The localization of quantum random walks on Sierpinski gaskets

Kai Zhao, Wei-Shih Yang

We consider discrete time quantum random walks on a Sierpinski gasket. We study the hitting probability as the level of the fractal graph goes to infinity in terms of their localization exponents βw, total variation exponents δw, and relative entropy exponents ηw. We define and solve the amplitude Green functions recursively when the level of the fractal graph goes to infinity. We obtain exact recursive formulas for the amplitude Green functions, on which the hitting probabilities and expectation of the first-passage time are calculated, and using the recursive formula with the aid of Monte Carlo integration, we evaluate their numerical values. We also show that when the level of the fractal graph goes to infinity, with probability 1, the quantum random walks will return to the origin, i.e., the quantum walks on a Sierpinski gasket are recurrent.

arXiv:2103.10575•Journal of Mathematical Physics•Jan 1, 2022•1 citation

Fractional scaling of quantum walks on percolation lattices

Viv M. Kendon, Godfrey Leung, Joe Bailey +1 more

Quantum walks can be used to model processes such as transport in spin chains and bio-molecules. The enhanced spreading and mixing properties of quantum walks compared with their classical counterparts have been well-studied on regular structures and also shown to be sensitive to defects and imperfections. Using numerical simulation, we study the spreading properties of quantum walks on percolation lattices for both bond and site percolation. The randomly missing edges or sites provide a controlled amount of disorder in the regular Cartesian lattice. In one dimension (the line) we introduce a simple model of quantum tunneling to allow the walk to proceed past the missing edges or sites. This allows the quantum walk to spread faster than a classical random walk for short times, but at longer times the disorder localises the quantum walk. In two dimensions, we observe fractional scaling of the spreading with the number of steps of the walk. For percolation above the 85% level, we obtain faster spreading than classical random walks on the full lattice.

Journal of Physics Conference Series•Mar 1, 2011•2 citations

Quantum phase transition in transverse-field Ising model on Sierpiński gasket lattice

Tymoteusz Braciszewski, Oliwier Urbański, Piotr Tomczak

We investigate the quantum phase transition in the transverse-field Ising model on the Sierpiński gasket using finite-size scaling (FSS) and numerical renormalization group (NRG). Since next generations of the fractal lattice contain exponentially more spins, which in turn increase exponentially the Hilbert space dimension, we challenge and prove usefulness of small systems in FSS. We identified a quantum critical point at $λ_c \approx 2.63 - 2.93$, with critical exponents $ ν\approx 0.64 - 0.71, β\approx 0.30, γ\approx 1.67$ and $z \approx 1.33$. The numerical renormalization group method produced results consistent with finite-size scaling approach ($λ_c = 2.766$$, β= 0.316$), supporting our findings. Compared to the values reported so far in the literature, critical field is in a strong disagreement, while exponents are generally similar excluding $β$ and $γ$. However, it should be noted, that the lattice investigated in previous works is different from ours, while the latter is in our opinion the standard Sierpiński gasket.

cond-mat.stat-mechCross-listedarXiv:2602.02904•Zeitschrift für Naturforschung A•Feb 4, 2026•0 citations
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{L}^{\ensuremath{'}}=2LL\ensuremath′=2L, characteristic times rescale as t\ensuremath′=2dwt{t}^{\ensuremath{'}}={2}^{{d}_{w}}tt\ensuremath′=2dw​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.
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.
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{\rho}(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{\rho}(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.
We analyze discrete-time quantum walks on Sierpinski gaskets using a flip-flop shift operator with the Grover coin. We obtain the scaling of two important physical quantities: The mean-square displacement, and the mixing time as function of the number of points. The Sierpinski gasket is a fractal that lacks translational invariance and the results differ from those described in the literature for ordinary lattices. We find that the diffusion scaling depends on the initial location. Averaged over all initial locations, our simulation obtain an exponent very similar to the classical diffusion.
We consider discrete time quantum random walks on a Sierpinski gasket. We study the hitting probability as the level of the fractal graph goes to infinity in terms of their localization exponents βw, total variation exponents δw, and relative entropy exponents ηw. We define and solve the amplitude Green functions recursively when the level of the fractal graph goes to infinity. We obtain exact recursive formulas for the amplitude Green functions, on which the hitting probabilities and expectation of the first-passage time are calculated, and using the recursive formula with the aid of Monte Carlo integration, we evaluate their numerical values. We also show that when the level of the fractal graph goes to infinity, with probability 1, the quantum random walks will return to the origin, i.e., the quantum walks on a Sierpinski gasket are recurrent.
Quantum walks can be used to model processes such as transport in spin chains and bio-molecules. The enhanced spreading and mixing properties of quantum walks compared with their classical counterparts have been well-studied on regular structures and also shown to be sensitive to defects and imperfections. Using numerical simulation, we study the spreading properties of quantum walks on percolation lattices for both bond and site percolation. The randomly missing edges or sites provide a controlled amount of disorder in the regular Cartesian lattice. In one dimension (the line) we introduce a simple model of quantum tunneling to allow the walk to proceed past the missing edges or sites. This allows the quantum walk to spread faster than a classical random walk for short times, but at longer times the disorder localises the quantum walk. In two dimensions, we observe fractional scaling of the spreading with the number of steps of the walk. For percolation above the 85% level, we obtain faster spreading than classical random walks on the full lattice.
We investigate the quantum phase transition in the transverse-field Ising model on the Sierpiński gasket using finite-size scaling (FSS) and numerical renormalization group (NRG). Since next generations of the fractal lattice contain exponentially more spins, which in turn increase exponentially the Hilbert space dimension, we challenge and prove usefulness of small systems in FSS. We identified a quantum critical point at λc≈2.63−2.93λ_c \approx 2.63 - 2.93λc​≈2.63−2.93, with critical exponents $ ν\approx 0.64 - 0.71, β\approx 0.30, γ\approx 1.67$ and z≈1.33z \approx 1.33z≈1.33. The numerical renormalization group method produced results consistent with finite-size scaling approach (λc=2.766λ_c = 2.766λc​=2.766,β=0.316, β= 0.316,β=0.316), supporting our findings. Compared to the values reported so far in the literature, critical field is in a strong disagreement, while exponents are generally similar excluding βββ and γγγ. However, it should be noted, that the lattice investigated in previous works is different from ours, while the latter is in our opinion the standard Sierpiński gasket.