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:1709.06414 · Journal of Statistical Mechanics Theory and Experiment

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

Stefan Boettcher, Joshua L. Pughe-Sanford

Published Mar 1, 2018• 2 citations
arXivHTMLPDF

Abstract

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

DOI
10.1088/1742-5468/aab050

Related papers

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

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

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

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

Revisiting one-dimensional discrete-time quantum walks with general coin

Mahesh N. Jayakody, Chandrakala Meena, Priodyuti Pradhan

Quantum walk (QW) is the quantum analog of the random walk. QW is an integral part of the development of numerous quantum algorithms. Hence, an in-depth understanding of QW helps us to grasp the quantum algorithms. We revisit the one-dimensional discrete-time QW and discuss basic steps in detail by incorporating the most general coin operator, constant in both space and time, and a localized initial state using numerical modeling. We investigate the impact of each parameter of the general coin operator on the probability distribution of the quantum walker. We show that by tuning the parameters of the general coin, one can regulate the probability distribution of the walker. We provide an algorithm for the one-dimensional quantum walk driven by the general coin operator. The study on general coin operators also includes the popular coins – Hadamard, Grover, and Fourier.

Physics Open•Nov 10, 2023•9 citations

Quantum random walks with decoherent coins

Todd A. Brun, Hilary A. Carteret, Andris Ambainis

The quantum random walk has been much studied recently, largely due to its highly nonclassical behavior. In this paper, we study one possible route to classical behavior for the discrete quantum walk on the line: the presence of decoherence in the quantum ``coin'' which drives the walk. We find exact analytical expressions for the time dependence of the first two moments of position, and show that in the long-time limit the variance grows linearly with time, unlike the unitary walk. We compare this to the results of direct numerical simulation, and see how the form of the position distribution changes from the unitary to the usual classical result as we increase the strength of the decoherence.

arXiv:quant-ph/0210180•Physical Review A•Mar 14, 2003•155 citations
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 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.
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.
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 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.
Quantum walk (QW) is the quantum analog of the random walk. QW is an integral part of the development of numerous quantum algorithms. Hence, an in-depth understanding of QW helps us to grasp the quantum algorithms. We revisit the one-dimensional discrete-time QW and discuss basic steps in detail by incorporating the most general coin operator, constant in both space and time, and a localized initial state using numerical modeling. We investigate the impact of each parameter of the general coin operator on the probability distribution of the quantum walker. We show that by tuning the parameters of the general coin, one can regulate the probability distribution of the walker. We provide an algorithm for the one-dimensional quantum walk driven by the general coin operator. The study on general coin operators also includes the popular coins – Hadamard, Grover, and Fourier.
The quantum random walk has been much studied recently, largely due to its highly nonclassical behavior. In this paper, we study one possible route to classical behavior for the discrete quantum walk on the line: the presence of decoherence in the quantum ``coin'' which drives the walk. We find exact analytical expressions for the time dependence of the first two moments of position, and show that in the long-time limit the variance grows linearly with time, unlike the unitary walk. We compare this to the results of direct numerical simulation, and see how the form of the position distribution changes from the unitary to the usual classical result as we increase the strength of the decoherence.