{'fraction_non_alphanumeric': 0.045847643480779576, 'fraction_numerical': 0.013282575412752927, 'mean_word_length': 4.3303925893251, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Grover Walks on a Line with Absorbing Boundaries

In this paper, we study Grover walks on a line with one and two absorbing boundaries. In particular, we present some results for the absorbing probabilities both in a semi-finite and finite line. Analytical expressions for these absorbing probabilities are presented by using the combinatorial approach. These results are perfectly matched with numerical simulations. We show that the behavior of Grover walks on a line with absorbing boundaries is strikingly different from that of classical walks and that of Hadamard walks.


I. INTRODUCTION
Since the seminal work by [1], quantum walks have been the subject of research for the past two decades. They were originally proposed as a quantum generalization of classical random walks [2]. Asymptotic properties such as mixing time, mixing rate and hitting time of quantum walks on a line and on general graphs have been studied extensively [3][4][5][6][7]. Applications of quantum walks for quantum information processing have also been investigated. Especially, quantum walks can solve the element distinctness problem [8,9] and perform the quantum search algorithms [10]. In some applications, quantum walks based algorithms can even gain exponential speedup over all possible classical algorithms [11]. The discovery of their capability for universal quantum computations [12,13] indicates that understanding quantum walks is necessary for better understanding quantum computing itself. For a more comprehensive review, we refer the readers to [14,15] and the references within.
One dimensional three state quantum walks, first considered by Inui et al. [16], are variations of two state quantum walks on a line. In the three state walk, the walker is governed by a coin with three degrees of freedom. In each step, the walker is not only capable of moving left or right, but also able to stay at the same position. Three state quantum walks have interesting differences from two state quantum walks. Most notably, if the walker of a three state quantum walk is initialized at one site, it is trapped with large probability near the origin after walking enough steps [17]. This phenomenon is previously found in quantum walks on square lattices [18] and is called localization. In fact, this model is the simplest model that exhibits localization, a quantum effect entirely absent from the corresponding classical random walk. Three state random walks are essentially regarded as the same process as two state random walks by scaling the time. A thorough understanding of the localization effect on this model becomes particularly relevant given the fact that this phenomenon is commonplace in higher-dimensional systems [15]. Recent researches showed that the localization effect happens with a broad family of coin operators in three state quantum walks [19][20][21].
The presence of absorbing boundaries apparently complicates the analysis of three state quantum walks considerably. In this paper, we focus on the question of determining the absorbing probabilities in Grover walks with one and two boundaries.
First, we consider the case where we have a single absorbing boundary. The walk process is terminated if the walker reaches that boundary. We offer methods to calculate the absorbing probability for an arbitrary boundary. When the boundary is fixed at −1, it is known that in the classical case the walker is absorbed with probability 1 [22], while in Hadamard walks the walker has an absorption probability of 2/π [3]. Intuitively, as some probability amplitudes are trapped near origin due to the localization effect in Grover walks, the absorbing probability of Grover walks is smaller than that of Hadamard walks. However, the Grover walker is absorbed with probability 0.6693 which is larger than 2/π. What's more, when the boundary is moved from −1 to −2, the absorbing probabilities suffer an extreme fast decrease. To explain these strange behaviors, we numerically study the oscillating localization effect in Grover walks with one boundary. We find that the localization is occurred owing to the quantum state oscillating between −1 and 0. If the boundary is at −1, the localization effect disappears and the state is absorbed, resulting in a large absorbing probability. If the boundary is at −2, the localization effect revives and the absorbing probability plummets.
Then, we review the case where there are two boundaries -one is at site −M (M > 0) to the walker's left, and the other is at site N (N > 0) to the walker's right. The walk is terminated if the walker is trapped in either absorbing boundary. Methods are designed to calculate the left and right absorbing probabilities to arbitrary accuracy for arbitrary left and right boundaries. In Hadamard walks, the left absorbing probability approaches 1/ √ 2 [3] when the left boundary is at −1 and the right boundary approaches infinity. It is concluded that adding a second boundary on the right actually increases the probability of reaching the left [3]. In Grover walks with two boundaries, we get the same left absorbing probability 1/ √ 2 under the same setting. The conclusion is still correct in Grover walks as 1/ √ 2 > 0.6693. When the left boundary is at −1, the oscillating localization effect disappears. As position −1 is occupied, the part of quantum state, which would have otherwise localized, now is absorbed. When the left boundary is to the left of −1, the sum of the left and right absorbing probabilities is generally less than 1 due to oscillating localization. When studying the case where the left boundary is at −2, we show that the localization probabilities are exponentially decaying in Grover walks with two boundaries.
The rest of this paper is organized as follows. Section II gives formal definitions of Grover walks with one and two absorbing boundaries, and the absorbing probabilities which we study. Section III and Section IV present the methods and results on Grover walks with one and two boundaries. Finally, we conclude in Section V.

A. Grover walks
The three state quantum walk (3QW) considered here is a kind of generalized two state quantum walk on a line. The Hilbert space of the system is given by the tensor product H = H P ⊗ H C of the position space H P = Span{|m , m ∈ Z} and the coin space H C . In each step, the walker has three choices -it can move to the left, move to the right or just stay at the current position. To each of these options, we assign a vector of the standard basis of the coin space H C , i.e. the coin space is three dimensional The evolution operator realizing a single step of the three state quantum walk is given by U = S · (I P ⊗ C) where S is the position shift operator, I P is the identity operator of the position space H P and C is the coin flip operator. In the three state quantum walk on a line, the position shift operator S has the form of S = +∞ m=−∞ |m − 1 m| ⊗ |L L| + |m m| ⊗ |S S| + |m + 1 m| ⊗ |R R|.
As for the coin operator C, a common choice is the Grover operator G. The Grover operator is originally designed for Grover's search algorithm [23], and now finds its use in quantum walks. The Grover operator is defined as The state of the walker after evolving t steps is given by the successive applications of the evolution operator U on the initial state. Let |ψ(t) be the system state after walking t steps, then where |ψ(0) is the initial state, ψ L (t, m) is the probability amplitude of the walker being at position m with coin state |L after walking t steps. ψ S (t, m) and ψ R (t, m) are defined similarly. We will write |m, L , |m, S and |m, R for short of |m ⊗ |L , |m ⊗ |S and |m ⊗ |R whenever there is no ambiguity. Let P (t, m) be the probability of finding the walker at position m after walking t steps, then In summary, the process of Grover walks on a line can be described as follows.
Step2. For any chosen number of steps t, apply U to the system t times.
Step3. Measure the system state |ψ(t) to get the walker's position probability distribution.

B. Grover walks with one boundary
In this process, we introduce an absorbing boundary into the line, resulting in Grover walks on a semi-infinite line. This can be done by setting a measurement device which corresponds to answering the question "Is the walker at position n?". The measurement is implemented as two projection operators Π n yes = |n n| ⊗ I C , Π n no = I − Π n yes , where I C is the identity operator of the coin space H C and I is the identity operator of the Hilbert space H.
As an example of the measurement, suppose the system is now in state |ψ(t) = 1 , R , and is measured by the projection operator Π 0 yes (corresponding to the question "Is the walker at position 0?"). The answer yes is obtained with probability in which case the system state collapses to |ψ(t) yes = 1 The answer is no with probability 2/5, in which case the system collapses to state |ψ(t) no = 1 Analogous to Grover walks on a line, Grover walks on a line with one boundary can be depicted as follows: Step1. Initialize the system state to |ψ 0 = α|0, L + β|0, S + γ|0, R , where α, β, γ ∈ C and |α| 2 + |β| 2 + |γ| 2 = 1.
Step2. For each step of the evolution 1. Apply U to the system.

Measure the system according to
Step3. If the measurement result is yes (i.e. the walker is at −M ), then terminate the process, otherwise repeat Step2.
We are interested the probability that the measurement of whether the walker is at position −M eventually results in yes, which is called the absorbing probability. Let P −M,0,∞ (α, β, γ) denotes the absorbing probability, where −M , 0, and ∞ represent the left boundary, the walker's initial position and the right boundary respectively, and α, β, γ are the probability amplitudes of the coin components |L , |S , |R . To keep accordance with the two boundaries case in symbols, we assume there is a right boundary which is infinitely far away in the one boundary case. That's why we have a rather confusing ∞ here.

C. Grover walks with two boundaries
The third process is similar to Grover walks with one boundary, except that two boundaries are presented rather than one. Specifically, using the same measurement devices as defined for semi-infinite Grover walks, we describe the following process which is called Grover walks on a line with two boundaries, or the finite Grover walks.
Step2. For each step of the evolution 1. Apply U to the system. 3. Measure the system according to {Π N yes , Π N no } to test whether the walker is or not at N (N > 0). N is the right absorbing boundary.
Step3. If either of the measurement results is yes (i.e. the walker is either at −M or N ), then terminate the process, otherwise repeat Step2.
We are interested in the absorbing probabilities that the walker is eventually absorbed by the left or the right boundary. Let • P −M,0,N (α, β, γ) be the left absorbing probability that the measurement of whether the walker is at position −M eventually results in yes.
• Q −M,0,N (α, β, γ) be the right absorbing probability that the measurement of whether the walker is at position N eventually results in yes.
In the above conventions, −M , 0, and ∞ represent the left boundary, the walker's initial position and the right boundary respectively, and α, β, γ are the probability amplitudes of the coin components |L , |S , |R .

III. ONE BOUNDARY
We begin with three special initial cases: 1) the initial state is |0, L ; 2) the initial state is |0, S ; and 3) the initial state is |0, R . The boundary is fixed at −1 for above three cases. We will define generating functions for these simple cases which are used to determine absorbing probabilities for all boundaries. The methods applied in this section are inspired by [24]. we thank them for offering such elegant methods.

