A weak limit theorem for quantum walks on the half-line Chaobin Liu1 Nelson Petulante2 3 Abstract 1 0 For a discrete two-state quantum walk on the half-line, we formu- 2 late and prove a weak limit theorem describing the terminal behavior n of its transition probabilities. In this context, localization is possible a even for a walk predicated on the assumption of homogeneity. For J the Hadamard walk on the half line, the weak limit is shown to be 8 independent of the initial coin state and to exhibit no localization. ] h p - 1 Introduction t n a The notion of quantum walks (QW) originated in 1993 with the publication u q of [1]. Since then, inspired by the ideas in [2, 3, 4], and propelled, in no small [ measure, by the hypothetical prospect of application to the development of 2 super-efficient quantum algorithms, this field of research has flourished im- v 9 mensely. For a lively and informative elaboration of the history of quantum 0 walks and their connection to quantum computing, the reader is referred to 1 [5, 6, 7, 8, 9, 10]. 1 . Among numerous other valuable results, Konno et al. [11, 12, 13] have 2 1 formulated and proved a weak limit theorem for the transition probabilities 2 of discrete unitary quantum walks on the full line (dynamically restricted 1 : to integer nodes). In this work, we formulate and prove an analogous result v i for quantum walks on the half-line (dynamically restricted to non-negative X integer nodes). Specifically, in this paper, we adopt the model of unitary r a discrete quantum walks on the half-line as proposed by Cantero et al. [14]. For a QW of this kind, much effort has been dedicated to studying the asymptotic behavior of its site-specific return probabilities and the mass point aspect of these distributions, notably by Cantero et al. using the CGMV method [10, 15]. Meanwhile, for a QW of this kind, the overall weak limit law for the probability distribution has remained relatively unexplored. Our treatment addresses this omission and emulates the approach employed by Chisaki et al. in [16]. This paper unfolds as follows. In the second section, we introduce the elements essential to understanding our adopted model of quantum walks [email protected] [email protected] Department of Mathematics, Bowie State University Bowie, MD 20715 USA on the half line and we define and develop the generating functions of the probability amplitudes associated therewith. In third section, we formulate and prove a weak limit formula for the class of QW’s under consideration. Much of the derivations and justifications of technical details are relegated to the subsequent sections. 2 QWs on the half line In this paper, we adopt the model of unitary quantum walks on the half-line as defined by Cantero et al. [14]. In this model, the unitary shift operator S is given by ∞ ∞ (cid:88) (cid:88) S = |x+1(cid:105)(cid:104)x|⊗| ↑(cid:105)(cid:104)↑ |+ |x−1(cid:105)(cid:104)x⊗| ↓(cid:105)(cid:104)↓ |+|0(cid:105)(cid:104)0|⊗| ↑(cid:105)(cid:104)↓ |. (1) x=0 x=1 According to this formula, each temporal iteration of S acts as follows: whenlocatedatanysite0,1,2,3,..., anupwardspinmigratesonesteptothe right. When located at any strictly positive position 1,2,3,..., a downward spin migrates one step to the left. When located at the special site 0, a downward spin reverses orientation and remains at site 0, so that, in the next iteration, it migrates to site 1. Inthismodel, theevolutionofquantumstatesisgovernedbytwounitary so-called “coins”, represented by the matrices: (cid:20) (cid:21) (cid:20) (cid:21) a b a b U = 0 0 , U = , (2) 0 c d c d 0 0 in terms of which, the one-step transition rules can be framed by a master operator U, as follows. When x (cid:54)= 0, we have U|x ↓(cid:105) = a|x−1 ↓(cid:105)+c|x+1 ↑(cid:105), U|x ↑(cid:105) = b|x−1 ↓(cid:105)+d|x+1 ↑(cid:105), (3) while, in the special case when x = 0, we have U|0 ↓(cid:105) = a |0 ↑(cid:105)+c |1 ↑(cid:105), U|0 ↑(cid:105) = b |0 ↑(cid:105)+d |1 ↑(cid:105). (4) 0 0 0 0 For the sake of clarity, it is appropriate to distinguish between two kinds of quantum walks on the half line. If the quantum walk is governed every- where by a single constant coin U (in particular U = U in Eq.(2)) let it be 0 referred to as a homogeneous quantum walk. Otherwise, let the quantum walk be called inhomogeneous. For instance, the Hadamard quantum walk on the half line is the homogeneous quantum walk governed everywhere by the constant coin U = H, where H is Hadamard matrix: √ (cid:20) (cid:21) 2 1 1 H = . (5) 2 1 −1 As is customary in the literature, the probability amplitude of finding thewalkeratpositionxattimetisdenotedbyψ(x,t) = (ψ (x,t),ψ (x,t))T, ↓ ↑ while its generating function is denoted by Ψ(x,z) = (cid:80)∞ ψ(x,t)zt. t=0 Referring to Eq. (2), let the matrices S , Q , P and Q be defined as 0 0 follows: (cid:20) (cid:21) (cid:20) (cid:21) (cid:20) (cid:21) (cid:20) (cid:21) 0 0 0 0 a b 0 0 S = , Q = , P = , Q = . (6) 0 a b 0 c d 0 0 c d 0 0 0 0 Then the one-step transition rules given by Eqs. (3) and (4) can be reformulated as follows in terms of the probability amplitudes: ψ(0,t+1) = Pψ(1,t)+S ψ(0,t) 0 ψ(1,t+1) = Pψ(2,t)+Q ψ(0,t) 0 ψ(x,t+1) = Pψ(x+1,t)+Qψ(x−1,t) forx ≥ 2 (7) Enlightened by the techniques employed by Konno and Oka et. al. in [11, 17], it is possible, in the present context, to derive an explicit closed formula for the generating function Ψ(x,z). Lemma 1 Suppose the quantum walk (as defined above) is launched fromsite0withinitialcoinstate(α,β)T (i.e.,ψ(0,0) = (α,β)T andψ(x,0) = 0 for x ≥ 1). Then the generating function Ψ(x,z) is given by (b+adBr(0,z))(α∆ z +αc +βd )z2 0 0 0 Ψ (0,z) = α+ , ↓ 1−b z −bc z2 −b∆ z3 −ad∆ z3Br(0,z)−ac dz2Br(0,z) 0 0 0 0 0 αa z +βb z +βb∆ z3 +βad∆ z3Br(0,z) 0 0 0 0 Ψ (0,z) = β + , ↑ 1−b z −bc z2 −b∆ z3 −ad∆ z3Br(0,z)−ac dz2Br(0,z) 0 0 0 0 0 (dλ /a)x−1dzBr(0,z)(α∆ z +αc +βd ) + 0 0 0 Ψ (x,z) = forx ≥ 1, ↓ 1−b z −bc z2 −b∆ z3 −ad∆ z3Br(0,z)−ac dz2Br(0,z) 0 0 0 0 0 (dλ /a)x−1z(α∆ z +αc +βd ) + 0 0 0 Ψ (x,z) = forx ≥ 1, ↑ 1−b z −bc z2 −b∆ z3 −ad∆ z3Br(0,z)−ac dz2Br(0,z) 0 0 0 0 0 where (cid:112) 1+∆z2 − ∆2z4 +2∆(1−2|a|2)z2 +1 λ −az λ = ,Br(0,z) = + , (8) + 2dz acz ∆ = a d −b c , and∆ = ad−bc (9) 0 0 0 0 0 The details involved in deriving the above formulas for Ψ(x,z) are de- ferred to section 4. Let X denote the position of the walker at time t. According to stan- t dard quantum mechanical conventions, the probability distribution of X is t identified with |ψ(x,t)|2. In the sequel, equipped with the explicit expres- sions for Ψ(x,z), as given by Lemma 1, our main goal is to evaluate, for a QW on the half-line, the terminal behavior, in the weak limit sense, of the scaled quantity X /t as t → ∞. t 3 Weak limit for QW’s on the half line To enable feasibility within reasonable effort, and without excessive loss of generality, let us proceed on the assumption that the determinants of the unitary coin operators in Eq. (2) are equal. That is: ∆ = ∆. Following 0 the approach in [16], the following theorem is obtained: Theorem 1. Suppose the QW on the half line (as defined above) is launched from site 0 with the initial coin state α| ↓(cid:105)+β| ↑(cid:105), then X /t ⇒ Y, (10) t where Y is the random variable with probability density |c|2y2I (y) (0,|a|) f(y) = ρδ(y)+h(y) (11) (cid:112) π(1−y2) |a|−y2 and where the symbol ⇒ denotes convergence in distribution. The symbols in the expression for f(y) are defined as follows: (h −h )(h +h −h )+h (h +h ) 6 8 1 2 3 7 4 5 h(y) = (h +h −h )2 −(h +h )2 1 2 3 4 5 (h +h )(−h +h +h )+h (h −h ) 6 8 1 2 3 7 4 5 + , (12) (−h +h +h )2 −(h −h )2 1 2 3 4 5 where h = 2|c|2(cid:61)(c¯∆1 −c¯∆1), h = (1+|c |2 −2(cid:60)(c¯c ))|c|(cid:112)1−y2, 1 2 0 2 2 0 0 h = (cid:61)(c¯∆1 +c¯c2∆−1)(1−y2), h = 2|c|(cid:60)(c¯∆1 −c¯∆1)(cid:112)|a|2 −y2, 3 2 0 2 4 2 0 2 (cid:112) (cid:112) (cid:112) h = 2(cid:61)(c¯c ) 1−y2 |a|2 −y2, h = (|α|2 +|αc +βd |2) 1−y2 5 0 6 0 0 1 (cid:112) 1 h = 2(cid:60)(α∆ αc +βd ) |a|2 −y2, h = 2|c|(cid:61)(α∆ αc +βd ), (13) 7 2 0 0 8 2 0 0 and where (cid:90) |a| |c|2y2I (y) (0,|a|) ρ = 1− h(y) dy. (14) (cid:112) π(1−y2) |a|−y2 0 The proof of this theorem can be found in Section 5. In [11, 12], Konno offers weak limit theorems for homogeneous quantum walks on the full line. More recently, these results have been extended to topological settings similar [13], but not quite equivalent, to the half-line setting of Theorem 1. In our setting, when restricted to the special case of a homogeneous quantum walk on the half line, Theorem 1 implies the following corollary: Corollary 1. Let the homogeneous QW be launched from site 0 with the initial coin state α| ↓(cid:105)+β| ↑(cid:105). Then X /t ⇒ Y, (15) t where Y is the random variable with probability density 2|c|3[|α|2 +|αc+βd|2 −2(cid:61)(c¯∆1)(cid:61)(α∆1αc+βd)]y2 2 2 f(y) = ρδ(y)+ I (y) π|a|2[|c|2 −((cid:61)(c¯∆1))2(1−y2)](1−y2)(cid:112)|a|2 −y2 (0,|a|) 2 In all cases studied by Konno in [11, 12], involving a two-state homoge- neous QW on the full line, the phenomenon of localization never occurs as a feature of the weak limit. However, for a typical two-state homogeneous QW on the half-line, the limiting behavior is quite different. Frequently, but not always, localization is to be expected. However, this discovery is not without precedent. Notably, Cantero et al. [10, 15] have devised special techniques known as the CGMV method for treating questions about mass point and the return probabilities of QWs on the half line. Also they (see page 1159 in [10]) have offered an example of a homogeneous QW on the half line for which localization occurs. Here we offer a different example. Example 1. Suppose the QW, everywhere governed by the coin oper- ator √ (cid:20) (cid:21) 2 1 eiπ/4 U = , (16) 2 e−iπ/4 −1 √ √ is launched from site 0 with initial coin state 2| ↓(cid:105) + i 2| ↑(cid:105). Then, by 2 2 Corollary 1, we have √ (6+2 2)y2I √ (y) (0, 2/2 f(y) = ρδ(y)+ , (17) (cid:112) π(1−y4) 1−2y2 √ √ √ where ρ = ( 3− 2)(3− 3). 6 The coefficient ρ (see Eq. (14)) acts as the weight of the Dirac func- tion δ(y) in the density function f(y) and thereby governs the propensity for localization near the origin. In fact it is not difficult to see that ρ may be computed as the sum of the limiting probabilities at all nodes, namely ρ = (cid:80)∞ lim |ψ(x,t)|2. Accordingly, for the purposes of numerical sim- x=0 t→∞ ulation, it suffices to consider only probability values not very far removed from the initial position and time, say x ≤ 4 and t = 400, as in Table 1: Table 1: Probability Distribution of X for x≤4 and t=400 t x 0 1 2 3 4 |ψ(x,t)|2 .0492 .0132 .0035 .0010 .0002 In terms of the tabulated values, we get ρ (cid:117) (cid:80)4 |ψ(x,t)|2 (cid:117) 0.0671 (cid:117) √ √ √ x=0 ( 3− 2)(3− 3). The limiting behavior of this specific QW is displayed in Fig- 6 ure 1. Note the localization spike near the origin. However,asshownbyournextexample,localizationisnotalwayspresent for a homogeneous unitary QW on the half line. Let the Hadamard matrix 0.09 0.08 0.07 0.06 Probability 00..0045 0.03 0.02 0.01 00 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Position (Normalized) Figure 1: Probability distribution at time t = 400 of a homogeneous QW on the half-line with unitary coin operator U as defined by Eq. (16) and initial coin state √ √ 2|↓(cid:105)+i 2|↑(cid:105). 2 2 H (see Eq.(5)) serve as the constant coin operator for the homogeneous QW. By Corollary 1, we deduce: Corollary 2. Suppose the Hadamard QW is launched from site 0 with the initial coin state α| ↓(cid:105)+β| ↑(cid:105), then X /t ⇒ Y (18) t where Y is a random variable with probability density 2I √ (y) (0, 2/2) f(y) = . (cid:112) π(1−y2) 1−2y2 For this QW, the probability distribution is depicted in Figure 2. 0.035 0.03 0.025 Probability0.00.1052 0.01 0.005 00 0.1 0.2 0.3 0.4 Position (0N.o5rmalized) 0.6 0.7 0.8 0.9 1 Figure2: Probabilitydistributionattimet=400ofahomogeneousQWonthehalf-line √ √ withHadamardcoinoperatorH asdefinedbyEq.(5)andinitialcoinstate 2|↓(cid:105)+i 2|↑(cid:105). 2 2 Notably, according to Corollary 2, at least when the QW on the half-line is governed by the Hadamard coin operator, the weak limit is seen to be independent of the initial coin state. Last, but not least, let us consider an example of an inhomogeneous quantum walk on the half line. Example 2. Let the QW on the half line be launched with initial coin state | ↑(cid:105) and coin operators U and U defined as follows: 0 √ √ (cid:20) (cid:21) (cid:20) (cid:21) 2 1 eiπ/4 2 1 1 U = , U = H = . (19) 0 2 e−iπ/4 −1 2 1 −1 By Theorem 1, the density for this QW is given by (cid:18) k y2 +k y4 +k y6 (cid:19) I √ (y) 1 2 3 (0, 2/2) f(y) = ρ δ(y)+ , (20) 0 m +m y2 +m y4 +m y6 π(cid:112)1−2y2 1 2 3 4 where the numerical coefficients are √ √ √ ρ = 0.677887, k = 54−38 2, k = 46 2−62, k = 16 2−16 0 √ 1 √ 2 √ 3 √ m = 17−12 2, m = 64 2−90, m = 121−84 2, m = (4−4 2)2. 1 2 3 4 The relatively large value of ρ ≈ 0.678 indicates a strong tendency for localization near the origin. In Table 2 and Figure 3 we display numerical data for this QW at time t = 400. Table 2: Probability Distribution of X for x≤7 and t=400 t x 0 1 2 3 4 5 6 7 |ψ(x,t)|2 .4428 .1648 .0299 .0275 .0046 .0054 .0010 .0012 Using the tabulated data, we verify that ρ (cid:117) (cid:80)7 |ψ(x,t)|2 (cid:117) 0.6771. 0 x=0 0.45 0.4 0.35 0.3 Probability 0.02.52 0.15 0.1 0.05 00 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 11 Position (Normalized) Figure 3: Probability distribution at time t = 400 of a non-homogeneous QW on the half-line with coin operators U and U as defined by Eq. (19) and initial coin state |↑(cid:105). 0 Arguably, in the literature, the publication most closely related to our present treatment of weak limits of QWs on the half-line is the investigation by Chisaki et al. [18] of a QW on a graph consisting of joined half lines. In that work, a similar weak limit is obtained. Other relevant publications include [19, 20, 21, 22, 23, 24, 25, 26]. Recently, Konno et al. [13] have proposed a universal formula charac- terizing weak limit measures of quantum walks on the full line. Accord- ing to this formula, any QW on the line may be characterized as follows: there exists a rational polynomial w(y) and real numbers C ∈ [0,1) and r ∈ (0,1) such that the weak limit µ(dy) = Cδ (y)+w(y)f (y;r)dy, where 0 K √ f (y;r) = 1−√r2 I (y) with C = 1 − (cid:82)∞ w(y)f (y;r)dy. We K π(1−y2) r2−y2 (−r,r) −∞ K remark that our QW model on the half line also conforms to this character- ization, with some adjustments. In particular, the indicator function I (−r,r) over the symmetric interval (−r,r)would have to be replaced by I , where (0,r) r = |a|. 4 Proof of Lemma 1 To obtain the desired generating functions, we begin by introducing some convenient notations. Let Ξ(x,t) denote the transition amplitude of the given QW, defined as the sum of the contributions from all paths starting at the site 0 and ending at the site x after t steps. For the specific model of a QW with a breakdown at the site 0, as in [17], let Ξb(x,t) denote Ξb(0 → x,t) as in [17]. To denote the generating functions Br(0 → x,z), Bq(0 → x,z) and Br(0 → x,z), as defined in [17], the abbreviated symbols Br(0,z), Bq(x,z) and Br(x,z) respectively are introduced. In addition to the special matrices S , Q , P and Q defined in Eq. (6), 0 0 let (cid:20) (cid:21) (cid:20) (cid:21) (cid:20) (cid:21) (cid:20) (cid:21) a b c d 0 0 c d P = 0 0 ,R = 0 0 ,S = ,R = (21) 0 0 0 0 0 0 a b 0 0 By the PQRS method [11], the transition amplitudes can be expressed as unique linear combinations of the matrices P ,Q ,R and S (or P,Q,R 0 0 0 0 and S): Ξ(x,t) = up0(x,t)P +uq0(x,t)Q +ur0(x,t)R +us0(x,t)S . (22) 0 0 0 0 The expressions in Eq. (22) can be represented as coefficients of the following four generating functions in z: ∞ ∞ (cid:88) (cid:88) Up0(x,z) = up0(x,t)zt, Uq0(x,z) = uq0(x,t)zt (23) t=0 t=0 ∞ ∞ (cid:88) (cid:88) Ur0(x,z) = ur0(x,t)zt, Us0(x,z) = us0(x,t)zt. (24) t=0 t=0 Now by Eq. (7), the transition amplitudes at x = 1 are given by: Ξ(1,1) = Q 0 Ξ(1,2) = Q S = d S 0 0 0 0 (cid:88) Ξ(1,t) = Ξb(0,t−1−l)Q Ξ(0,l) 0 l + Ξ(0,t−1)Q +Q Ξ(0,t−1)fort ≥ 3 (25) 0 0 in terms of which, we obtain the following formulas for the generating functions at x = 1. Up0(1,z) = [c Up0(0,z)+d Us0(0,z)]dzBr(0,z), 0 0 Uq0(1,z) = z +d zUq0(0,z)+c zUr0(0,z), 0 0 Ur0(1,z) = [1+d Uq0(0,z)+c Ur0(0,z)]dzBr(0,z), 0 0 Us0(1,z) = c zUp0(0,z)+d zUs0(0,z). (26) 0 0 Again by Eq. (7), we have: PΞ(1,t)+S Ξ(0,t) = Ξ(0,t+1) (27) 0 Also, by Eqs. (27) and (26) we obtain the following formulas for the generating functions at x = 0: bd z3 +add z3Br(0,z) Up0(0,z) = 0 0 , 1−b z −bc z2 −b∆ z3 −ad∆ z3Br(0,z)−ac dz2Br(0,z) 0 0 0 0 0 a bz3 +aa dz3Br(0,z) Uq0(0,z) = 0 0 , 1−b z −bc z2 −b∆ z3 −ad∆ z3Br(0,z)−ac dz2Br(0,z) 0 0 0 0 0 (1−b z)[bz2 +adz2Br(0,z)] Ur0(0,z) = 0 , 1−b z −bc z2 −b∆ z3 −ad∆ z3Br(0,z)−ac dz2Br(0,z) 0 0 0 0 0 z −bc z3 −ac dz3Br(0,z) Us0(0,z) = 0 0 (28) 1−b z −bc z2 −b∆ z3 −ad∆ z3Br(0,z)−ac dz2Br(0,z) 0 0 0 0 0 When x ≥ 2, Eq. (7) yields: Ξ(x,x) = Ξb(x−1,x−1)Q 0 (cid:88) Ξ(x,t) = Ξb(x−1,t−1−l)Q Ξ(0,l) 0 0<l≤t−x + Ξb(x−1,t−1)Q fort ≥ x+1, (29) 0 and subsequently: Up0(x,z) = [c Up0(0,z)+d Us0(0,z)]dzBr(x−1,z), 0 0 Uq0(x,z) = [1+d Uq0(0,z)+c Ur0(0,z)]dzBq(x−1,z), 0 0 Ur0(x,z) = [1+d Uq0(0,z)+c Ur0(0,z)]dzBr(x−1,z), 0 0 Us0(x,z) = [c Up0(0,z)+d Us0(0,z)]dzBq(x−1,z). (30) 0 0 Finally, we have: ∞ (cid:88) Ψ (0,z) = (1,0)ψ(0,0)+ (1,0)Ξ(x,t)ψ(0,0)zt ↓ t=1 = α+(αc +βd )Ur0(0,z)+(αa +βb )Up0(0,z) 0 0 0 0 ∞ (cid:88) Ψ (x,z) = (1,0)Ξ(x,t)ψ(0,0)zt ↓ t=1 = (αc +βd )Ur0(x,z)+(αa +βb )Up0(x,z) 0 0 0 0 ∞ (cid:88) Ψ (0,z) = (0,1)ψ(0,0)+ (0,1)Ξ(x,t)ψ(0,0)zt ↑ t=1 = β +(αc +βd )Uq0(0,z)+(αa +βb )Us0(0,z) 0 0 0 0 ∞ (cid:88) Ψ (x,z) = (0,1)Ξ(x,t)ψ(0,0)zt ↑ t=1 = (αc +βd )Uq0(x,z)+(αa +βb )Us0(x,z) (31) 0 0 0 0 Together, Eqs.(26), (28), (30) and (31) suffice to complete the proof. 5 Proof of Theorem 1 Consider the Fourier transform of the generating function Ψ(x,z), which is given by Ψ(cid:98)(k,z) = (cid:80)∞ Ψ(x,z)eixk. Collecting like terms in zt, we get x=0 Ψ(cid:98)(k,z) = (cid:80)∞ Ψ(k,t)zt where Ψ(k,t) = (cid:80)∞ ψ(x,t)eixk. By Lemma 1, t=0 t=0 one has a closed formula for Ψ(cid:98)(k,z), by which it can be shown that Ψ(cid:98)(k,z) has two types of unit poles: the first type of poles are the zeros (assumed to be {ω : j ∈ J}) of 1−b z−bc z2−b∆ z3−ad∆ z3Br(0,z)−ac dz2Br(0,z), j 0 0 0 0 0 which contribute to the part of a mass point represented by the distribution ρδ(y) in the formula for f(y); while the second type of pole, as the zero of 1− dλ eik, determines the absolutely continuous part of the density f(y). a + Let us introduce a∆−1 = |a|eiη with 0 ≤ η < 2π, then this single pole 2 is eiθ1(k) when k ∈ (η − π,η), or eiθ2(k) when k ∈ (η − 2π,η − π). Here θ (k) = arccos(|a|cos(η −k)) and θ (k) = 2π −arccos(|a|cos(η −k)). 1 2 By Cauchy’s integral theorem, (cid:73) 1 Ψ(cid:98)(k,z) Ψ(k,t) = dz (32) 2πi zt+1 {z:|z|=rfor0<r<1} (cid:40) −Res(Ψ(cid:98)(k,z),eiθ1)−(cid:80) Res(Ψ(cid:98)(k,z),ω ), k ∈ (η −π,η), = zt+1 j∈J zt+1 j (33) −Res(Ψ(cid:98)(k,z),eiθ2)−(cid:80) Res(Ψ(cid:98)(k,z),ω ), k ∈ (η −2π,η −π). zt+1 j∈J zt+1 j By the structure of the function Ψ(k,t), one can calculate the character-