Zishi Chen(陳子石) and Xueyuan Hu(胡雪元)

School of Information Science and Engineering,Shandong University,Qingdao 266237,China

Keywords: coherence,quantum walk,probability distribution

1. Introduction

Although CW is widely applied,there also exist a number of restrictions for CW to solve some special problems. Hence many variants are essential to develop to adapt to the problems,such as biased diffusions and reinforced random walk.[13-17]Classical random walk with memory (CWM) is one of these variants. In CWM, the move of the walker is also on a line in a discrete manner. After n=1 step, the probability of the walker’s position x=±1 is 1/2. Then the walker continues in its forward direction with the probability pfand returns to its last position with the probability 1 ?pfinstead of flipping a coin as in CW.[16,18]

Quantum walk (QW) is widely applied in physics,quantum computation, quantum information theory, and so on.[19-30]QW that we discuss is the discrete-time QW. Using the quantum coin and the“flip operations”instead of flipping the coin as in CW, the walker moves on a line in a discrete manner through the moving operations. There are also several proposed models of quantum walks with memory(QWM).[31-33]Therefore,it is necessary to compare CW,CWM, QW, and QWM in this section. In this paper, we just discuss one-dimensional walks. The one-dimensional order-2 QWM is compared with CW and QWM through simulating in Ref. [31]. Indeed, in this case, CWM is equivalent to CW because their probabilities are equivalent. Furthermore,in Ref.[18],CW,CWM,and QW are compared based on their variances, which can reflect these models’ spreading speeds.QW is a useful tool for building algorithms because of its faster spreading speed than CW’s. However, as discussed in Ref. [18], CWM could have a faster spreading than that of QW conditioned on a finite number of the steps. Therefore,it would be interesting to find a model that includes CW and CWM as special cases,such that by varying its parameters,it can fit into different algorithms.

The quantumness of QW is related to coherence.[12,34,35]To explore the quantumness of QW,it is important to find out what kind of models are not quantum. Intuitively, the quantumness of QW originates from the superposition of the paths.Such superposition comes from the initial coherence contained in the initial state of the coin, as well as the coherence generated by the “flip operation” in each step. Therefore, it is natural to regard the walks, which can be realized classically as those with an initially incoherent coin and coherence nongenerating “flip operations”. Further, it is also interesting to study how the initial coherence contained in the coin can affect the quantumness of QW.To explore the relationship between coherence and QW,we ask the following problem: what is the behavior of QW when the involved operations are restricted to the coherence non-generating channels.

In this paper, we discuss how quantum coherence of the initial coin influences the probability distribution under coherence non-generating channels. Firstly, we briefly review how to describe CW in the language of the density matrix.Then we use the language of the density matrix to describe CWM and define a model called generalized classical random walk with memory (GCWM). Similar to CW and CWM, GCWM can also be depicted in the language of the density matrix. Finally,we find the probability distributions of quantum walks under a class of coherence generating channels are GCWM.Also,we find that for another class of coherence non-generating channels,the probability distributions are influenced by the coherence in the initial state of the coin. Nevertheless,the influence degrades as the number of steps increases.

2. The description of classical random walk and two of its variants in the language of the density matrix

In this section,how to use the language of the density matrix to describe CW is briefly reviewed.[36]CWM and GCWM can be described in the same way. Let {|x〉,x ∈Z} be the eigenstates of walker’s position operator and yields an orthonormal basis for the walker’s Hilbert space Hw. As described above,the walk is driven by a coin,which belongs to a two-dimensional quantum system Hcspanned by the orthonormal basis |±〉. Make |+〉and |?〉represent the head and tail of the coin,respectively. We can make a general assumption:regardless of the way of the walker’s move, the total density matrix of walker and coin after n steps is

where axnand bxndepend on the position x and step n.

2.1. Classical random walk

According to the rule of CW,after n+1 steps,the density matrix in CW is