A. Generating functions
We first consider simple cases where the boundary is at −1, and the initial state is |0, L , |0, S and |0, R respectively. We define the following generating functions l(z), s(z) and r(z) for each of above three cases , L is the probability amplitude with which the walker first reaches the boundary −1 after walking t steps when starting with state |0, L . It's easy to see that we encode all the probability amplitudes that lead the walker to −1 into the coefficients of z t in l(z). s(z) and r(z) are similarly defined except that the system is initialized to |0, S and |0, R respectively.
Then by Equations 7-9, we can calculate the absorbing probabilities for these three special cases: The analytical absorbing probabilities are matched with the simulation results, as shown in Figure 1. We can see that the absorbing probabilities converge toward their limiting values very quickly. The fast convergence indicates that the remaining probability amplitudes spread rapidly to the right and never go back.

B. Arbitrary boundary
The reason that the generating functions l(z), s(z) and r(z) are important in analyzing absorbing probability for arbitrary boundary is as follows. Suppose now that the boundary is located at −M for some M ≥ 1 and the walker's initial state is |0, R . Consider a generating function defined similarly to r(z), except for the boundary at position −M rather than 1. Then this generating function is simply r(z)(l(z)) M −1 , which follows from the fact that to reach the boundary −M from original position 0, the walker has to move left M times effectively. For each move after the first, the coin state is always |L . The first move is with coin state |R . The process is depicted in Figure 2. Likewise, the generating functions corresponding to staring in states |0, L and |0, S are simply (l(z)) M and s(z)(l(z)) M −1 . Then from the discussions in the previous section we know how to calculate the absorbing probabilities for these The walker is initialized to state |0, R and the boundary is at −M . In order to reach the boundary, the walker has to move left M times effectively. For each move after the first, the coin state is |L . The first move is with coin state |R .  We can see that the absorbing probability P −M,0,∞ (0, 0, 1) undergoes an extreme fast decay when the boundary is moved from −1 to −2, and then rapidly reaches its limiting value as the boundary becomes large. This rather strange phenomenon is emerged due to the oscillating localization effect in Grover walks. It has been proved that Grover walks on an infinite line will result in localization when the system is initialized to state |0, R . The localization probability is 0.202 at the origin (position 0) [25], and is exponentially decaying with the distance from the origin [21]. However, localization is also shown at position −1 in this special case, which violates the exponentially decaying conclusion stated in [21], and has not been studied to the best of my knowledge. The localization probability at −1 is approximate to 0.202 by simulation, as shown in Figure 4. From Figure 4 we can infer that, the probabilities of finding the walker at position −1 and 0 are sum to constant 0.404, while the two probabilities are oscillating around 0.202. These two probabilities will finally both be 0.202 when the walker evolves large enough steps. By analyzing the numerical data, we also find that the probabilities at the left of −1 decay exponentially with the distance from −1, while the probabilities at the right of 0 decay exponentially with the distance from 0. This is a new two-peak localization phenomenon. We conjecture that it is the oscillating effect that results in the two-peak localization -a fair part of the system state is oscillating between position −1 and 0, and never leave that region. When a boundary is located at −1, the amplitudes that should have been oscillating between −1 and 0 are absorbed by that boundary, resulting in the disappearance of localization. When a boundary is located at −2, some of the amplitudes are oscillating between position −1 and 0, resulting in the amplitudes absorbed by the boundary −2 are much less than in the former case. The two-peak oscillation now revives at −1 and 0. From this point of view, we figure out the reason for the extreme fast decay of P −M,0,∞ (0, 0, 1).
We have only considered the cases where the boundaries were located to the left of the walker so far. The symmetric cases (where the boundaries are to the right of the walker) are easy to analyze as the Grover operator is permutation symmetric. A Grover walk with some initial state (α, β, γ) and a boundary M ≥ 0 is equivalent to a Grover walk with some initial state (γ, β, α) and a boundary −M in the sense that they have the symmetric probability distribution and the same absorbing probability. Let P ∞,0,M (α, β, γ) denotes the absorbing probability where the boundary is

