# Directivity of Quantum Walk via Its Random Walk Replica

Authors: Tomoki Yamagami; Etsuo Segawa; Nicolas Chauvet; André Röhm; Ryoichi Horisaki; Makoto Naruse
Journal: Complexity
 (2022)

---

## Abstract

Quantum walks (QWs) exhibit different properties compared with classical random walks (RWs), most notably by linear spreading and localization. In the meantime, random walks that replicate quantum walks, which we refer to as quantum-walk-replicating random walks (QWRWs), have been studied in the literature where the eventual properties of QWRW coincide with those of QWs. However, we consider that the unique attributes of QWRWs have not been fully utilized in the former studies to obtain deeper or new insights into QWs. In this paper, we highlight the directivity of one-dimensional discrete quantum walks via QWRWs. By exploiting the fact that QWRW allows trajectories of individual walkers to be considered, we first discuss the determination of future directions of QWRWs, through which the effect of linear spreading and localization is manifested in another way. Furthermore, the transition probabilities of QWRWs can also be visualized and show a highly complex shape, representing QWs in a novel way. Moreover, we discuss the first return time to the origin between RWs and QWs, which is made possible via the notion of QWRWs. We observe that the first return time statistics of QWs are quite different from RWs, caused by both the linear spreading and localization properties of QWs.


---

## Body

## 1. Introduction

In this paper, we examine the concept of aquantum-walk-replicating random walk, which we call QWRW. A quantum walk (QW) is often explained as the counterpart of the classical random walk (RW) [1–3]. However, the properties of a quantum walk are quite different from the latter. Quantum walks were first introduced in the field of quantum information theory [4, 5]. After that, the characteristic structure of quantum walks was intensively studied by mathematicians, and since then, quantum walks have been an important topic in both fundamental and applied research. Indeed, quantum walks exhibit versatile behavior depending on conditions or settings of time and space, so there are many studies about their mathematical analysis [6–13]. In addition, their unique behavior is useful for implementing quantum structures or quantum analogs of existing models; therefore, the application is considered in fields such as quantum teleportation [14, 15], time series analysis [16], topological insulators [17, 18], radioactive waste reduction [19, 20], and optics [21]. Moreover, properties of quantum walks have also been simulated numerically [22] or experimentally via the interference of classical light waves [23–25].The particularly unique characteristics of a quantum walk are linear spreading and localization. The former means that the deviation of the distribution of a quantum walk is proportional to its run time. The latter implies that there exist specific positions that have nonzero measurement probability after sufficient time evolution. These interesting properties are, however, not easy to intuitively interpret since they are based on the quantum superposition of multiple states. On the other hand, modified models of classical random walks are widely considered (e.g., correlated random walk [26], Lévy walk [27], and Metropolis walk [28]). Such walks are treated as interesting models not only in the field of mathematics but also in natural science [29], economics [30], and informatics [31], among others. While the distribution of a simple random walk converges to the normal distribution, those of classical random walks, in general, do not necessarily do so, including the ones mentioned above. This is why researchers in many fields are interested in them: they can describe more complex transitions of states in real phenomena.The relationship between quantum walks and modified classical random walks is an active field of study. A related study is given regarding finite graph structures by Andrade et al. [32]. In their study, they show the transition probability matrices of quantum walks as nonhomogeneous random walks. In the study on ℤ, the construction of Markov processes is presented by separating the quantum evolution equation into Markovian and interference terms by Romanelli et al. [33]. The aim of their decomposition is to show that the linear spreading is derived from coherence. That is, if the equation is decoherent, the spread of the probability distribution goes like simple random walks: the standard deviation is Ot, where t is the run time [34, 35]. In the meantime, Montero studied how to obtain the time- and site-dependent coin operator to generate an intended probability distribution on ℤ [36]. Therein, the nonhomogeneous random walk on ℤ exhibiting the identical probability distribution of quantum walk was discussed as a part of interchanging roles.Our study treats the infinite lineℤ and sheds new light on the associated fundamental properties of QWs from the viewpoint of directivity, which is accessible by the notion of QWRWs. In conventional quantum walks, the probability of observing a walker in a particular position is calculated via a coherent sum of all probability amplitudes. On the other hand, a QWRW provides an individual trajectory to reach a position. The probability of observing a walker in a position is calculated via the statistics of individual walkers. In other words, the coherent summation of probability amplitudes is transformed into the transition probabilities of walkers at time n and position x on the line in QWRW, which results in the characteristic directivity of walkers. While there are previous studies on classical analogs of QWs as mentioned above, we consider that the effects of linear spreading or localization in QW are not examined well from such a perspective in the literature. In particular, concerning the fact that one of the remarkable attributes of QWRW is its ability to track the trajectory of individual walkers, we can obtain insights into the properties of QWs regarding directivity.More specifically, we characterize the decision of future directions of QWs, which manifests the effect of linear spreading and localization in an unconventional manner. Furthermore, the transition probabilities of the QWRW are spatially and temporally defined and allow to study characteristics of QWs. Moreover, we examine the first return time of the walkers to the origin after departing the origin with respect to RWs and QWs, which is another interesting aspect examined via the notion of QWRWs. We observe that the first return time statistics of QWs are quite different from RWs.The rest of the paper is organized as follows. Section 2 gives the model of one-dimensional quantum walks and quantum-walk replicating random walks as preparation. In Section 3, we discuss the directivity of quantum walkers by utilizing QWRWs. Beginning with the discussion on the trajectory of quantum walkers, we discuss the decision of future direction, transition probabilities, and the first return time statistics, which all exhibit different characteristics compared with simple random walks. Finally, we give a summary and discussion in Section 4.


## 2. Preliminaries

In this section, we present quantum-walk-replicating random walk (QWRW). First, we define the two-state quantum walk that QWRW is based on. Second, we describe the way of constructing the QWRW. In this study, we limit the target toℤ. We then show that the probability distribution of a QWRW matches that of the corresponding quantum walk by giving an initial condition for both of them.


### 2.1. Quantum Walk

