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

Analysis of coined quantum walks with renormalization

Stefan Boettcher, Shanshan Li

Published Jan 12, 2018• 18 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.97.012309

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

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

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 RANDOM WALK ON FRACTALS

Kai Zhao

Quantum walks are the quantum mechanical analogue of classical random walks. Discrete-time quantum walks have been introduced and studied mostly on the line Z or higher dimensional space Z d but rarely defined on graphs with fractal dimensions because the coin operator depends on the position and the Fourier transform on the fractals is not defined. Inspired by its nature of classical walks, different quantum walks will be defined by choosing different shift and coin operators. When the coin operator is uniform, the results of classical walks will be obtained upon measurement at each step. Moreover, with measurement at each step, our results reveal more information about the classical random walks. In this dissertation, two graphs with fractal dimensions will be considered. The first one is Sierpinski gasket, a degree-4 regular graph with Hausdorff di- mension of df = ln 3/ ln 2. The second is the Cantor graph derived like Cantor set, with Hausdorff dimension of df = ln 2/ ln 3. The definitions and amplitude functions of the quantum walks will be introduced. The main part of this dissertation is to derive a recursive formula to compute the amplitude Green function. The exiting probability will be computed and compared with the classical results. When the generation of graphs goes to infinity, the recursion of the walks will be investigated and the convergence rates will be obtained and compared with the classical counterparts.

•Jan 1, 2018•0 citations

Renormalization of discrete-time quantum walks with a non-Grover coin

Stefan Boettcher, Joshua L. Pughe-Sanford

Abstract We present an in-depth analytic study of discrete-time quantum walks driven by a non-reflective coin. Specifically, we compare the properties of the widely-used Grover coin C G that is unitary and reflective ( C G 2 = I ) with those of a 3 × 3 ‘rotational’ coin C 60 that is unitary but non-reflective ( C 60 2 ≠ I ) and satisfies instead C 60 6 = I , which corresponds to a rotation by 60 ∘ . While such a modification apparently changes the real-space renormalization group (RG) treatment, we show that nonetheless this non-reflective quantum walk remains in the same universality class as the Grover walk. We first demonstrate the procedure with C 60 for a three-state quantum walk on a one-dimensional ( 1d ) line, where we can solve the RG-recursions in closed form in a process providing exact solutions for some difficult non-linear recursions. Then, we apply the procedure to a quantum walk on a dual Sierpinski gasket (DSG), for which we ultimately reproduce the same results found for C G

arXiv:1709.06414•Journal of Statistical Mechanics Theory and Experiment•Mar 1, 2018•2 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
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λ1{\ensuremath{\lambda}}_{1}\ensuremathλ1​ of the RG flow merely reproduces the fractal dimension, df=log2\ensuremathλ1{d}_{f}={log}_{2}{\ensuremath{\lambda}}_{1}df​=log2​\ensuremathλ1​, the asymptotic analysis shows that the second Jacobian eigenvalue \ensuremathλ2{\ensuremath{\lambda}}_{2}\ensuremathλ2​ becomes essential to determine the dimension of the quantum walk via dwQ=log2\ensuremathλ1\ensuremathλ2{d}_{w}^{Q}={log}_{2}\sqrt{{\ensuremath{\lambda}}_{1}{\ensuremath{\lambda}}_{2}}dwQ​=log2​\ensuremathλ1​\ensuremathλ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.
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 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.
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.
Quantum walks are the quantum mechanical analogue of classical random walks. Discrete-time quantum walks have been introduced and studied mostly on the line Z or higher dimensional space Z d but rarely defined on graphs with fractal dimensions because the coin operator depends on the position and the Fourier transform on the fractals is not defined. Inspired by its nature of classical walks, different quantum walks will be defined by choosing different shift and coin operators. When the coin operator is uniform, the results of classical walks will be obtained upon measurement at each step. Moreover, with measurement at each step, our results reveal more information about the classical random walks. In this dissertation, two graphs with fractal dimensions will be considered. The first one is Sierpinski gasket, a degree-4 regular graph with Hausdorff di- mension of df = ln 3/ ln 2. The second is the Cantor graph derived like Cantor set, with Hausdorff dimension of df = ln 2/ ln 3. The definitions and amplitude functions of the quantum walks will be introduced. The main part of this dissertation is to derive a recursive formula to compute the amplitude Green function. The exiting probability will be computed and compared with the classical results. When the generation of graphs goes to infinity, the recursion of the walks will be investigated and the convergence rates will be obtained and compared with the classical counterparts.
Abstract We present an in-depth analytic study of discrete-time quantum walks driven by a non-reflective coin. Specifically, we compare the properties of the widely-used Grover coin C G that is unitary and reflective ( C G 2 = I ) with those of a 3 × 3 ‘rotational’ coin C 60 that is unitary but non-reflective ( C 60 2 ≠ I ) and satisfies instead C 60 6 = I , which corresponds to a rotation by 60 ∘ . While such a modification apparently changes the real-space renormalization group (RG) treatment, we show that nonetheless this non-reflective quantum walk remains in the same universality class as the Grover walk. We first demonstrate the procedure with C 60 for a three-state quantum walk on a one-dimensional ( 1d ) line, where we can solve the RG-recursions in closed form in a process providing exact solutions for some difficult non-linear recursions. Then, we apply the procedure to a quantum walk on a dual Sierpinski gasket (DSG), for which we ultimately reproduce the same results found for C G
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.