PROPOSITION 2.
In Grover walks with one boundary, the absorbing probability satisfies where M ≥ 0 is a boundary, and (α, β, γ) are amplitudes corresponding to |L , |S , |R coin components.

IV. TWO BOUNDARIES
We study Grover walks with two boundaries in the following way. First, we fix the left boundary at −1, and move the right boundary N relatively to observe how the left absorbing probability changes with N . To simplify the analysis, we consider three simple cases: 1) the initial state is |0, L ; 2) the initial state is |0, S ; and 3) the initial state is |0, R . The left boundary is fixed at −1 for above cases. The left absorbing probabilities P −1,0,N (1, 0, 0), P −1,0,N (0, 1, 0), and P −1,0,N (0, 0, 1) are studied both numerically and analytically. Recall that these notations are defined in Section IV. Then, arbitrary left boundary −M and arbitrary right boundary N are investigated. We make use of the generating functions defined in the former case to express the absorbing probabilities studied in this one. We will show that the sum of the left and right absorbing probabilities is less than 1 for almost arbitrary left and right boundaries −M, N , which is strikingly different from that of Hadamard walks and random walks with boundaries. This is due to the localization effect uniquely in Grover walks. Some of the system state is trapped near the origin and cannot be absorbed by either boundary, resulting in the sum less than 1.