First, we give the following unitary matrix: forx∈ℤ,(1)Cx=axbxcxdx,where ax,bx,cx,dx∈ℂ and axbxcxdx≠0. We call Cx a coin of the quantum walk. Here, we consider the decomposition of C. Let L and R be 1,0T and 0,1T, respectively. Using them, we put(2)Px=LLCx,Qx=RRCx.Then, we obtain(3)Cx=Px+Qx,where Px and Qx give the decomposition of Cx. Px and Qx correspond to the transition probabilities in the context of simple random walks, respectively.For a setn,x∈ℕ0×ℤ, we define the vector Ψnx∈ℂ2. Here, n and x represent the time instant of quantum walks and the position on ℤ, respectively. Then, Ψnx stands for the probability amplitude vector of quantum walks on the position x at the time n. We define the time evolution of quantum walks as follows:(4)Ψn+1x=Px+1Ψnx+1+Qx−1Ψnx−1,which is an analog of the recurrent formula of existence probability of a walker in the context of simple random walks.Finally, for a setn,x, we define(5)μnx=Ψnx2,where μnx now describes the measurement probability of the particle on the position x at the time n.


### 2.2. Quantum-Walk-Replicating Random Walk (QWRW)

In this subsection, we construct QWRWs. For a setn,x∈ℕ0×ℤ such that μnx>0, the transition probabilities of the random walks are defined by the following quantity:(6)pnx=PxΨnx2μnx,qnx=QxΨnx2μnx.Here forpnx and qnx, the following Propositions 1 and 2 hold, which are important to construct the distribution.Proposition 1.
For a setn,x∈ℕ0×ℤsuch thatμnx>0,(7)0≤pnx≤1and0≤qnx≤1.Proof.
Here, we show this proposition forpnx. We can obtain the conclusion for qnx by making a similar discussion.
By the property of norms and the assumptionμnx>0, the inequality(8)0≤pnx,is trivial. We define PL=ax,bx, which leads to PΨnx2=PL|Ψnx2. By Cauchy–Schwarz inequality,(9)PL|Ψnx2≤PL2⋅Ψnx2=ax2+bx2μnx.
Here, the relationshipPL2=ax2+bx2=1 holds by the unitarity of the coin C. Therefore, we obtain the inequality(10)PΨnx2≤μnx⇔pnx=PΨnx2μnx≤1.
Combining (8) and (10), we obtain the desired result.Proposition 2.
For a setn,x∈ℕ0×ℤsuch thatμnx>0,(11)pnx+qnx=1.Proof.
By unitarity of the coinC and Eq. (1), we obtain(12)μnx=Ψnx2=CxΨnx2=PxΨnx+QxΨnx2.
Here, the relational expressionL|R=R|L=0 holds, which leads to(13)PxΨnx+QxΨnx2=PxΨnx2+QxΨnx2.
Therefore,(14)PxΨnx2+QxΨnx2=μnx⇔pnx+qnx=1.
This is the desired equation.By the propositions above, we can define QWRW as follows:Definition 1.
(quantum-walk-replicating random walk (QWRW)).LetΨnn∈ℕ0 be the quantum walk defined by (4), that is,(15)Ψn+1x=Px+1Ψnx+1+Qx−1Ψnx−1,Ψ0x=δ0xφ0.with‖φ0‖=1. The quantum-walk-replicating random walk (QWRW) Snn∈ℕ0 satisfies the following evolution: for n,x∈ℕ0×ℤ such that μnx>0,(16)ℙSn+1=x+ξ|Sn=x=pnx:ξ=−1qnx:ξ=+10:otherwise,where pnx=PxΨnx2/μnx and qnx=PxΨnx2/μnx.Letνnx be the probability that a particle following QWRW (a QWRWer) exists on x∈ℤ at the time n∈ℕ0. In other words, νnx is defined by the initial distribution and the following recurrent formula:(17)νn+1x=pnx+1νnx+1+qnx−1νnx−1.Moreover, we put(18)νn=⋯,νn−1,νn0,νn1,⋯T,and call it the distribution of QWRWs at time n.Incidentally, we have the following lemma:Lemma 1.
Forn∈ℕ0,(19)μn+1x=pnx+1μnx+1+qnx−1μnx−1.Proof.
By Eq. (4),(20)μn+1x=Ψn+1x2=Px+1Ψnx+1+Qx−1Ψnx−12=LCx+1Ψnx+12+R|Cx−1|Ψnx−12=Px+1Ψnx+12+Qx−1Ψnx−12.By the definition of pnx and qnx (6), we obtain the desired conclusion.Using Lemma 1, we obtain the following fact: if and only if we assumeν0=μ0, the distribution of QWRWs and QWs coincidents completely. Therefore, we can draw the following theorem:Theorem 1.
(21)ν0=μ0⇔νn=μnfor alln∈ℕ0.Proof.
We assume that for time instantn∈ℕ0,(22)νn=μn.
Then using the relational expression (17) and the assumption above, we have(23)νn+1x=pnx+1μnx+1+qnx−1μnx−1,for any x∈ℤ. Therefore, by Lemma 1, we obtain the following:(24)νn+1x=μn+1x.
Reminding that this holds for anyx∈ℤ, we obtain the desired conclusion.Here, we compare our theory with previous studies. Our statement extends Theorem 1 in [32] to an infinite graph if we consider numbers of position x∈ℤ as labels of vertices on the infinite graph Gℤ,Eℤ with Eℤ=x,y∈ℤ2‖x−y|=1. Our definition of transition probabilities (6) corresponds to the case that υu,t>0 and u,v∈E in Eq. (16) in their results, which is the case that μnx>0 and x,y∈Eℤ in our contexts. Note that ρv,c,t+1 in their paper corresponds to the left (resp. right) chirality of Ψn+1x−1Ψn+1x+1, whose value matches the left (right) component of PxΨnxQxΨnx. The difference of our study from their result is that the identification between the distribution of quantum walk μn and QWRW νn is the theorem as we showed in Theorem 1 while they assume the match between quantum walk υv,t and nonhomogeneous random walk πvt.In Reference [36], almost the same model is generated as a result of interchanging roles, which solve the problem of how a time- and site-dependent random walk mimics the properties of a quantum walk or the opposite situation. Time- and site-dependent random walk and quantum walk are combined by equating both of the net fluxes, which are(25)JnRWx=qnx−pnxνnx,JnQWx=QΨnx2−PΨnx2,respectively, in our contexts. However, this theory also needs the assumption that the distribution of time- and site-dependent random walk and that of quantum walk are the same, which are described as ρn,t in Reference [36]. In this sense, our introduction of the distribution is made in the opposite direction to their paper.


