Analysis of coined quantum walks with renormalization

Stefan Boettcher and Shanshan Li
Phys. Rev. A 97, 012309 – Published 12 January 2018

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 NdwQ/df with system size N. While the largest Jacobian eigenvalue λ1 of the RG flow merely reproduces the fractal dimension, df=log2λ1, the asymptotic analysis shows that the second Jacobian eigenvalue λ2 becomes essential to determine the dimension of the quantum walk via dwQ=log2λ1λ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 and dwQ=1—appear to be quite general and likely apply to networks beyond those studied here.

  • Figure
  • Figure
  • Figure
  • Received 8 May 2017

DOI:https://doi.org/10.1103/PhysRevA.97.012309

©2018 American Physical Society

Physics Subject Headings (PhySH)

Statistical Physics & ThermodynamicsQuantum Information, Science & Technology

Authors & Affiliations

Stefan Boettcher and Shanshan Li

  • Department of Physics, Emory University, Atlanta, Georgia 30322, USA

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 97, Iss. 1 — January 2018

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review A

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×