A. Generating functions
Three special initial cases are considered: the initial state is |0, L , |0, S and |0, R respectively, and the left boundary is always fixed at −1. We define three functions l(N, z), s(N, z), r(N, z) for these cases as Some explanations on the left generating function l(N, z): • The initial state is |0, L .
• The left boundary is fixed at −1.
• The right boundary is at N ≥ 1.
, L is the (non-normalized) probability amplitude that the quantum walker first hits the left boundary −1 before hitting the right boundary N after walking t steps.
• We encode all probability amplitudes that will result in the left absorption into the coefficients of z t in l(N, z).
Other two generating functions s(N, z), r(N, z) have the same explanations as l(N, z) except that the latter two have initial states |0, S , |0, R respectively.
Let's define L(N, θ) = l(N, e iθ ), S(N, θ) = s(N, e iθ ) and R(N, θ) = r(N, e iθ ). Based on the reasoning techniques described in Section III A, we can calculate the absorbing probabilities for above three cases by following equations where [z t ]l(N, z) is the coefficient of z t in l(N, z), and similarly for [z t ]s(N, z), [z t ]r(N, z).
In Grover walks with two boundaries, the generating functions defined in Equations 13, 14 and 15 can be solved. For details on the solving procedure, the readers can refer to Appendix B. We only summarize the results here. Let l(0, z) = s(0, z) = r(0, z) = 0, then for any N ≥ 1, these generating functions satisfy the following recurrences Assuming r(N − 1, z) to be constant, we find the solutions to these equations, as stated in Theorem 3.
By combining Equations 16-21, we can calculate the left absorbing probabilities P −1,0,N (1, 0, 0), P −1,0,N (0, 1, 0) and P −1,0,N (0, 0, 1) for arbitrary right boundary N ≥ 0. As an example, we calculate these values for 10 different right boundaries. The results are shown in Figure 5. We can see that the left absorbing probability reaches to its limiting value rapidly when the right boundary is shifting.
We derive a closed recurrence for P −1,0,N (0, 0, 1), as stated in Theorem 4. The theorem perfectly matches with the simulation data. We prove its correctness in Appendix C. Solving the recurrence, we get the left absorbing probability when the right boundary is infinitely far to the right: lim N →∞ P −1,0,N (0, 0, 1) = 1/ √ 2.
Up to now, we have only discussed how to estimate the left absorbing probability P −M,0,N (α, β, γ). How to calculate the right absorbing probability Q −M,0,N (α, β, γ)? As the Grover operator is permutation symmetric, a Grover walk with some initial state (α, β, γ), a left boundary −M and a right boundary N is equivalent to a Grover walk with some initial state (γ, β, α), a left boundary −N and a right boundary M in the sense that they have the symmetric probability distributions and the symmetric left/right absorbing probabilities. The relationship between the left and right absorbing probabilities is stated in Proposition 5.  Table I shows the values of l(−2, N ), r(−2, N ) and s(−2, N ) for different right boundaries N (N varies from 1 to 6). From Table I, we observe that s(−2, N ) is less than 1, which is in sharp contrast to the Hadamard walk case. In Hadamard walks with two boundaries, it is stated that The localization probabilities are exponentially decay in Grover walks, as stated in [16,25]. This phenomenon is also observed in Grover walk with two boundaries. Now let's dig deeper on the data given in Table I. For arbitrary N ≥ 1, we define p(N ) = s(−2, N ) − s(−2, N + 1). Actually, p(N ) is the localization probability at position N when the left boundary is at −2 and the right boundary is at N + 1. As the localization probabilities are rather small, we scale up p(N ) by 10 12 to observe their trends. In order to show that p(N ) is truly exponentially decaying, we also calculate the log values of p(N ). The values of p(N ) and log 2 (p(N )) are calculated in Table I, and visualized in Figure 6. From the inset of Figure 6, we can see that the log values of p(N ) decrease linearly with N , which indicates the exponential decay of localization probabilities in Grover walk with two boundaries.

