Transport and Localization in Quantum Walks on a Random Hierarchy of Barriers

Our walks are governed by the discrete-time evolution equation Redner (2001) for the state of the system,

$$\left|\Psi\left(t+1\right)\right\rangle={\cal U}\left|\Psi\left(t\right)\right\rangle$$

(1)

with propagator ${\cal U}$. This propagator is a stochastic operator for a classical, dissipative random walk. But in the quantum case it is unitary and, thus, reversible. Then, in the discrete $N$-dimensional site-basis $\left|x\right\rangle$ of some network, the PDF is given by $\rho\left(x,t\right)=\psi_{x,t}=\left\langle x|\Psi\left(t\right)\right\rangle$ for random walks, or by $\rho\left(x,t\right)=\left|\psi_{x,t}\right|^{2}$ for quantum walks. A discrete Laplace-transform (or “generating function”) Redner (2001) of the site amplitudes

$$\overline{\psi}_{x}\left(z\right)={\textstyle\sum_{t=0}^{\infty}}\psi_{x,t}z^{t}$$

(2)

has all its poles – and hence those for $\overline{\rho}\left(x,z\right)$ – located right on the unit-circle in the complex-$z$ plane Boettcher et al. (2017).

On the 1d-line. the propagator in Eq. (1) is

$${\cal U}={\textstyle\sum_{x}}\left\{A_{x}\left|x+1\right\rangle\left\langle x\right|+B_{x}\left|x-1\right\rangle\left\langle x\right|+M_{x}\left|x\right\rangle\left\langle x\right|\right\}$$

(3)

for nearest-neighbor transitions. While the norm of $\rho$ for random walks merely requires conservation of probability for the hopping coefficients, $A_{x}+B_{x}+M_{x}=1$, for quantum walks it demands unitary propagation, $\mathbb{I}={\cal U}^{\dagger}{\cal U}$. The rules Boettcher et al. (2018) then impose the conditions $\mathbb{I}_{r}=A_{x}^{\dagger}A_{x}+B_{x}^{\dagger}B_{x}+M_{x}^{\dagger}M_{x}$ and $0=A_{x-1}^{\dagger}M_{x}+M_{x}^{\dagger}B_{x+1}=A_{x-1}^{\dagger}B_{x+1}$. This algebra requires at least $r=2$-dimensional matrices, and it is customary Portugal (2013); Venegas-Andraca (2012) to employ the most general unitary coin-matrix,

$${\cal C}=\left(\begin{array}[]{cc}\sin\theta,&e^{i\chi}\,\cos\theta\\ e^{i\vartheta}\cos\theta,&-e^{i\left(\chi+\vartheta\right)}\sin\theta\end{array}\right).$$

(4)

We thus define ${\cal U}={\cal S}\left({\cal C}\otimes\mathbb{I}_{N}\right)$ with shift ${\cal S}$ using matrices $S^{\left\{A,B,M\right\}}$ for transfer in a direction either out of a site or back to itself, i.e., $A=S^{A}{\cal C}$, $B=S^{B}{\cal C}$, and $M=S^{M}{\cal C}$ with $S^{A}+S^{B}+S^{M}=\mathbb{I}_{r}$, where ${\cal C}={\cal C}_{x}$ may be heterogeneous via $x$-dependent parameters. The quantum-coin entangles all $r$ components of $\psi_{x,t}$ and the shift-matrices facilitate the subsequent transitions to neighboring sites. For $r=2$, there are no self-loops ($S^{M}=0,M=0$) and we shift upper (lower) components of each $\psi_{x,t}$ to the right (left) using projectors $S^{A}=\left[\begin{array}[]{cc}1&0\\ 0&0\end{array}\right]$ and $S^{B}=\left[\begin{array}[]{cc}0&0\\ 0&1\end{array}\right]$. Alternatively, these coin-degrees of freedom could be replaced by a “staggered” walk without coin Portugal et al. (2015); Portugal (2016), for which schemes equivalent to the following RG can be developed. Finally, similar considerations apply for walks on networks, such as a fractal, except that the propagator ${\cal U}$ in Eq. (3) is modified to reflect the respective Laplacian.

