Analysis of coined quantum walks with renormalization

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-dwQ/df with system size N. While the largest Jacobian eigenvalue lambda(1) of the RG flow merely reproduces the fractal dimension, d(f) = log(2)lambda(1), the asymptotic analysis shows that the second Jacobian eigenvalue lambda(2) becomes essential to determine the dimension of the quantum walk via d(w)(Q) = log(2)root lambda(1)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.