V. CONCLUSION
We analyze in detail the dynamics of Grover walks on a line with one and two absorbing boundaries in this paper. Both cases illustrate interesting differences between Grover walks and Hadamard walks with boundaries.
In the one boundary case, we begin with three special initial states and define generating functions for these simple cases. These generating functions have closed form solutions. Then, we use the solutions to calculate the absorbing probability for arbitrary boundary. The oscillating localization phenomenon is observed and numerically studied in Grover walks with one boundary. It offers a nice explanation for the extreme fast decrease of the absorbing probabilities when the boundary is moved from −1 to −2.
We study the two boundaries in almost the same way as what we did in the former case. Generating functions are defined for three special initial states. We then derive recurrence solutions to these generating functions. These solutions are used to solve more complicated cases. The absorbing probabilities (both the left and right absorbing probability) for arbitrary left and right boundary can be calculated to arbitrary accuracy by recursively applying these solutions. When the left boundary is at −2, the quantum walk leads to localization. We show that the localization probabilities decay exponentially.
Many questions are still left unsolved. We cannot calculate the absorbing probability when the boundary approaches infinity in the one boundary case. In the two boundaries case, we are unable to analytically calculate the left and right absorbing probabilities with arbitrary coin states. A further detailed study on these questions will appear in our forth-coming paper.