For a random walk, the probability density $\rho\left(\vec{x},t\right)$ to detect it at time $t$ at site $\vec{x}$, a distance $x=\left|\vec{x}\right|$ from its origin, obeys the collapse with the scaling variable $x/t^{1/d_{w}}$,

$$\rho\left(\vec{x},t\right)\sim t^{-\frac{d_{f}}{d_{w}}}f\left(x/t^{\frac{1}{d_{w}}}\right),$$

(5)

where $d_{w}$ is the walk-dimension and $d_{f}$ is the fractal dimension of the network Havlin and Ben-Avraham (1987). On a translationally invariant lattice of any spatial dimension $d(=d_{f})$, it is easy to show that the walk is always purely “diffusive”, $d_{w}=2$, with a Gaussian scaling function $f$, which is the content of many classic textbooks on random walks and diffusion Feller (1966); Weiss (1994). The scaling in Eq. (5) still holds when translational invariance is broken or the network is fractal (i.e., $d_{f}$ is non-integer). Such “anomalous” diffusion with $d_{w}\not=2$ may arise in many transport processes Havlin and Ben-Avraham (1987); Bouchaud and Georges (1990); Redner (2001). For quantum walks, the only previously known value for a finite walk dimension is that for ordinary lattices Grimmett et al. (2004), where Eq. (5) generically holds with $d_{w}=1$, indicating a “ballistic” spreading of the quantum walk from its origin. This value has been obtained for various versions of one- and higher-dimensional quantum walks, for instance, with so-called weak-limit theorems Konno (2002); Grimmett et al. (2004); Segawa and Konno (2008); Konno (2008); Venegas-Andraca (2012).

In recent work, we have developed RG for discrete-time quantum walk with a coin Boettcher et al. (2013, 2014, 2015, 2017). It expands the analytic tools to understand quantum walks, since it works for networks that lack translational symmetries. Our RG provides principally similar results as in Eq. (5) in terms of the asymptotic scaling variable $x/t^{1/d_{w}}$ (or pseudo-velocity Konno (2005)), whose existence allows to collapse all data for the probability density $\rho\left(\vec{x},t\right)$, aside from oscillatory contributions (“weak limit”). While algebraically laborious, we have developed a simple scheme to obtain RG-flow equations for unitary evolution equations Boettcher and Li (2018). Abstracting from those results, we have conjectured that the fundamental quantum walk dimension $d_{w}$ for a homogeneous walk always is half of that for the corresponding random walk Boettcher et al. (2015),

$$d_{w}^{Q}=\frac{1}{2}\,d_{w}^{R}.$$

(6)

It is not clear how spatial inhomogeneity affects the relation between classical and quantum walks. The ability to explore a given geometry much faster than diffusion is essential for the effectiveness of quantum search algorithms Ambainis (2007); Childs et al. (2003). In fact, using Eq. (6) and the Alexander-Orbach relation Alexander and Orbach (1982), $d_{w}^{R}d_{s}=2d_{f}$, we have shown Boettcher et al. (2018) that attaining Grover’s limit in quantum search on a homogeneous network is determined by its spectral dimension $d_{s}$.

Walks and transport efficiency in disordered environments have been of significant interest, exemplified by the Sinai model Sinai (1982). There have been a few approaches to understand quantum walks with disorder, either through spatially Brun et al. (2003); Segawa and Konno (2008); Konno (2009); Shikano and Katsura (2010); Vakulchyk et al. (2017) or temporally Ribeiro et al. (2004) varying coins. Even less is known about the impact of heterogeneous environments on quantum search efficiency. However, exact quantum models similar to Sinai’s for asymptotic scaling of the displacement in random environments are hard to find. For random walks, models of “ultra-diffusion” with a hierarchy of ultra-metric barriers Teitel and Domany (1985); Ogielski and Stein (1985); Huberman and Kerszberg (1985); Maritan and Stella (1986) have been proposed to study slow relaxation and aging, solved with RG, that allow to interpolate between regular diffusion ($d_{w}=2$) via anomalous sub-diffusion to the full disorder limit ($d_{w}\to\infty$). Even spectral properties of the tight-binding model have been explored Ceccatto et al. (1987).