### 2.3. Demonstrations

Here we show two examples, which are treated in the numerical studies later.Example 1.
(Site-homogeneous model). We set(26)Cx=12111−1for anyx,Ψ00=121i.
In this case, transition and existence probabilities are calculated like Figure1(a). These calculations are detailed in Appendix A. The probability remains the same as the case of a symmetric simple random walk until time n=3. However, the distribution starts to differ at time n=4. From there on, the effects of linear spreading become apparent. The resulting probability distribution νnx appears as Figure 2(a). This graph shows the peaks on the ends; these correspond to linear spreading. Localization does not appear in this case.
The quantum walk model based on this example is well known as one of the most fundamental models of quantum walks and is introduced assymmetric model in Konno [7]. The graph of the probability function also matches that of Figure 3 in Konno [7].Figure 1
Transition of the distributionνn of the QWRW corresponding to (a) Ex. 1 and (b) Ex. 2. Red and blue arrows represent pnx and qnx from each set n,x, respectively. Values on each coordinate n,x represent the corresponding value of νx. For the coordinates that do not have any display about νnx, their values are 0.
(a)(b)Figure 2
Graphical expressions of QWRW for (a) example 1 (site-homogeneous model) and (b) example 2 (one-defect model). The upper figure of each panel illustrates the space-time diagrams of the probability distribution. Circular markers are located at the coordinatesn,x such that νnx>0 with their color indicating the value of νnx. The darker the color is, the larger the value of νnx is. The lower figure of each panel shows probability distribution of QWRW νnx at the time instant n=500, which exactly matching the distribution of the original QWs.
(a)(b)Figure 3
Paths of individual walkers in QWRWs for final timeN=500 and 100 walkers for (a) example 1 (site-homogeneous model), (b) example 2 (one-defect model), and (c) simple random walk. The linear spreading of quantum walks is visible as quasiballistic trajectories towards the edges. Paths staying around the origin in Ex. 2 (b) localization by the defect coin in the quantum walk.
(a)(b)(c)Example 2.
(One-defect model). We set(27)Cx=1001x=012111−1x≠0,Ψ00=121i.
In this case, transition and existence probabilities are calculated like Figure1(b). These calculations are detailed in Appendix A. The probability is the same as the case of symmetric simple random walks until n=4. However, at time n=5 QWRWers are likely to go outside on x=±1, which results in a different probability distribution from the symmetric simple random walk. The resulting probability distribution νnx is shown in Figure 2(b). While this example has peaks on the ends similar to Ex. 1, it also has an extremely high peak on the origin, as this example shows both linear spreading and localization.
The quantum walk model based on this example is often calledone-defect quantum walk, which exhibits localization at x=0 as well as linear spreading.


## 2.1. Quantum Walk

First, we give the following unitary matrix: forx∈ℤ,(1)Cx=axbxcxdx,where ax,bx,cx,dx∈ℂ and axbxcxdx≠0. We call Cx a coin of the quantum walk. Here, we consider the decomposition of C. Let L and R be 1,0T and 0,1T, respectively. Using them, we put(2)Px=LLCx,Qx=RRCx.Then, we obtain(3)Cx=Px+Qx,where Px and Qx give the decomposition of Cx. Px and Qx correspond to the transition probabilities in the context of simple random walks, respectively.For a setn,x∈ℕ0×ℤ, we define the vector Ψnx∈ℂ2. Here, n and x represent the time instant of quantum walks and the position on ℤ, respectively. Then, Ψnx stands for the probability amplitude vector of quantum walks on the position x at the time n. We define the time evolution of quantum walks as follows:(4)Ψn+1x=Px+1Ψnx+1+Qx−1Ψnx−1,which is an analog of the recurrent formula of existence probability of a walker in the context of simple random walks.Finally, for a setn,x, we define(5)μnx=Ψnx2,where μnx now describes the measurement probability of the particle on the position x at the time n.


## 2.2. Quantum-Walk-Replicating Random Walk (QWRW)

