Analysis of Coined Quantum Walks with Renormalization

Abstract

We introduce a new 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 1d-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 ${\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\sqrt{{\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.

arXiv comment9 pages, revtex4, 3 figures, for related information, see http://www.physics.emory.edu/faculty/boettcher/

References in corpus (24)

• Quantum Mechanics helps in searching for a needle in a haystack
• Quantum random walks - an introductory overview
• Universal computation by quantum walk
• Quantum walks: a comprehensive review
• Single-Spin Addressing in an Atomic Mott Insulator
• Two-particle bosonic-fermionic quantum walk via 3D integrated photonics
• From quantum cellular automata to quantum lattice gases
• Realization of quantum walks with negligible decoherence in waveguide lattices
• Anderson localization of entangled photons in an integrated quantum walk
• A 2D Quantum Walk Simulation of Two-Particle Dynamics
• Decoherence and disorder in quantum walks: From ballistic spread to localization
• Continuous-Time Quantum Walks: Models for Coherent Transport on Complex Networks
• Decoherence in quantum walks - a review
• Weak limits for quantum random walks
• One-Dimensional Three-State Quantum Walk
• Decoherence in the quantum walk on the line
• Direct Probe of Topological Invariants Using Bloch Oscillating Quantum Walks
• Quantum walks: the first detected passage time problem
• Weak Limit of the 3-State Quantum Walk on the Line
• Relation between Random Walks and Quantum Walks
• Interacting quantum walkers: Two-body bosonic and fermionic bound states
• Renormalization and Scaling in Quantum Walks
• Driven Topological Systems in the Classical Limit
• Renormalization of the Unitary Evolution Equation for Coined Quantum Walks

Cited by in corpus (14)

• Multifractal Spin-Glass Chaos Projection and Interrelation of Multicultural Music and Brain Signals
• A Lower Lower-Critical Spin-Glass Dimension from Quenched Mixed-Spatial-Dimensional Spin Glasses
• Complete Density Calculations of q-State Potts and Clock Models: Reentrance of Interface Densities under Symmetry Breaking
• Scaling Hypothesis of Spatial Search on Fractal Lattice Using Quantum Walk
• Uncertainty relation between detection probability and energy fluctuations
• Complexity Bounds on Quantum Search Algorithms in finite-dimensional Networks
• Renormalization-Group Theory of the Heisenberg Model in d Dimensions
• Phase Transitions of the Variety of Random-Field Potts Models
• Nematic Ordering in the Heisenberg Spin-Glass System in d=3 Dimensions
• Transport and Localization in Quantum Walks on a Random Hierarchy of Barriers
• Renormalization of Discrete-Time Quantum Walks with non-Grover Coins
• Spin-s Spin-Glass Phases in the d=3 Ising Model
• Quantum Ultra-Walks: Walks on a Line with Hierarchical Spatial Heterogeneity
• Metastable Reverse-Phase Droplets within Ordered Phases: Renormalization-Group Calculation of Field and Temperature Dependence of Limiting Size