As a hierarchical model of spatial inhomogeneity, we have considered position-dependent coins, Eq. (4), in such a way that all sites of odd index $x$ share the same coin, and so do all sites that are divisible by $2^{i}$, $i\geq 0$, so that sites of the same value of $i$ have an identical coin, ${\cal C}_{i}$, with hierarchy index $i=i(x)$ based on the (unique) binary decomposition of any integer $x(\not=0)$ Boettcher (2020):

$$x=2^{i}(2j+1),\quad(i\geq 0,-\infty<j<\infty)$$

(7)

Setting uniformly $\vartheta=\chi=0$ in Eq. (4) but choosing

$$\theta_{i}=\theta_{0}\epsilon^{i}\qquad(0<\epsilon\leq 1)$$

(8)

with $\theta_{0}=\frac{\pi}{4}$ , the sequence of such coins becomes ever more reflective for a walker trying to transition through the respective site. Thus, the walker gets confined in a tree-like ultra-metric set of domains with vastly varying timescales for exit. Two neighboring domains at level $i$ form a larger domain at level $i+1$, and so on, from which an ultra-metric hierarchy emerges, as depicted in Fig. 2.

The master equation (1) in Laplace-space with ${\cal U}$ in Eq. (3) becomes $\overline{\psi}_{x}=zM_{x}\overline{\psi}_{x}+zA_{x}\overline{\psi}_{x-1}+zB_{x+1}\overline{\psi}_{x+1}$. For simplicity, we merely consider initial conditions (IC) localized at the origin, $\psi_{x,t=0}=\delta_{x,0}\psi_{IC}$ and define the coin at $x=0$ simply to be the identity matrix. For the RG in Ref. Boettcher (2020), we recursively eliminated $\overline{\psi}_{x}$ for all sites for which $x$ is an odd number ($i=0$), then set $x\to x/2$ ($i\to i-1$) for the remaining sites, and repeat, step-by-step for $k=0,1,2,\ldots$. In each step, we successively eliminate all sites within an entire hierarchy $i$, each with an identical coin ${\cal C}_{i}$, starting at $k=0$ with the “raw” hopping operator $A_{i}^{(0)}=zA_{x(i,j)}$, $B_{i}^{(0)}=zB_{x(i,j)}$, and $M_{i}^{(0)}=zM_{x(i,j)}\equiv 0$. After each step, the master equation becomes self-similar in form by identifying the renormalized hopping operators $A_{i}^{(k)}$, $B_{i}^{(k)}$, $M_{i}^{(k)}$ for all $i>0$ as

	$\displaystyle A_{i-1}^{(k+1)}$	$\displaystyle=$	$\displaystyle A_{0}^{(k)}\left[\mathbb{I}-M_{0}^{(k)}\right]^{-1}A_{i}^{(k)},$
	$\displaystyle B_{i-1}^{(k+1)}$	$\displaystyle=$	$\displaystyle B_{0}^{(k)}\left[\mathbb{I}-M_{0}^{(k)}\right]^{-1}B_{i}^{(k)},$		(9)
	$\displaystyle M_{i-1}^{(k+1)}$	$\displaystyle=$	$\displaystyle M_{i}^{(k)}+A_{0}^{(k)}\left[\mathbb{I}-M_{0}^{(k)}\right]^{-1}B_{i}^{(k)}$		(11)
			$\displaystyle\quad+B_{0}^{(k)}\left[\mathbb{I}-M_{0}^{(k)}\right]^{-1}A_{i}^{(k)}.$

Amazingly, we can entirely eliminate the hierarchy-index $i$: If we define the $k$-th renormalized shift matrices via $\left\{A,B,M\right\}_{i}^{(k)}=S_{k}^{\{A,B,M\}}{\cal C}_{i+k},$ these satisfy the recursions:

	$\displaystyle S_{k+1}^{\{A,B\}}$	$\displaystyle=$	$\displaystyle S_{k}^{\{A,B\}}\left[{\cal C}_{k}^{-1}-S_{k}^{M}\right]^{-1}S_{k}^{\{A,B\}},$		(12)
	$\displaystyle S_{k+1}^{M}$	$\displaystyle=$	$\displaystyle S_{k}^{M}+S_{k}^{A}\left[{\cal C}_{k}^{-1}-S_{k}^{M}\right]^{-1}S_{k}^{B}$		(14)
			$\displaystyle\quad+S_{k}^{B}\left[{\cal C}_{k}^{-1}-S_{k}^{M}\right]^{-1}S_{k}^{A},$