Equations(1)and(2)reveal the relation between the density matrix after n steps and after n+1 steps in CW,which is helpful for following discussions.

2.2. Classical random walk with memory

Similarly,CWM can be described in the language of density matrix. The initial position density matrix of the walker is|0〉〈0|. After n=1 step,the total density matrix is

The total density matrix is Eq. (1) after n steps. So in CWM,after n+1 steps,the density matrix is

Therefore,if we want to describe CWM,Eqs.(4)and(5)need be achieved. Meanwhile, another meaning is given for CWM instead of the coin flip in CW: the probability that the coin has no change is pf; 1 ?pfmeans the probability that the coin is overturned. In CWM,the probability distribution is dependent on the coin’s ability to remain its state.

2.3. Generalized classical random walk with memory

We have to define GCWM for the following discussions.Give the walker a coin before it starts moving. The coin is head at the probability q, and the probability of tail is 1 ?q.When the walker starts moving and the coin is head,the probability that the coin remains head is pf+and the probability that the coin becomes tail is 1 ?pf+. While the coin is tail,the probability that the tail remains tail is pf?and the probability that the coin turns head is 1 ?pf?. In the same way, in GCWM,after n=1 steps,the density matrix is

In GCWM, the relationship between the density matrix between n steps and n+1 steps can be thereby derived. After n steps,the density matrix is Eq.(1). So after n+1 steps,the total density matrix is

In fact, CW and CWM are included in GCWM. It is more understandable in probability theory than the density matrix. Some events need be described: H represents the event that the coin is head after n steps,T represents the event that the coin is tail after n steps, F represents the event that the walker moves in its forward direction after n+1 steps,and R represents the event that the walker returns to its last position after n+1 steps. So in GCWM, P(F|H) = pf+,P(R|H)=1 ?pf+,P(F|T)= pf?and P(R|T)=1 ?pf?. For CW,P(F|H)=P(R|T)=p and P(R|H)=P(F|T)=1?p. In CWM,P(F|H)=P(F|T)=pfand P(R|H)=P(R|T)=1?pf.Meanwhile, for CWM, the probability at x=1 and x=?1 equals 1/2 when the number of step is 1.

Proposition 1pf+= p and pf?=1 ?p is the sufficient and necessary condition for the proposition that GCWM degrades into CW.

ProofThe sufficiency of the condition is easy to discuss.Plug pf+=p and pf?=1?p into Eq.(6)and find that Eq.(6)is equivalent to Eq.(2)when pf+=p and pf?=1?p.

The necessity of the condition need further deduction.Comparing Eqs.(2)and(6),if GCWM can degrade into CW,the relation should be satisfied as follows:

Simplify Eq.(7),the equation becomes

Equation (8) always stands up for every axnand bxn. So pf+=p and pf?=1?p. Hence,the proposition is proven.

Proposition 2pf+= pf?= pfand q=1/2 is the sufficient and necessary condition for the proposition that GCWM degrades CW.

ProofThe discussion is similar to Proposition 1. Plug pf+= pf?= pfand q=1/2 into Eq.(5)and find that Eq.(5)is equivalent to Eq. (3). When pf+= pf?= pf, Eq. (6) is in fact Eq. (4), which illustrates that GCWM can degrade into CWM.The sufficiency of the condition is proved.

The necessity of the condition is also similar to Proposition 1. Thus the detailed process of proof can be simplified here. Comparing Eqs. (4) and (6) gives an impression that pf+= pf?= pf,which can be proved in the same way as Proposition 1.Then get two binary equations when comparing Eqs.(3)and(5)and plugging pf+=pf?=pf

By solving Eq. (9), Eq. (3) can also be satisfied for any pfwhen q=1/2. So the necessity of the condition is proved.

Therefore, the relationship between CM, CWM, and GCWM can be drawn. Figure 1 shows the comparison between CW,CWM,and GCWM.

Fig.1. The comparison between CW,CWM,and GCWM.