In this subsection, we construct QWRWs. For a setn,x∈ℕ0×ℤ such that μnx>0, the transition probabilities of the random walks are defined by the following quantity:(6)pnx=PxΨnx2μnx,qnx=QxΨnx2μnx.Here forpnx and qnx, the following Propositions 1 and 2 hold, which are important to construct the distribution.Proposition 1.
For a setn,x∈ℕ0×ℤsuch thatμnx>0,(7)0≤pnx≤1and0≤qnx≤1.Proof.
Here, we show this proposition forpnx. We can obtain the conclusion for qnx by making a similar discussion.
By the property of norms and the assumptionμnx>0, the inequality(8)0≤pnx,is trivial. We define PL=ax,bx, which leads to PΨnx2=PL|Ψnx2. By Cauchy–Schwarz inequality,(9)PL|Ψnx2≤PL2⋅Ψnx2=ax2+bx2μnx.
Here, the relationshipPL2=ax2+bx2=1 holds by the unitarity of the coin C. Therefore, we obtain the inequality(10)PΨnx2≤μnx⇔pnx=PΨnx2μnx≤1.
Combining (8) and (10), we obtain the desired result.Proposition 2.
For a setn,x∈ℕ0×ℤsuch thatμnx>0,(11)pnx+qnx=1.Proof.
By unitarity of the coinC and Eq. (1), we obtain(12)μnx=Ψnx2=CxΨnx2=PxΨnx+QxΨnx2.
Here, the relational expressionL|R=R|L=0 holds, which leads to(13)PxΨnx+QxΨnx2=PxΨnx2+QxΨnx2.
Therefore,(14)PxΨnx2+QxΨnx2=μnx⇔pnx+qnx=1.
This is the desired equation.By the propositions above, we can define QWRW as follows:Definition 1.
(quantum-walk-replicating random walk (QWRW)).LetΨnn∈ℕ0 be the quantum walk defined by (4), that is,(15)Ψn+1x=Px+1Ψnx+1+Qx−1Ψnx−1,Ψ0x=δ0xφ0.with‖φ0‖=1. The quantum-walk-replicating random walk (QWRW) Snn∈ℕ0 satisfies the following evolution: for n,x∈ℕ0×ℤ such that μnx>0,(16)ℙSn+1=x+ξ|Sn=x=pnx:ξ=−1qnx:ξ=+10:otherwise,where pnx=PxΨnx2/μnx and qnx=PxΨnx2/μnx.Letνnx be the probability that a particle following QWRW (a QWRWer) exists on x∈ℤ at the time n∈ℕ0. In other words, νnx is defined by the initial distribution and the following recurrent formula:(17)νn+1x=pnx+1νnx+1+qnx−1νnx−1.Moreover, we put(18)νn=⋯,νn−1,νn0,νn1,⋯T,and call it the distribution of QWRWs at time n.Incidentally, we have the following lemma:Lemma 1.
Forn∈ℕ0,(19)μn+1x=pnx+1μnx+1+qnx−1μnx−1.Proof.
By Eq. (4),(20)μn+1x=Ψn+1x2=Px+1Ψnx+1+Qx−1Ψnx−12=LCx+1Ψnx+12+R|Cx−1|Ψnx−12=Px+1Ψnx+12+Qx−1Ψnx−12.By the definition of pnx and qnx (6), we obtain the desired conclusion.Using Lemma 1, we obtain the following fact: if and only if we assumeν0=μ0, the distribution of QWRWs and QWs coincidents completely. Therefore, we can draw the following theorem:Theorem 1.
(21)ν0=μ0⇔νn=μnfor alln∈ℕ0.Proof.
We assume that for time instantn∈ℕ0,(22)νn=μn.
Then using the relational expression (17) and the assumption above, we have(23)νn+1x=pnx+1μnx+1+qnx−1μnx−1,for any x∈ℤ. Therefore, by Lemma 1, we obtain the following:(24)νn+1x=μn+1x.
Reminding that this holds for anyx∈ℤ, we obtain the desired conclusion.Here, we compare our theory with previous studies. Our statement extends Theorem 1 in [32] to an infinite graph if we consider numbers of position x∈ℤ as labels of vertices on the infinite graph Gℤ,Eℤ with Eℤ=x,y∈ℤ2‖x−y|=1. Our definition of transition probabilities (6) corresponds to the case that υu,t>0 and u,v∈E in Eq. (16) in their results, which is the case that μnx>0 and x,y∈Eℤ in our contexts. Note that ρv,c,t+1 in their paper corresponds to the left (resp. right) chirality of Ψn+1x−1Ψn+1x+1, whose value matches the left (right) component of PxΨnxQxΨnx. The difference of our study from their result is that the identification between the distribution of quantum walk μn and QWRW νn is the theorem as we showed in Theorem 1 while they assume the match between quantum walk υv,t and nonhomogeneous random walk πvt.In Reference [36], almost the same model is generated as a result of interchanging roles, which solve the problem of how a time- and site-dependent random walk mimics the properties of a quantum walk or the opposite situation. Time- and site-dependent random walk and quantum walk are combined by equating both of the net fluxes, which are(25)JnRWx=qnx−pnxνnx,JnQWx=QΨnx2−PΨnx2,respectively, in our contexts. However, this theory also needs the assumption that the distribution of time- and site-dependent random walk and that of quantum walk are the same, which are described as ρn,t in Reference [36]. In this sense, our introduction of the distribution is made in the opposite direction to their paper.


## 2.3. Demonstrations

Here we show two examples, which are treated in the numerical studies later.Example 1.
(Site-homogeneous model). We set(26)Cx=12111−1for anyx,Ψ00=121i.
In this case, transition and existence probabilities are calculated like Figure1(a). These calculations are detailed in Appendix A. The probability remains the same as the case of a symmetric simple random walk until time n=3. However, the distribution starts to differ at time n=4. From there on, the effects of linear spreading become apparent. The resulting probability distribution νnx appears as Figure 2(a). This graph shows the peaks on the ends; these correspond to linear spreading. Localization does not appear in this case.
The quantum walk model based on this example is well known as one of the most fundamental models of quantum walks and is introduced assymmetric model in Konno [7]. The graph of the probability function also matches that of Figure 3 in Konno [7].Figure 1
Transition of the distributionνn of the QWRW corresponding to (a) Ex. 1 and (b) Ex. 2. Red and blue arrows represent pnx and qnx from each set n,x, respectively. Values on each coordinate n,x represent the corresponding value of νx. For the coordinates that do not have any display about νnx, their values are 0.
(a)(b)Figure 2
Graphical expressions of QWRW for (a) example 1 (site-homogeneous model) and (b) example 2 (one-defect model). The upper figure of each panel illustrates the space-time diagrams of the probability distribution. Circular markers are located at the coordinatesn,x such that νnx>0 with their color indicating the value of νnx. The darker the color is, the larger the value of νnx is. The lower figure of each panel shows probability distribution of QWRW νnx at the time instant n=500, which exactly matching the distribution of the original QWs.
(a)(b)Figure 3
Paths of individual walkers in QWRWs for final timeN=500 and 100 walkers for (a) example 1 (site-homogeneous model), (b) example 2 (one-defect model), and (c) simple random walk. The linear spreading of quantum walks is visible as quasiballistic trajectories towards the edges. Paths staying around the origin in Ex. 2 (b) localization by the defect coin in the quantum walk.
(a)(b)(c)Example 2.
(One-defect model). We set(27)Cx=1001x=012111−1x≠0,Ψ00=121i.
In this case, transition and existence probabilities are calculated like Figure1(b). These calculations are detailed in Appendix A. The probability is the same as the case of symmetric simple random walks until n=4. However, at time n=5 QWRWers are likely to go outside on x=±1, which results in a different probability distribution from the symmetric simple random walk. The resulting probability distribution νnx is shown in Figure 2(b). While this example has peaks on the ends similar to Ex. 1, it also has an extremely high peak on the origin, as this example shows both linear spreading and localization.
The quantum walk model based on this example is often calledone-defect quantum walk, which exhibits localization at x=0 as well as linear spreading.