which instead now have an explicit $k$-dependence via the inverse coins ${\cal C}_{k}^{-1}$ of the $k$-th hierarchy.

As a specific physical situation for such a setting, Ref. Boettcher (2020) considered a walk between two absorbing walls of separation $N=2^{l}+1$, equidistant from the starting site $x=2^{l-1}$. As the wall-sites $x=0$ and $x=2^{l}$ a fully absorbing, there is no flow reflecting out of those sites such that at the end of $l-1$ RG-steps, for either wall it is

$$\overline{\psi}_{\left\{0,2\right\}}=S_{l-1}^{\left\{A,B\right\}}\left({\cal C}_{l-1}^{-1}-S_{l-1}^{M}\right)^{-1}\psi_{IC}.$$

(15)

In Ref. Boettcher (2020), the RG calculation yielded for the quantum ultra-walk the walk dimension, as defined in Eq. (5):

$$d_{w}^{Q}=\frac{1}{2}+\frac{1}{2}\log_{2}\left(1+\epsilon^{-2}\right),$$

(16)

which grows without bound for decreasing $\epsilon$, i.e., for increasing barrier heights transports diminishes from ballistic ($d_{w}^{Q}=1$ for $\epsilon=1$) to extremely sub-diffusive for $\epsilon\to 0$. However, it was found numerically that, eventually, the entire weight of the wave function gets absorbed at arbitrarily distant walls for any finite value of $\epsilon$.

Clearly, overlaying this form of extensive randomness with the hierarchical barriers analyzed in Sec. II.3, e.g. by replacing in Eq. (8) the constant $\theta_{0}$ with a random variable $\theta_{x}$ at each site $x$ in addition to the barrier strengths $\epsilon^{-i}$, merely enhances the already observed localization (see Fig. 4 below). In turn, it appears that the question regarding which level of sub-extensive randomness might be required to induce a localization transition is of some interest and can be conveniently studied in the context of such a one-dimensional quantum walk. To this end, specifically, we propose a simple two-parameter family of DTQW on the 1d-line with a combination of regular hierarchical barriers described by $\epsilon$ in combination with hierarchical randomness, manifested by choosing random angles $\theta_{i}$ from the $W$-controlled distribution in Eq. (17) merely for each level $i=i(x)$, as defined in Eq. (7). Indeed, we find evidence for localization transitions both for nontrivial values of $\epsilon$ for $W>0$ as well as of $W$ for $\epsilon<1$, while there is no transition either for $\epsilon=1$ at any value of $W$ or for $W=0$ at any $0<\epsilon\leq 1$ (the case considered in Ref. Boettcher (2020)). In light of the ability to treat this system with RG, see Sec. II.3, this will open the door for high-precision calculations via numerical iteration and disorder-averaging of the (exact) RG-recursion equations in the future.

Our means to determine the existence of those transitions in this study are very simple: For given $\epsilon$ and $W$, we generate multiple instances of placing random angles $\theta_{i}$ drawn from ${\cal P}_{W}$ in Eq. (17) into the coins on all sites $x$ (up to $\left|x\right|\leq L$ with $L=2^{16}$) matching Eq. (7) with that $i$ and any $\left|j\right|\leq L/2^{i+1}$. We note that each instance involves at most a sub-extensive, $O(\log L)$ choice of random angles $\theta_{i}$ that could ever be experienced by the walker while Ref. Vakulchyk et al. (2017) employed an extensive, $O(L)$ selection of random angles $\theta_{x}$. For each instance, we evolve DTQW initiated at $x=0$ for $t_{{\rm max}}=L=2^{16}$ time-steps to measure its mean-square displacement, $\sigma(t)^{2}$, which is the variance of $\rho(x,t)$ defined in Sec. II.1. It immediately follows from Eq. (5) that the root mean square displacement for large times $t$ scales as

$$\sigma(t)\sim t^{1/d_{w}},$$

(18)