3. Quantum walk and the walk under channels

QW just replaces the classical coin with the quantum coin.[12]The quantum coin is operated to generate QW.Some operators are chosen to change the state of the coin to supersede the coin flip. These operators are usually unitary matrixes. After flipping the coin, the walker needs to move through the moving operation. Each step of QW is given

Utilizing quantum channels can also generate QW, because the unitary operators are included in quantum channels.So the formulation of the walk driven by quantum channels is written as

It is necessary to discuss the effect of S(·) on the nondiagonal elements of the coin. Suppose that after n steps,the total density matrix is

To get the density matrix of the coin, the partial trace should be operated

Then let the channel I?E(·) operate on the coin. The total density matrix is

The coin density matrix is

Finally,S(·)works. The final total density matrix is

The coin density matrix is

From Eq.(17), it is found that S(·)only influences nondiagonal elements of the coin density matrix. The point is meaningful for coherence non-generating channels.

4. The walk under coherence non-generating channels

In Ref. [37], rank-2 qubit channels that do not generate coherence are divided into two following categories:

When Λ2is chosen

To explore the influence of the coherence, non-diagonal elements should be as large as possible when the channel works. When Λ1is chosen, it may be a good choice that ξ =0 according to Eq. (22). When Λ2is chosen, it should choose ξ =0 to make the influence of non-diagonal elements obvious. Meanwhile, η =0 is to keep new non-diagonal elements large to the greatest extent. Observing Eqs. (22) and(23), diagonal elements do not participate in the operation of non-diagonal elements under coherence non-generating channels. Meanwhile,the effect of the coin non-diagonal elements only needs considering when Λ2is chosen because in Eq.(22)the coin non-diagonal elements do not participate in the operation of diagonal elements. Therefore,the discussion is divided into two parts.

4.1. The walk under Λ1(·)

Fig.2. The curves of (ρ(n))are shown in(a)within 30 steps. (b)shows the curves of (ρcoin(n)). (c) shows the curves of N(ρ(n)). The initial coin is C0= ,and θ is fixed at θ =75?.

In Fig.2,we have the following observations:

1. The coherence of the composed system never increases.This is because the operations involved are incoherent operations.

2. When θ =φ, the coherence of the composed system is preserved. This is because the anti-diagonal elements of the state of the coin are not affected when θ =φ.

3. The coherence of the coin oscillates.This oscillation is due to the interconversion of coherence and entanglement under incoherent operations.Precisely,when the number of steps is odd, the moving operator S transforms the coherence of the coin to the entanglement between the coin and the walker.When the number of steps is even,part of the entanglement is transformed back to the coherence of the coin. See Figs.2(b)and 2(c)for a comparison.

After n steps,the probability at x is

Equation (24) shows that diagonal elements of the total density matrix decide the probability distribution of the walk.Due to Eq. (22), the measured result of the operation is not affected under Λ1(·) regardless of the quantum coherence of the initial coin. So in the view of the probability distribution,the coin with coherence is equivalent to the coin without coherence. The part of Eq.(16)that can be measured is

From Eq.(22),

Reviewing Eq.(6),the probability distribution of the walk under Λ1(·) is GCWM when cos2θ = pf+and cos2φ = pf?.So when cos2θ = p and cos2φ =1?p,the walk under Λ1(·)can degrade into CW where cos2θ = p and cos2φ =1 ?p.Figure 3 shows the probability distribution of the walk under Λ1(·) when cos2θ = p and cos2φ =1 ?p. In Fig.3. these distributions show features of CW such as symmetry and gaussian like distribution. So utilizing Λ1(·)can generate the probability distribution of CW when cos2θ=p and cos2φ=1?p,which illustrates the validity of our conclusion on the other hand.