## 3. Directivity of QWRWers

In this section, we introduce graphical representations of QWRW as our main results. Comparing them with those of simple random walk, whose walkers go to both sides with probability1/2 regardless of time and site, we point out how linear spreading and localization play roles as walk controllers.


### 3.1. Trajectories

One of the significant benefits of QWRWs is that the notion of the path of a walker is valid because the walker follows a classical probability at each position. A real quantum walk is not a stochastic process, so it is not permitted to observe its path in such a classical way. In this regard, QWRW plays an important role as the visualizer of quantum walks. Here, we demonstrate the path trajectories of the walkers of QWRWs.The curves in Figures3(a) and 3(b) show the path trajectories of the walkers of QWRWs, which correspond to Exs. 1 and 2, respectively. For comparison, we also show the path trajectories of simple random walk in Figure 3(c). The horizontal and vertical axes, respectively, denote time and position. The number of walkers shown therein is 100.There are many paths that spread towards the end sections resulting in linear spreading. While in genuine QW, linear spreading and localization are the effects of many interfering wave amplitudes, in QWRWs this effect can be observed as a trace of an individual walker.In Figure3(a), the corresponding QWRW has the property of linear spreading, but does not exhibit localization. Linear spreading carries walkers radially, and the range of terminus of walkers is much wider than that of simple random walkers. Moreover, the farther from the origin the position is, the higher the density of walkers, which corresponds to the highest peaks of the probability distribution shown in Figure 2.On the other hand, in Figure3(b), both linear spreading and localization work on walkers. As with Ex. 1, some walkers leave away from the origin. However, many walkers wander around the origin, which is a clear difference from the previous example. Furthermore, comparing the area −200<x<200 with Figure 3(a), the center area except for the origin is almost free of walkers. This range is also much narrower than the running range of the simple random walker. These different observations from Ex. 1 are affected by localization. This property catches walkers and prevents them from leaving away. Meanwhile, the walkers that are not captured by localization go far under the influence of linear spreading. Eventually, walkers are divided between far travelers and stayers on the origin.


### 3.2. Future Direction

We further examine the properties made observable by QWRWs through the analysis of individual trajectories. Here, the final time instant is given byN∈ℕ. Let K be the number of walkers of QWRWs or the simple random walk and Snk as the position of the k-th walkers at time n with k∈K and n∈N0. Moreover, using them, we define rn as the following to characterize the relevance of the current (time: n) position and the future (time: N) position:(28)rn=1K×#k∈K|sgnSNksgnSnk=1.Here,sgnSNksgnSnk=1 means that the k-th walker is on the same side as the final position with respect to the origin at time n. On the other hand, sgnSNksgnSnk=−1 means that the k-th walker is on the opposite side of the final position with respect to the origin at time n. In this way, sgnSNksgnSnk is the benchmark to investigate when walkers effectively determine the directions they arrive in the future. If a walker maintains sgnSNksgnSnk=1, we can interpret the walker determines its own evolving direction. Based on that, we can consider that rn is a figure-of-merit to investigate the ratio of walkers that determines their future direction.The red and green curves in Figure4(a) show rn regarding QWRWs of Exs. 1 and 2, respectively. In addition, the blue curve in Figure 4(a) indicates rn for the simple random walk.Figure 4
(a) Degree of deciding future direction is characterized through the analysis of paths derived via QWRWs or the simple random walk (N=499, K=100000). According to Eq. (26), walkers are counted to the numerator of rn in the only case that the sign at time n matches the final one. Note that it is not counted in case of Sn=0. QWRWs of Exs. 1 and 2 exhibit a dramatic increase right after the initial time, which is another manifestation of linear spreading. (b) The 2-term moving variance (MV) vn of rn. QWRW of Ex. 2 exhibits a larger variance, which clearly indicates localization.
(a)(b)We can clearly observe thatrn of QWRWs increases dramatically soon after the time evolution begins after n=0, that is, the future direction of a walker is highly determined by the position in its early stage. This observation is affected by linear spreading; this property pulls walkers from the origin and prevents returning there again. On the other hand, the jump-up of rn of the one-defect QWRW (Ex. 2) is not higher than that of the no-defect QWRWs (Ex. 1) and maintains the value within a certain range. In addition, even after rn of Ex. 2 is reached and overtaken by that of the simple random walk, the stay of value continues, and at the very end, goes to 1. This is the effect that localization makes some walkers wander around the origin, which repeats crossing x=0.Another observable feature is oscillation. The ratiorn gets higher and lower value when n is odd and even, respectively, which causes oscillation for all the curves. This is because some walkers are on the origin at even time instance because they are not counted on the numerator of rn (see (27)). In response to this fact, we set the final time instance of this simulation as an odd number so as to have rn reach 1 in the end. The amplitude of oscillation can be estimated by the 2-term moving variance vn of rn by the following equation, see Appendix A for details.(29)vn=14rn2−2rnrn−1+5rn−12.The results are shown in Figure4(b). We observe that vn decreases dramatically right after the jump-up in QWRWs of Ex. 1. This is because most of the walkers leave from the origin right away with linear spreading and never return there again. Conversely, in QWRW of Ex. 2, vn does not exhibit a drastic decrease, which stays at a constant value of approximately 10−2. This means that many walkers of the one-defect QWRW wander around the origin right before the final time; that is, the effect of the other characteristics of quantum walks: localization.


### 3.3. Transition Probability