from which we can extract the walk dimension $d_{w}$ asymptotically. In Fig. 3, we illustrate this procedure by reproducing the walk dimensions $d_{w}$ in Eq. (16) for various values of $\epsilon$ in the pure quantum ultra-walk without randomness ($W=0$). For any finite value of $d_{w}$ there is still extensive transport occurring, while $d_{w}=\infty$, or $1/d_{w}=0$, would indicate localization. In the quantum ultra-walk, there is no localization for any $\epsilon>0$, not even for any fraction of the wave function Boettcher (2020).

Since we are interested in the asymptotic behavior for large times and distances for the walk, we instead will plot our data for $\sigma(t)$ in form of an extrapolation plot. To this end, we convert $\sigma\sim At^{\frac{1}{d_{w}}}$ in Eq. (18) into

$$\frac{\log{\sigma(t)}}{\log{t}}\sim\frac{1}{d_{w}}+\frac{\log A}{\log{t}}.$$

(19)

When plotted with $X=1/\log t$ versus $Y=\frac{\log{\sigma(t)}}{\log{t}}$, asymptotically, Eq. (19) describes a line from which we can read off $1/d_{w}$ approximately at the intercept $X=0$, i.e., $t=\infty$. We first illustrate this technique in Fig. 4 for simulations employing extensive randomness which recap the findings of Ref. Vakulchyk et al. (2017) (for $\epsilon=1$) and show that localization only gets stronger for higher barriers ($\epsilon=0.6)$. Clearly, in all cases with $W>0$, the extrapolations indicate a vanishing of $1/d_{w}$, making $\sigma(t)$ bounded for large times $t$ as evidence that the walk remains localized.

In the following, we apply the methods developed in Sec. III.2 to the model of a quantum ultra-walk with sub-extensive randomness introduced in Sec. III.1. In Fig. 5, we summarize our data of the walk simulations for various values in the ($\epsilon,W$)-plane. In particular, as shown in Fig. 5(a), for the otherwise homogeneous (barrier-free) 1d quantum walk obtained for $\epsilon=1$, the addition of merely sub-extensive randomness placed hierarchically on the lattice is insufficient to localize the walk for any value of $W$. Even for angles chosen entirely randomly ($W=\pi)$ the walk at most becomes mildly sub-diffusive and $1/d_{w}$ remains far from zero. This is in stark contrast with the corresponding case of extensive randomness Vakulchyk et al. (2017) shown in Fig. 4(a). However, in concert with the hierarchy of barrier that emerges for $\epsilon=0.8$ and $\epsilon=0.6$, as shown in Figs. 5(b,c), such a sub-extensive amount of randomness proves sufficient to induce localization. In fact, it appears that for each of those fixed values of $\epsilon<1$, there is a transition at a finite value of $W$, although it would be possible for that transition to be at $W=0$.

We can summarize our results by sketching out a tentative phase diagram for the localization transition in the plane formed by the set of parameters $(\epsilon,W)$. In Fig. 6, we illustrate the emerging scenario, highlighting the region of localization ($1/d_{w}=0$, in red) from that of transport ($1/d_{w}>0$, in green) with a phase boundary between them estimated from our data. First, the earlier discussion in Sec. II.3 concerning the quantum ultra-walk without any randomness shows that the entire line ($\epsilon,W=0$) is not localized but that the line ($\epsilon=0,W$) for any $W$ certainly is. Thus, the phase boundary must pass the origin ($\epsilon=0,W=0$). While we can not entirely exclude the possibility that that boundary remains at $W=0$ also for most $\epsilon<1$, it is conceivable from Figs. 5(b,c) that for intermediate barrier strengths $\epsilon$ there is a transition at similarly intermediate values $W$, as the two interior marks at $\epsilon=0.6$ and $\epsilon=0.8$ insinuate. The argument for this scenario is strengthened by the fact that the point ($\epsilon=1,W=\pi$), yielding $1/d_{w}\approx 0.3-0.4$ from Fig. 5(a), appears far from localization and, thus, from the phase boundary. Hence, unless there is a discontinuous jump in $d_{w}$, that phase boundary seems to reach full randomness ($W=\pi$) at some value of $\epsilon_{c}$ that might be close to, but is well bounded-away from $\epsilon=1$, as indicated in Fig. 6. Then, either the phase boundary varies gradually between the origin and that point, as shown, or discontinuously jumps at $\epsilon_{c}$ from $W=0$ to $W=\pi$.