Fig.3. When the initial coin density matrix is C0 = , the probability distributions of the walk under Λ1(·) are shown after 30 steps at cos2 θ = p and cos2 φ =1 ?p in order to simulate CW. The points whose probabilities equal 0 are ignored for the sake of convenient calculation and intuitive understanding. It is the same with the following pictures.

To get the probability distribution of CWM,diagonal elements of the initial coin should equal 0.5 and cos2θ =cos2φ.Figure 4 shows the probability distribution of the walk under Λ1(·)when cos2φ =cos2θ = pf. When pfapproaches 0,the probability distribution is closer to the center. While pfapproaches 1, the probability distribution tends to move further from the center,which is a visual feature of CWM.

Fig.4. When the initial coin density matrix is C0= ,the probability distributions of the walk under Λ1(·)are shown after 30 steps at cos2 φ =cos2 θ =pf in order to simulate CWM.

4.2. The walk under Λ2(·)

When the initial coin does not have coherence, the walk under Λ2(·) responds to the walk under Λ1(·) where φ =θ.Similarly,we show Fig.5. by measuring the coherence of the walk and the coin.

In Fig.5,we have the following observations:

1. These curves reveal the tendency of the coherence of the walk only depends on θ compared(a)and(c).

2. When n is large enough,the coherence of the coin declines faster in(d)than(a).

3. There still exists the revival of the coherence of the coin. Meanwhile, these curves reveal that the revival of the coin is limited due to their downtrend. This oscillation behavior is similar to the walk under Λ1(·). However, different from Λ1(·), the effect of the non-diagonal elements has to be taken into consideration under Λ2(·). Therefore,under certain conditions,when n is not rather large,the influence can fluctuate visibly,and when n is large enough,the influence may be insignificant.

To illustrate this point, the concept of relative entropy should be introduced. Suppose that there are P = {pi}iand Q={qi}i, the relative entropy is defined by D(P||Q)=∑ipi(log pi?logqi) to measure how different they are. For Λ2(·),P is the probability distribution driven by the coin with coherence, while Q is driven by the same coin only without coherence. The reason why CW is not considered is that the walk under Λ2(·)belongs to GCWM.So the walk under Λ2(·)is able to generate CWM,which can make relative entropy increase with steps when CW is chosen as Q. In Eq. (23), the non-diagonal elements turn to diagonal elements with sinθ and remain non-diagonal elements with cosθ, which seems that θ =45?may be a good choice.Figure 4 shows the change of relative entropy.

In Fig.6,when φ =75?the curve reaches the maximum value at n=5 and Fig.7 shows the probability distributions P and Q respectively when n takes different values. The oscillation of these curves reveals that the influence of the coherence of the coin is related to the parity of the number of steps,which reflects the revival of coherence of the coin.

Comparing Figs. 7(a), 7(b), and 7(d), when φ =75?the influence of the coherence mainly embodies at the center of the distribution and the influence vanish when odd n is large enough. When n is even, the relative entropy of the case of n=20 is relatively large in Fig.6, but P is nearly coincident with Q, which reflects that the influence is not pronounced when n is even.

Fig.5. The curves of (ρ(n))are shown in(a)and(c)within 30 steps. (b)and(d)show the curves of (ρcoin(n)). φ is fixed at φ =45?in(a)and(b)within 30 steps. θ is fixed at θ =45?in(c)and(d). The initial coin is C0=. In(c),the curves of (ρ(n))coincide.

5. Conclusion

We discuss probability distributions under rank-2 qubit coherence non-generating channels and find that only utilizing quantum coherence of the initial coin seems impossible to get a walk that can be influenced powerfully and continuously by coherence under these channels. The probability distribution depends on the diagonal elements of the coin under Λ1(·)regardless of whether there exists coherence. Taking advantage of this channel, a model, which can include CW and CWM,is defined as GCWM. The walk, which we can get by Λ1(·),belongs to GCWM in the view of the probability distribution.Furthermore,under Λ2(·),the influence of coherence tends to vanish when the number of steps is large enough.