We examine the expressions of transition probabilitiespnx and qnx. The sum of pnx and qnx is equal to 1; hence, our interest is in the imbalances between pnx and qnx. The red and red portion of the color bars in Figure 5 indicate the amount of pnx and qnx, respectively.Figure 5
Transition probabilitiesp500x and q500x for QWRWs generated from QWs for (a) Ex. 1 (site-homogeneous) and (b) Ex. 2 (one-defect). It holds that p500x+q500x=1, so left (p500x, blue) and right (q500x, orange) transition probabilities are expressed as a stacked bar graph.
(a)(b)Figure 6
(a) Relationship between timenf and the ratio of walkers whose first return time is the time, which is described as Rnf (N=104, K=100000). (b) Cumulative value of Rnf, whose setting is the same as (a). In case of simple random walk, site-homogeneous QWRW, and one-defect QWRW, R10000 is approximately 0.992, 0.613, and 0.699, respectively.
(a)(b)A common attribute observed in Figures5(a) and 5(b) is that there are peaks of pnx and qnx on the left and right sides, respectively. For x≤−350 and x≥350, all examples have identical transition probabilities, following a simple quasicontinuous function of x. This part of the transition probabilities indicates that individual walkers that go far away from the origin tend to go farther, which is related to the linear spreading property of QWs.In the center region of Figure5, the transition probabilities are fluctuating quickly as a function of x. These fluctuations are calm around the origin, but they are violent outside x=±50. The exact position and height of these maxima and minima in pnx and qnx also change with n. The causes of these fluctuations are not clarified, but we hypothesize that they are the classical representation of self-interference of the quantum walkers.A significant difference between two examples shown in Figure5 is the distribution around the origin. In Figure 5(a), pnx exhibits a peak on the left side of the origin while qnx shows a peak on the right side of the origin. This means that the QWRWers starting from the origin equally likely go to the left side or to the right side. This is strongly related to the fact that the probability distribution νnx in Ex. 1 exhibits its highest peaks on both left and right sides (Figure 2(a)).On the other hand, in Figure5(b), pnx and qnx show the local maximum on the right and left sides, respectively, meaning that the QWRWers are guided toward opposite directions alternatively around the origin. Namely, QWRWers are highly likely locked in around the origin, which is a manifestation of localization (Figure 2(b)). This is considered to be a result of the defect located near the origin. Furthermore, from the transition probabilities calculated via QWRWs, we can foresee certain underlying smooth structures plus highly oscillatory ones in Figures 5(a) and 5(b), which is one of the interesting future studies.


### 3.4. FirstReturn Time

The first return time concerns whether a walker departing from the origin comes back to the origin and if so, the first return time is the time when the walker comes back to the origin first, which is denoted bynf . This is one of the interesting figures to characterize the directivity of walkers. It is well known that the probability of a walker to be back to the origin at time nf for a symmetric one-dimensional random walk follows power law nf3/2. Furthermore, the cumulative return probability is 1, meaning that the random walker surely comes back to the origin at some moment.Fig. 6(a) summarizes the fraction of walkers whose first return time is timenf, which is denoted by R(nf). The blue, red, and green curves represent the result with respect to simple RW, site-homogeneous QWRW, and one-defect QWRW, respectively. Here we run in a total of 100,000 random walkers. The simple RW (red curve) in Fig. 6(a) follows the abovementioned nf3/2 trend. In addition, Fig. 6(b) characterizes the cumulative value of R(nf) as a function of nf. It should be noted that the red curve by the simple RW is approaching unity, manifesting that the return probability of simple RW is one.In contrast, the site-homogeneous QWRW exhibits smallerR(nf) values for any nf than simple RW in Fig. 6(a), which indicates that the walker is less likely to come back to the origin at time nf than for a simple RW. Indeed, in Fig. 6(b), the cumulative value of R(nf) undergoes a plateau, indicating strongly that some of the walkers never return to the origin. This is another manifestation of the linear spreading of QW in the format of the first return time discussion. Indeed, the red curve in Fig. 6(a) approximately numerically follows power-law statistics with nf−2. A strict derivation of this distribution could give further insights into the behavior of the QWRWs, but so far this remains an open challenge.In the one-defect model (green curve),R(nf) shows the same order of value as that of simple RW until nf = 8, but after that, it drastically decreases. This indicates that the defect coin strongly pulls some walkers back to the origin by localization to the origin (until nf = 8), but such a character quickly decays, and most of the walkers run away because of linear spreading. Similar to the former site-homogeneous case, the cumulative value of R(nf) sees a plateau, indicating that some of the walkers spread away from the origin. At the same time, it should be noted that the cumulative value of R(nf) by one-defect QW is larger than that by site-homogeneous QW, indicating that the localization by the defect contributes to the increase of the returns of the walkers.Connecting the results of the future direction (Fig. 4) and first return time (Fig. 6), we can also see that approximately 38% of walkers for site-homogeneous QWRW never return to the origin, which means that their future direction must stay on the same side after timen = 1. Indeed, compared with future directions shown in Fig. 4(a), r(n) is larger than about 0.38. Similarly, for all the models of walk and time instance n, r(n) is larger than the cumulative value of R(n), and the difference is related to the walkers that cross the origin several times because of wandering.


## 3.1. Trajectories

One of the significant benefits of QWRWs is that the notion of the path of a walker is valid because the walker follows a classical probability at each position. A real quantum walk is not a stochastic process, so it is not permitted to observe its path in such a classical way. In this regard, QWRW plays an important role as the visualizer of quantum walks. Here, we demonstrate the path trajectories of the walkers of QWRWs.The curves in Figures3(a) and 3(b) show the path trajectories of the walkers of QWRWs, which correspond to Exs. 1 and 2, respectively. For comparison, we also show the path trajectories of simple random walk in Figure 3(c). The horizontal and vertical axes, respectively, denote time and position. The number of walkers shown therein is 100.There are many paths that spread towards the end sections resulting in linear spreading. While in genuine QW, linear spreading and localization are the effects of many interfering wave amplitudes, in QWRWs this effect can be observed as a trace of an individual walker.In Figure3(a), the corresponding QWRW has the property of linear spreading, but does not exhibit localization. Linear spreading carries walkers radially, and the range of terminus of walkers is much wider than that of simple random walkers. Moreover, the farther from the origin the position is, the higher the density of walkers, which corresponds to the highest peaks of the probability distribution shown in Figure 2.On the other hand, in Figure3(b), both linear spreading and localization work on walkers. As with Ex. 1, some walkers leave away from the origin. However, many walkers wander around the origin, which is a clear difference from the previous example. Furthermore, comparing the area −200<x<200 with Figure 3(a), the center area except for the origin is almost free of walkers. This range is also much narrower than the running range of the simple random walker. These different observations from Ex. 1 are affected by localization. This property catches walkers and prevents them from leaving away. Meanwhile, the walkers that are not captured by localization go far under the influence of linear spreading. Eventually, walkers are divided between far travelers and stayers on the origin.


## 3.2. Future Direction

We further examine the properties made observable by QWRWs through the analysis of individual trajectories. Here, the final time instant is given byN∈ℕ. Let K be the number of walkers of QWRWs or the simple random walk and Snk as the position of the k-th walkers at time n with k∈K and n∈N0. Moreover, using them, we define rn as the following to characterize the relevance of the current (time: n) position and the future (time: N) position:(28)rn=1K×#k∈K|sgnSNksgnSnk=1.Here,sgnSNksgnSnk=1 means that the k-th walker is on the same side as the final position with respect to the origin at time n. On the other hand, sgnSNksgnSnk=−1 means that the k-th walker is on the opposite side of the final position with respect to the origin at time n. In this way, sgnSNksgnSnk is the benchmark to investigate when walkers effectively determine the directions they arrive in the future. If a walker maintains sgnSNksgnSnk=1, we can interpret the walker determines its own evolving direction. Based on that, we can consider that rn is a figure-of-merit to investigate the ratio of walkers that determines their future direction.The red and green curves in Figure4(a) show rn regarding QWRWs of Exs. 1 and 2, respectively. In addition, the blue curve in Figure 4(a) indicates rn for the simple random walk.Figure 4
(a) Degree of deciding future direction is characterized through the analysis of paths derived via QWRWs or the simple random walk (N=499, K=100000). According to Eq. (26), walkers are counted to the numerator of rn in the only case that the sign at time n matches the final one. Note that it is not counted in case of Sn=0. QWRWs of Exs. 1 and 2 exhibit a dramatic increase right after the initial time, which is another manifestation of linear spreading. (b) The 2-term moving variance (MV) vn of rn. QWRW of Ex. 2 exhibits a larger variance, which clearly indicates localization.
(a)(b)We can clearly observe thatrn of QWRWs increases dramatically soon after the time evolution begins after n=0, that is, the future direction of a walker is highly determined by the position in its early stage. This observation is affected by linear spreading; this property pulls walkers from the origin and prevents returning there again. On the other hand, the jump-up of rn of the one-defect QWRW (Ex. 2) is not higher than that of the no-defect QWRWs (Ex. 1) and maintains the value within a certain range. In addition, even after rn of Ex. 2 is reached and overtaken by that of the simple random walk, the stay of value continues, and at the very end, goes to 1. This is the effect that localization makes some walkers wander around the origin, which repeats crossing x=0.Another observable feature is oscillation. The ratiorn gets higher and lower value when n is odd and even, respectively, which causes oscillation for all the curves. This is because some walkers are on the origin at even time instance because they are not counted on the numerator of rn (see (27)). In response to this fact, we set the final time instance of this simulation as an odd number so as to have rn reach 1 in the end. The amplitude of oscillation can be estimated by the 2-term moving variance vn of rn by the following equation, see Appendix A for details.(29)vn=14rn2−2rnrn−1+5rn−12.The results are shown in Figure4(b). We observe that vn decreases dramatically right after the jump-up in QWRWs of Ex. 1. This is because most of the walkers leave from the origin right away with linear spreading and never return there again. Conversely, in QWRW of Ex. 2, vn does not exhibit a drastic decrease, which stays at a constant value of approximately 10−2. This means that many walkers of the one-defect QWRW wander around the origin right before the final time; that is, the effect of the other characteristics of quantum walks: localization.


## 3.3. Transition Probability

We examine the expressions of transition probabilitiespnx and qnx. The sum of pnx and qnx is equal to 1; hence, our interest is in the imbalances between pnx and qnx. The red and red portion of the color bars in Figure 5 indicate the amount of pnx and qnx, respectively.Figure 5
Transition probabilitiesp500x and q500x for QWRWs generated from QWs for (a) Ex. 1 (site-homogeneous) and (b) Ex. 2 (one-defect). It holds that p500x+q500x=1, so left (p500x, blue) and right (q500x, orange) transition probabilities are expressed as a stacked bar graph.
(a)(b)Figure 6
(a) Relationship between timenf and the ratio of walkers whose first return time is the time, which is described as Rnf (N=104, K=100000). (b) Cumulative value of Rnf, whose setting is the same as (a). In case of simple random walk, site-homogeneous QWRW, and one-defect QWRW, R10000 is approximately 0.992, 0.613, and 0.699, respectively.
(a)(b)A common attribute observed in Figures5(a) and 5(b) is that there are peaks of pnx and qnx on the left and right sides, respectively. For x≤−350 and x≥350, all examples have identical transition probabilities, following a simple quasicontinuous function of x. This part of the transition probabilities indicates that individual walkers that go far away from the origin tend to go farther, which is related to the linear spreading property of QWs.In the center region of Figure5, the transition probabilities are fluctuating quickly as a function of x. These fluctuations are calm around the origin, but they are violent outside x=±50. The exact position and height of these maxima and minima in pnx and qnx also change with n. The causes of these fluctuations are not clarified, but we hypothesize that they are the classical representation of self-interference of the quantum walkers.A significant difference between two examples shown in Figure5 is the distribution around the origin. In Figure 5(a), pnx exhibits a peak on the left side of the origin while qnx shows a peak on the right side of the origin. This means that the QWRWers starting from the origin equally likely go to the left side or to the right side. This is strongly related to the fact that the probability distribution νnx in Ex. 1 exhibits its highest peaks on both left and right sides (Figure 2(a)).On the other hand, in Figure5(b), pnx and qnx show the local maximum on the right and left sides, respectively, meaning that the QWRWers are guided toward opposite directions alternatively around the origin. Namely, QWRWers are highly likely locked in around the origin, which is a manifestation of localization (Figure 2(b)). This is considered to be a result of the defect located near the origin. Furthermore, from the transition probabilities calculated via QWRWs, we can foresee certain underlying smooth structures plus highly oscillatory ones in Figures 5(a) and 5(b), which is one of the interesting future studies.


## 3.4. FirstReturn Time

The first return time concerns whether a walker departing from the origin comes back to the origin and if so, the first return time is the time when the walker comes back to the origin first, which is denoted bynf . This is one of the interesting figures to characterize the directivity of walkers. It is well known that the probability of a walker to be back to the origin at time nf for a symmetric one-dimensional random walk follows power law nf3/2. Furthermore, the cumulative return probability is 1, meaning that the random walker surely comes back to the origin at some moment.Fig. 6(a) summarizes the fraction of walkers whose first return time is timenf, which is denoted by R(nf). The blue, red, and green curves represent the result with respect to simple RW, site-homogeneous QWRW, and one-defect QWRW, respectively. Here we run in a total of 100,000 random walkers. The simple RW (red curve) in Fig. 6(a) follows the abovementioned nf3/2 trend. In addition, Fig. 6(b) characterizes the cumulative value of R(nf) as a function of nf. It should be noted that the red curve by the simple RW is approaching unity, manifesting that the return probability of simple RW is one.In contrast, the site-homogeneous QWRW exhibits smallerR(nf) values for any nf than simple RW in Fig. 6(a), which indicates that the walker is less likely to come back to the origin at time nf than for a simple RW. Indeed, in Fig. 6(b), the cumulative value of R(nf) undergoes a plateau, indicating strongly that some of the walkers never return to the origin. This is another manifestation of the linear spreading of QW in the format of the first return time discussion. Indeed, the red curve in Fig. 6(a) approximately numerically follows power-law statistics with nf−2. A strict derivation of this distribution could give further insights into the behavior of the QWRWs, but so far this remains an open challenge.In the one-defect model (green curve),R(nf) shows the same order of value as that of simple RW until nf = 8, but after that, it drastically decreases. This indicates that the defect coin strongly pulls some walkers back to the origin by localization to the origin (until nf = 8), but such a character quickly decays, and most of the walkers run away because of linear spreading. Similar to the former site-homogeneous case, the cumulative value of R(nf) sees a plateau, indicating that some of the walkers spread away from the origin. At the same time, it should be noted that the cumulative value of R(nf) by one-defect QW is larger than that by site-homogeneous QW, indicating that the localization by the defect contributes to the increase of the returns of the walkers.Connecting the results of the future direction (Fig. 4) and first return time (Fig. 6), we can also see that approximately 38% of walkers for site-homogeneous QWRW never return to the origin, which means that their future direction must stay on the same side after timen = 1. Indeed, compared with future directions shown in Fig. 4(a), r(n) is larger than about 0.38. Similarly, for all the models of walk and time instance n, r(n) is larger than the cumulative value of R(n), and the difference is related to the walkers that cross the origin several times because of wandering.


## 4. Summary and Discussion

In this study, we examine the directivity of quantum walks via its random walk replica, which is called quantum-walk-replicating random walk (QWRW). Although the theoretical approach to deal with quantum walks in classical random walks (i.e., QWRW) has been studied in the literature, the insights and viewpoints made possible by QWRW are not well characterized, especially the directivity of quantum walks. We start with the derivation of trajectories of QWRW, followed by the demonstration of transition probabilities to left and right, which coincides with the linear spreading and localization properties of QW. Furthermore, we demonstrate that the future direction of QWRW is determined at the very early stage of the time evolution, which is another representation of the linear spreading attribute. Finally, the first return time of QWRW is examined where the scaling properties are different from the simple RW. With the site-homogeneous coin and one-defect coin examples, we can clearly observe the linear spreading and localization effects in the first return time statistics.For future studies, more avenues of research remain. A deeper mathematical understanding of QWRWs is desirable, and several open questions remain. For example: what is the asymptotic behavior of transition probabilitieslimn⟶∞pnx and limn⟶∞qnx for each x∈ℤ? Can the metrics to describe the future directions be represented by an analytical formula? Besides, quantum walks strongly depend on initial conditions as studied in Reference [37]; therefore, the initial state dependency is a promising future direction to QWRW.So far, the coin operator has also been restricted to be a Hermitian matrix. Extension to non-Hermitian systems [38, 39] would significantly enhance the generality of the related discussions.The present study only examines single-particle systems. QWRW approaches for multiparticle systems, including entanglement, could provide even deeper insights into the relationship between classical RWs and QWs. Entangled QWRWs could also potentially have computational advantages over full quantum simulations, although this remains an open question.In particular, QWRWs generate walkers exhibiting equivalent statistics as the measurement result of a QW. Computationally, the cost is also much lower under certain assumptions; once the transition probabilities at timen and the position x are known, calculating an individual trajectory of the QWRW is very fast and will be On for trajectories until time n. A comparable QW would necessarily need to calculate the fully selfinteracting wave function, which requires matrix products and is On2.However, in our current work, the correct transition probabilitiespn are directly calculated from the wave function, which requires a complete QW simulation initially, as this is how we ensure that the resulting QWRW shares all important properties with the original QW. As related thoughts in Andrade et al. [32] outline, there are potential cases where pn could be obtained directly. In those cases, which for now appear to be rare, a simulation of QWRW would overall be more efficient than a QW simulation. Whether it is possible to obtain the transition probabilities pn and qn in general through some clever formulae that avoid calculating the wave function of the corresponding QW remains an open problem.Besides the numerical simulation of QWRWs, the physical implementation of QWRWs is an intriguing issue. In QWRW, the walker transits to the left or right depending on the transition probability at any given time and position. This could be implemented physically, for example, in a mechanical system where a ball, the walker, rolling down a plane encounters an array of pins that deflect the ball to left or right in a probabilistic manner, just like in “pachinko” [40]. The precision of the deflection rates may, however, turn out to be a limiting factor for large QWRW. To its advantage, such a mechanical system also ensures an effectively discrete-time evolution of the ball’s pathway, corresponding to the rows in a classical “pachinko” machine. Ultimately, much faster physical processes may also allow for the construction of quasi-“pachinko” machines, such as electronics or photonics.A QWRW trajectory can also be the starting point of further applications. In the literature, a chaotically oscillating time series has been experimentally utilized in efficiently solving multiarmed bandit problems [41]. Furthermore, Okada et al. [42] demonstrated a theoretical model that accounts for the acceleration of solving the two-armed bandit problem within the framework of correlated random walks. These findings imply that a QWRW may be an exciting resource for solving such bandit problems.



---

*Source: 9021583-2022-10-29.xml*