Conditional Probability Distributions of Finite Absorbing Quantum Walks
Parker Kuklinski








Anomaly Detection in DevOps Toolchain
    Antonio Capizzi 1, Salvatore Distefano 1, Manuel Mazzara 2 
 Luiz J.P. Araújo 2, Muhammad Ahmad 1,3, Evgeny Bobrov 2 
 
University of Messina, Italy
Innopolis University, Innopolis, Respublika Tatarstan, Russian Federation
Department of Computer Engineering, Khwaja Fareed University of Engineering and Information Technology, Pakistan.

    December 30, 2023
=====================================================================================================================================================================================================================================================================================================================================================





Quantum walks are known to have nontrivial interactions with absorbing boundaries. In particular it has been shown that an absorbing boundary in the one dimensional quantum walk partially reflects information, as observed by absorption probability computations. In this paper, we shift our sights from the local phenomena of absorption probabilities to the global behavior of finite absorbing quantum walks in one dimension. We conduct our analysis by approximating the eigenbasis of the associated absorbing quantum walk operator matrix Q_n where n is the lattice size. The conditional probability distributions of these finite absorbing quantum walks exhibit distinct behavior at various timescales, namely wavelike reflections for times t=O(n), fractional quantum revivals for t=O(n^2), and stability for t=O(n^3). At the end of this paper, we demonstrate the existence of fractional quantum revivals in other sufficiently regular quantum walk systems.




§ INTRODUCTION


The quantum walk is a unitary analogue of the classical random walk. Where classical random walks have been used in algorithms for classical computers <cit.> <cit.> <cit.> <cit.>, quantum walks can be used in algorithms for quantum computers, providing various degrees of speedup over their classical counterparts <cit.> <cit.> <cit.> <cit.> <cit.>. As opposed to the standard deviation of the random walk which grows at O(√(t)), the standard deviation of the quantum walk grows at O(t) and the wave function has highly oscillatory behavior close to the wave fronts. The quantum walk has been studied in a variety of purely mathematical contexts <cit.> <cit.> and has also been physically implemented in a number of settings <cit.> <cit.>. In this paper, we will explore the asymptotic behavior of finite quantum walks with absorbing boundaries.

Quantum walks with absorbing boundaries were first studied in relation to absorption probabilities <cit.> <cit.>. Let p_∞ be the probability that a Hadamard walk particle initialized in |1⟩ |R⟩ is eventually absorbed at |0⟩, and let p_n be the probability that this particle is absorbed at |0⟩ and not by an additional absorbing boundary at |n⟩. Ambainis et. al. <cit.> found that p_∞ =2/π and lim _n→∞p_n=1/√(2). This paradoxical result (i.e. lim _n→∞p_n>p_∞) indicates that absorbing boundaries in the quantum walk setting partially reflect information. A sharper result conjectured by these authors and later proved by Bach and Borisov <cit.> states that p_n+1=1+2p_n/2+2p_n. These results were extended to the three-state Grover walk <cit.>, two-state quantum walks <cit.>, and general discrete quantum mechanical systems <cit.> <cit.>. Other authors have considered hitting times, or the mean expected time that a quantum walk particle is first observed at an absorbing boundary <cit.> <cit.> <cit.>. Absorption probabilities and hitting times, however, are concerned with local behavior at an absorbing boundary as opposed to the global behavior that we wish to study. 

The quantum walk can be defined as a linear combination of translations, so it is natural to view the quantum walk operator on a finite domain as a matrix. In the case of the quantum walk with absorbing boundaries, the quantum walk operator matrix is a composition of a unitary operator with a Hermitian projection operator which projects off of the absorbing boundary locations. The asymptotic behavior of a finite quantum walk is best understood by computing the eigenbasis of the operator matrix. To compute the eigenvalues of a quantum walk matrix, we first calculate its characteristic polynomial p_n(λ ) where n is the size of the domain. These characteristic polynomials satisfy a second order recursion which we exploit to compute the eigenvalues up to polynomial order. Similar techniques are used in the computation of the eigenvectors.

The eigenvalues of Q_n uniformly approach two sectors of the unit circle at O(n^-1) as n increases. At t=O(n^3), the top eigenvalues of Q^t_n begin to dominate the system. More interestingly, the minimum phase difference between the k^th top eigenvalue of Q_n and one of the points ± |a|± i|b| (a,b determined by Q_n) is roughly k^2/n^2α for small k and some constant α. Thus, there exist times t for which the top eigenvalues of Q_n^t approximately align in the complex plane in various patterns. More specifically, there exists a value τ∈ ^+ such that Q_n^τ n^2 becomes a crude approximation of the identity matrix. For sufficiently simple rational multiples z∈ of τ (i.e. z=p/q such that p,q are small), the matrix Q_n^zτ n^2 becomes a weighted sum of approximations of vector reversals and transpositions. As z increases, the granularity of these approximations decreases. For an initial state Ψ _0 describing a delta potential directly between the absorbing boundaries, the situation becomes more visually striking. For m∈ sufficiently small, Q_n^mτ /8Ψ _0 reproduces an approximation of Ψ_0. Furthermore for p,q∈ sufficiently small, Q_n^pτ /8qΨ _0 produces an approximation of q evenly spaced delta potentials in the domain. This behavior is an approximation of fractional quantum revivals which have been observed in several quantum settings. <cit.> <cit.>

The rest of the paper is organized as follows: section 2 is dedicated to defining the finite absorbing quantum walk and its matrix representation. In section 3 we approximate the eigensystem of the one-dimensional absorbing quantum walk operator. In section 4 we use these approximations to describe the approximate fractional quantum revival behavior at t=O(n^2). In section 5 we demonstrate the existence of these quantum revivals in a two dimensional absorbing quantum walk.









§ DEFINITIONS AND METHODS


To begin, we recount the quantum walk on groups as first defined by Acevedo et. al. <cit.>. The following definitions have appeared in previous works by Kuklinski <cit.> <cit.> <cit.>.

Let (G,· ) be a group, let Σ⊂ G where |Σ |=n, and let U∈ U(n) where U(n) is the set of n× n unitary matrices. The quantum walk operator Q:ℓ ^2(G×Σ )→ℓ ^2(G×Σ ) corresponding to the triple (G,Σ ,U) may be written as Q=T(I⊗ U) where for g∈ G and σ∈Σ, T:|g⟩ |σ⟩↦ |g+σ⟩ |σ⟩. We denote this correspondence as Q↔ (G,Σ ,U). 

The pair (G,Σ ) can be thought of as an undirected Cayley graph which admits loops <cit.>.

We must also define an absorption unit for quantum walks. To this end, we formally define the measurement operator. Let b∈ G×Σ be the location of an absorption unit. The measurement operator Π ^b_yes:ℓ ^2(G×Σ )→ℓ ^2(G×Σ ) is a projection onto |b⟩ while Π _no^b is a projection onto the the subspace spanned by elements in (G×Σ )\ b. The probabilistic interpretation of quantum mechanics dictates that if we measure a state ψ∈ℓ ^2(G×Σ ) at b, the resulting state becomes Π _yes^bψ /‖Π _yes^bψ‖ with probability ‖Π _yes^bψ‖ ^2 and Π _no^bψ /‖Π _no^bψ‖ with probability ‖Π _no^bψ‖ ^2. If B⊂ G×Σ, let Π _no^B be the composition of no measurement projections for all b∈ B. In this way, we can define an operator for the absorbing quantum walk.

Let Q↔ (G,Σ ,U) be a quantum walk operator and let B⊂ G×Σ be a collection of absorption units. Then we say that Π _no^BQ is the absorbing quantum walk operator corresponding to the ordered quadruple (G,Σ ,U,B) and we denote this correspondence as Π _no^BQ↔ (G,Σ ,U,B).

We use the no operator in our definition because if we observe the particle somewhere in B, then the experiment is terminated, while if the particle is not observed in B (i.e. we are in the range of Π _no^B) the experiment continues. Note that we speak of the absorption units as being elements of the classical space and not as members of the corresponding orthonormal basis. 

In this paper, we are interested in the computing the probability distribution of an absorbing quantum walk Π _no^BQ↔ (G,Σ ,U,B) on G×Σ conditioned on the particle not being absorbed by B. If ψ∈ℓ ^2(G×Σ ) is an initial condition, then we are interested in calculating the following function P_t:G×Σ→ [0,1]:

    P_t(x)=|⟨ x|(Π _no^BQ)^t|ψ⟩ |^2/‖ (Π ^B_noQ)^tψ‖ ^2 .

However, for the absorbing quantum walk it is more natural to perform analysis on the probability amplitude space before converting to the probability space, bypassing the need for renormalization at every time t. If G is finite, we can represent the operator Π _no^BQ↔ (G,Σ ,U,B) as a |G|· |Σ |× |G|· |Σ | matrix.

It will often occur that we need to take large powers of 2× 2 matrices. Using an eigenvalue expansion, we derive:

Let M=[ a b; c d ], λ _± =1/2[ a+d±√((a+d)^2-4(ad-bc))], and F_n=λ _+^n-λ _-^n. Then

    M^n=1/F_1[ F_n+1-dF_n       bF_n;       cF_n F_n+1-aF_n ]

and F_n+2-(a+d)F_n+1+(ad-bc)F_n=0.




















§ EIGENSYSTEM OF THE ONE-DIMENSIONAL FINITE ABSORBING QUANTUM WALK


We now compute the eigensystem of the one-dimensional two-state absorbing quantum walk. The corresponding quantum walk operator can be written as Q_n=Π _no^1Π _no^nQ↔ ( ,C_1,U,{ 1,n} ), which we represent as a 2n× 2n unitary matrix acting as

    Q_nΨ =[   0 U_-   0       0; U_+   0 U_-        ;   0 U_+   0   ⋱    ;   ⋮       ⋱   ⋱ U_-;   0         U_+   0 ][ ψ _1;    ⋮;    ⋮;    ⋮; ψ _n ]

where C_1={ -1,1}, U=U_++U_-, U_+=[ a b; 0 0 ], U_-=[   0   0; -b̅  a̅ ], |a|^2+|b|^2=1, and ψ _k=[ψ _R(k),ψ _L(k)]'. To compute the eigenvalues of Q_n we first calculate the characteristic polynomial.

Let p_n(λ )=(λ I-Q_n). These characteristic polynomials satisfy the following recursion:

    p_n+1(λ )=(λ ^2+1)p_n(λ )-|a|^2λ ^2p_n-1(λ )

Here, p_0(λ )=1 and p_1(λ )=λ ^2.

Proof: We conduct a recursive cofactor expansion on the matrix A_n=λ I-Q_n. Let [M]_ij be the ij-minor of M, or the matrix resulting from the deletion of the i^th row and j^th column. Let B_n=[A_n]_11, C_n=[B_n+1]_21, and D_n=[C_n]_12. Letting A_n'=A_n and likewise for the other matrices, we find the following recursions:

    A_n'=λ B_n',B_n'=λ A_n-1'+bC_n-1',C_n'=b̅B_n'+a̅D_n'D_n'=aA_n-1'

We arrive at the result by rewriting these recursions strictly in terms of A'. 

While in the case of a Chebyshev recursion we are able to use a trigonometric substitution to easily facilitate locating the roots of the polynomial, this procedure will not work here due to the initial conditions <cit.> <cit.> <cit.>. We instead must reference a set with no elementary analytic representation to describe the eigenvalues.

Let Θ _n^±={θ∈ :sin ^2nθ=-y^2sin ^2θ,0<Re θ <π ,±Im θ >0} with y=|a|/|b|. Then the set Λ _n of eigenvalues of Q_n may be written as Λ _n ={ 0}∪Λ _n^+∪Λ _n^- where

    Λ _n^±={ |a|cosθ± i√(1-|a|^2cos^2θ):θ∈Θ _n^±} .

The eigenvalue λ =0 has multiplicity 2.

Proof: Using Lemma 2.1, we can derive a closed form for the characteristic polynomial:

    p_n(λ )=λ ^2/F_1(λ )[ F_n(λ )-|a|^2F_n-1(λ )] .

Here, F_n(λ )=ω _+(λ )^n-ω _-(λ )^n and ω _± (λ )=1/2[λ ^2+1±√((λ ^2+1)^2-4|a|^2λ ^2)]. The factor of λ ^2 accounts for the eigenvalue at λ =0 of multiplicity 2. Using the substitution λ _± (θ )=|a|cosθ± i√(1-|a|^2cos^2θ), we have F_n(λ _± (θ ))=± 2i(|a|λ _± (θ ))^nsin nθ. Substituting this into the nontrivial factor and squaring gives us the equation:

    sin ^2nθ =-y^2sin^2θ

Since we have squared the equation, we have doubled the number of solutions, half of which do not satisfy the original equation. We can check that only values of θ∈Θ _n^± satisfy F_n(λ _± (θ ))-|a|^2F_n-1(λ _± (θ ))=0. 

We provide additional results to better visualize the location of the eigenvalues, the first of which gives a uniform bound on Λ _n.

Let S_n be the set defined as follows:

    S_n^± = { 0}∪{λ∈ :r(n)<λ <1,-ϕ <arg (±λ )<ϕ}

where 

    r(n)^2    = 1/2(c(n)-1)[ (4|a|^2-3)-(4|a|^2-1)c. 
       . +√([(2|a|+1)^2c-(4|a|^2+4|a|-1)][(2|a|-1)^2c-(4|a|^2-4|a|-1)])] ,

c(n)=(1+|a|/1-|a|)^1/n-1, and e^iϕ=|a|+i|b|. Then Λ _n⊂ (S_n^+∪ S_n^-).

Proof: Following the argument of Proposition 2.2 in Kuklinski <cit.>, suppose v is an eigenvector of PU with eigenvalue |λ |=1 where U is unitary and P is a projection. Then v must also be an eigenvalue of U. From Kuklinski <cit.>, the eigenvectors of the corresponding quantum walk operator with periodic boundary conditions satisfy ‖ Pv‖ <‖ v‖ where P is the projection associated with the absorbing boundaries at |1⟩ and |n⟩ and ‖·‖ is the ℓ ^2 norm. Therefore, all eigenvalues of the absorbing quantum walk operator must satisfy |λ |<1.

Suppose p_n(λ _0)=0 and λ _0 0. By expanding F_n in terms of ω _± in equation (5), we have:

    0=|ω _-(λ _0)-|a|^2/ω _+(λ _0)-|a|^2| -|ω _+(λ _0)/ω _-(λ _0)| ^n-1 =|f(λ _0)|-|g(λ _0)|^n-1.

If we can find a set S⊂ such that max _λ∈ S|f(λ )|≤min _λ∈ S|g(λ )|^n-1, then λ _0∉ S. Since f(λ ) is analytic on the unit disk, it obtains its maximum absolute value on the unit circle <cit.>, and this value is obtained at λ =± i such that |f(λ )|≤1+|a|/1-|a|. We also find that for fixed |λ |, the function g(λ )=ω _+(λ )/ω _-(λ ) achieves its minimum absolute value at ± i|λ | such that min _|λ |≤ R|g(λ )|= -g(iR). The formula for r(n) follows by solving (-g(iR))^n-1=(1+|a|/1-|a|) for R.

Through direct computation, we can prove that |f(λ )|<1 and |g(λ )|>1 on the sets A_± ={λ∈ :-ϕ <arg (±λ )<ϕ}, thus completing the proof. 

By the proposition, the eigenvalues of the absorbing quantum walk operator uniformly limit to the unit circle as n increases. Using the identity lim _n→∞n(x^1/n-1)=logx, we can show that the following approximation on our bound holds:

    r(n)=1-|a|^2/nlog1+|a|/1-|a|+O(n^-2)

Furthermore, the eigenvalues are restricted to two sectors of the unit disk symmetric about the real axis; as |a| increases these sectors become larger. These features of the eigenvalues can be observed in Figure 1.

We now make asymptotic approximations on the eigenvalues of Q_n. First we write an asymptotic description of elements of Θ _n, which may be verified via direct computation.

Consider the set Θ _n^± from Theorem 4.1 with elements θ _k,n^±∈Θ _n^± for k∈{ 1,...,n-1}. For fixed k, let x=π k and y=|a|/|b| such that:

    θ ^± _k,n=x/n±ixy/n^2-xy^2/n^3∓ixy/n^4( iy^2+x^2/6+x^2y^2/6) +O(n^-5).

For α =k/n fixed, we have:

    θ _α n,n^±=πα±i/nsinh ^-1(ysinπα)+O(n^-2).


Proof: Recall that we are solving the equation sin^2 nθ =-y^2sin ^2θ, where the roots of positive imaginary real part belong to Θ _n^+ and the roots of negative imaginary real part belong to Θ _N^-. Otherwise, we are solving two equations sinnθ=± iysinθ (here, ± is independent of Θ _n^±) and separating solutions into the sets Θ _n^± afterwards. By using the representation θ =θ _1/n+O(n^-1), we find that sinθ _1+O(n^-1)=O(n^-1), and therefore θ _1=π k for some k∈. By further considering an N^th order approximation of θ =∑ _j=1^Nθ _jn^-j+O(n^-(N+1)) and using an angle sum identity, we have

    (-1)^ksin(∑ _j=1^N-1θ _j+1/n^j) +O(n^-N)=± iysin(∑ _j=1^N-1θ _j/n^j) +O(n^-N)

Each choice of k corresponds to two root approximations dictated by the ± sign on the right hand side. If we eliminate the factor of (-1)^k on the left side, then the two root approximations indexed by the ± sign correspond to roots with positive and negative imaginary part respectively, and thus are in direct correspondence with the sets Θ _n^±. By choosing N=4 and using a Taylor expansion of sinθ, we can write:

    θ _2/n+θ _3/n^2+θ _4/n^3-1/6(θ _2/n) ^3+O(n^-4)=± iy(θ _1/n+θ _2/n^2+θ _3/n^3-1/6(θ _1/n) ^3) +O(n^-4)

By equating like factors of n^-j, we have the following system of three equations:

    θ _2=± iyθ _1,θ _3=± iyθ _2,θ _4-θ _2^3/6=± iy(θ _3-θ _1^3/6)

Solving this system gives the first result. If at the outset we instead fix α =k/n, we instead have the expansion θ =πα +θ _1/n+O(n^-2), thus giving the equation

    sin(θ _1/n)=± iysinπα

Solving this for θ _1 gives us the second result.


For the remainder of the paper we let y=|a|/|b|. This lemma allows us to index our approximations of the nonzero eigenvalues of Q_n as λ _k,n^± =λ _± (θ ^± _k,n). It should be noted that θ =π +θ _k,n^± is also a solution to sin nθ =± iysinθ. These solutions, when passed through the function λ _± (θ ), represent eigenvalues which converge to -e^± iϕ. Since the characteristic polynomial p_n(λ ) in equation (3) is an even function, we will omit mention of these solutions without loss of generality. When presenting asymptotic characterizations of these eigenvalues, we distinguish between the convergence of the k^th eigenvalue to ± e^± iϕ (as given by λ _k,n)  and the uniform convergence of the collection of eigenvalues to arcs of the unit circle as described by Proposition 3.2 (these eigenvalues represented as λ _α n,n). We summarize this in the following proposition:

For fixed k, we write λ _k,n^±∈Λ _n from Theorem 4.1 as follows:

    λ _k,n^± =e^± iϕ( 1∓ix^2y/2n^2 -x^2y^2/n^3-x^2y/n^4[±3/2y^2+x^2/24( 3y± i(3y^2+1))]) +O(n^-5).

For |α |<1 with α n∈, we can write

    λ _α n,n^±=e^± if(α )( 1-1/n|a|sinπα/√(1-|a|^2cos^2πα)sinh^-1(|a|/|b|sinπα)) +O(n^-2)

where e^± if(α )=|a|cosπα± i√(1-|a|^2cos^2πα).

Proof: We can formally write θ _k,n^± =θ _±(1/n) where the coefficient of n^-m in equation (8) is represented by θ ^(m)_± (0)/m!. In this way, we can write λ _k,n^± =λ _±(θ _±(1/n)). If we abuse notation and define, for the moment, λ =λ _± (0), θ =θ _± (0), and likewise for higher derivatives, then by the chain rule we have:

    λ _k,n^±   = λ +θ 'λ '/n+θ”λ '+(θ ')^2λ”/2n^2+θ”'λ '+3θ 'θ”λ”+(θ ')^3λ”'/6n^3
       +θ””λ '+(4θ 'θ”'+3(θ”)^2)λ” +6(θ ')^2θ”λ”'+(θ ')^4λ””/24n^4+O(n^-5)

Lemma 3.1 gives us the “derivatives" θ ^(m), while implicit differentiation of the equation λ _± (θ )^2-2|a|λ _± (θ )cosθ +1=0 with respect to θ gives us the derivatives λ ^(m). Since λ (θ ) is an even function, we need only consider the even derivatives:

    λ =e^± iϕ,λ”=± iye^± iϕ,λ ^(4)=-ye^± iϕ[ 3y± i(3y^2+1)]

Making these substitutions gives us the first result. To arrive at the second, we use a Taylor approximation of λ _±(θ ) at θ =πα instead of at θ =0 as in the previous case. Combining equation (12) with the approximations in Lemma 3.1 gives us the second result. 




With the results from Theorem 3.2, we can prove that the absorbing quantum walk reaches a steady state at time t=O(n^3).

Let ϵ >0 be fixed. There exists T=log (1/ϵ )/π ^2y^2(k^2-1)n^3 +O(n^2) such that for all t>T, we have

    (|λ _k,n^± |/|λ _1,n^± |) ^t<ϵ


This proposition shows that the magnitude of the ratio between the largest and k^th largest eigenvalues of Q_n^t becomes arbitrarily small at times  t=O(n^3). This implies that the largest eigenmode becomes dominant at this timescale. Compare this behavior to the classical random walk which reaches a stable distribution at t=O(n^2).

Using similar techniques we can compute entries of the corresponding eigenvectors.

Let v^± _k,n=[r^± _k,n,1,l^± _k,n,1,...,r^± _k,n,n,l^± _k,n,n]' be the eigenvector of Q_n corresponding to eigenvalue λ ^± _k,n. By letting j=nβ for |β |<1 fixed, we can write these eigenvectors as

    [ r_k,n,β n^±; l_k,n,β n^± ]=(a/|a|) ^nβ([       a̅b; ± i|a||b| ]sinπ kβ +π k/n[ a̅b(± iβ y-1);   |a|^2(β -1) ]cosπ kβ+O(n^-2))


Proof: We find that the entries of v^± _k,n satisfy a matrix multiplication recursion:

    [ r^± _k,n,j+1; l^± _k,n,j+1 ] =1/λ ^± _k,n[                      a                      b;                 ab̅/a̅ (λ ^± _k,n)^2+|b|^2/a̅ ][ r^± _k,n,j; l^± _k,n,j ]

Using Lemma 2.1 gives us the expression:

    [ r_k,n,j^±; l_k,n,j^± ]=1/(a̅λ )^jF_1[ F_j-(λ ^2+|b|^2)F_j-1              a̅bF_j-1;              ab̅F_j-1        F_j-|a|^2F_j-1 ][ r_k,n,1^±; l_k,n,1^± ]

Since the nonzero eigenvalues must satisfy r_k,n,1^± =0, we have:

    [ r_k,n,j^±; l_k,n,j^± ]=1/(a̅λ )^jF_1[       a̅bF_j-1; F_j-|a|^2F_j-1 ]

By making the substitutions j=nβ and λ (θ ), and using equations (8) and (10) to make approximations for θ and λ respectively, we arrive at the result. 

On the right side of Figure 1, we see that the top eigenvectors are are approximations of sine waves up to phase, as described by Theorem 3.3. We pause for a moment to consider these results as an analogy to the partical in an infinite well <cit.>. The approximately sinusoidal top eigenvectors of the presently defined absorbing quantum walk operator Q_n are in agreement with eigenfunctions of the particle in an infinite potential well. Moreover, the phase difference between the k^th top eigenvalue of Q_n and one of the points ± |a|± i|b| is proportional to k^2 for n sufficiently large. This same energy spacing is present in the infinite potential well particle and leads to the revival behavior of the following section.




§ FRACTIONAL QUANTUM REVIVALS


Previous studies have illustrated that the quantum walk has wave-like behavior for t=O(n) <cit.>, and in particular that quantum walks appear to partially reflect off absorbing boundaries <cit.> <cit.>. In the previous section, we showed that the absorbing quantum walk reaches a stable state for t=O(n^3). At the intermediate timescale t=O(n^2), the absorbing quantum walk exhibits fractional quantum revivals. <cit.> <cit.>

First, let us consider an approximation of (λ ^± _k,ne^∓ iϕ)^τ n^2 for a specific value of τ:

For τ =4/(π y), the following result holds:

    (λ ^± _k,ne^∓ iϕ)^τ n^2=1+O(n^-1)


Proof: Using Theorem 3.2, we can take a logarithm to find:

    log[ (λ ^± _k,ne^∓ iϕ)^τ n^2]    = (τ n^2)log (λ ^± _k,ne^∓ iϕ) 
       = τ n^2(∓ i(π k)^2y/2n^2+O(n^-3)) 
       = ∓ iτ y(π k)^2/2+O(n^-1)

Letting τ =4/(π y) results in the main component becoming ± 2π i k^2 and the result immediately follows. 

For the remainder of the paper, we let τ =4/(π y). This result shows that the top few eigenvalues of Q _n^τ n^2 are approximately equal to one. However, these approximations are only suitable for fixed k; for t=O(n^2) numerics show us that for ϵ >0 fixed there are O(√(n)) eigenvalues with |(λ _k,n^± )^t|>ϵ. Thus we would like new approximation for the eigenvalues λ _β√(n),n^± where β is fixed. We write an extension of Lemma 3.1:

Consider the set Θ _n^± from Theorem 3.1 with elements θ _k,n∈Θ ^± _n for k∈{ 1,...,n-1}. For β =k/√(n) fixed, we have:

    θ _β√(n),n^± =x/√(n)±ixy/n^3/2±ixy/n^5/2[ ± iy-x^2/6(1+y^2)] +O(n^-7/2)

where x=πβ.

Proof: We follow the argument of Lemma 3.1 and fix β =k/√(n). This allows us to posit an asymptotic expansion θ =∑ _j=1^Nθ _j/n^j-1/2+O(n^-(N+1/2)), giving us an equation:

    sin(θ _2/√(n)+θ _3/n^3/2) +O(n^-5/2)=± iysin(θ _1/√(n)+θ _2/n^3/2) +O(n^-5/2)

The first term becomes θ _1=πβ. By using a Taylor series expansion of sinθ and matching like powers of n^-j, we have:

    θ _2=± iyθ _1,θ _3-θ _2^3/6=± iy(θ _2-θ _1^3/6)

Solving this system gives the result. 

Using Lemma 4.1, we can find the eigenvalues at this new timescale.

For fixed β =k/√(n), we write λ _β√(n),n^±∈Λ _n from Theorem 4.1 as follows:

    λ _k,n^± =e^± iϕ( 1±ix^2y/2n-x^2y/n^2(y+x^2/24[ 3y± i(3y^2+1)])) +O(n^-3)


Proof: We can formally write θ _β√(n),n^± =φ _±(1/√(n)) where the coefficient of n^-(m-1/2) is represented by φ ^(2m-1)(0)/(2m-1)!. This allows us to write λ _β√(n),n^± =λ _±(φ _±(1/√(n))). By using the same chain rule argument but noting that φ ^(2m+1)=0 and λ ^(2m)=0, we have:

    λ _β√(n),n^± =λ +(φ ')^2λ”/2n+4φ 'φ”'λ”+(φ ')^4λ””/24n^2+O(n^-3)

Making the proper substitutions gives us the result. 

With this new representation of the eigenvalues, we can consider a more detailed approximation of the relevant eigenvalues at the timescale t=O(n^2). 

For β =k/√(n) fixed, we have:

    (λ ^± _β√(n),ne^∓ iϕ)^τ n^2+ρ n=e^-x^2y^2τexp[±ix^2y/2(ρ -x^2τ/12(3y^2+1))] +O(n^-1)


Proof: Taking a logarithm of the left hand side of equation (17) and using the approximation from proposition 4.2, we have:

    log[ (λ ^± _β√(n),ne^∓ iϕ)^τ n^2+ρ n]    = (τ n^2+ρ n)log (λ ^± _β√(n),ne^∓ iϕ) 
       = (τ n^2+ρ n)log( 1±ix^2y/2n-x^2y/n^2(y+x^2/24[ 3y± i(3y^2+1)]) +O(n^-3)) 
       = (τ n^2+ρ n)[(±ix^2y/2n-x^2y/n^2(y+x^2/24[ 3y± i(3y^2+1)])) -1/2(±ix^2y/2n) ^2] +O(n^-1) 
       = ±ix^2y/2τ n-x^2y^2τ±ix^2y/2[ρ -x^2τ/12(3y^2+1)] +O(n^-1)

The result follows from noting that ± ix^2yτ n/2 is always an integer. 

This theorem gives us a better perspective on the eigenvalues of Q_n^t for t=O(n^2). The absolute value of equation (17) decreases at O(e^-β ^2) for large β, and the phase is a quartic function of β. More importantly, equation (17) shows that the top O(√(n)) eigenvalues of Q_n are significant for t=O(n^2) and roughly align in the complex plane on the real interval [0,1]. The remaining eigenvalues become negligible at this scale.

One reason we introduce the linear term ρ n to the exponent is to better “align" the eigenvalues in the complex plane. It is an interpretive task to define alignment, however one particularly compelling definition is to consider alignment as an entropy minimization task. Recall that if p:→ is a probability distribution function, its Shannon entropy (not to be confused with Von Neumann entropy of a density matrix) is defined as H[p]=-∫ _-∞^∞ p(x)logp(x)dx. Loosely speaking, entropy is a measure of uncertainty in the outcome of a probabilistic process. For instance, if p(x)=δ _x_0(x), then H[p]=0, otherwise p describes a deterministic quantity and there is no uncertainty in the corresponding outcome. Alternatively, if the domain of p is an interval on the real line, H[p] is maximized when p is the uniform distribution, or all possible outcomes are equally likely. Suppose we begin our absorbing quantum walk with the initial state ψ _0=|n/2⟩ |R⟩. Notice that H[|ψ _0|^2]=0. We claim that at time t=τ n^2+O(n), Q_n^t in some sense approximates the identity matrix; the fitness of this approximation can be estimated by computing the entropy quantity H[|Q_n^tψ _0|^2]. If Q_n^t is a good approximation of the identity matrix, we expect this entropy quantity to be small, and subsequently for the eigenvalues of Q_n^t to “align" in some capacity. This method of using entropy to gauge quantum revivals was explored previously in Romera and de Los Santos <cit.>. We explore this concept visually and computationally in the remainder of the section.





Figure 2 contains two plots of the entropy H[|Q_n^tψ _0|^2/‖ Q_n^tψ _0‖ ^2] over time t. The left plot shows that the entropy of this system is a roughly periodic function with decaying amplitude. Notice that the most prominent minima occur at approximately t=τ n^2/8k where k∈. We deduce that these minima correspond to times at which Q_n^tψ _0 approximates a delta function, as shown in the left side of Figure 4. As k increases, these approximations in some sense lose “higher frequency" components as they eventually approach the steady-state top eigenvector. However, it is not true that Q_n^τ n^2k/8 approximates the identity matrix for all k; in fact this approximation holds only for k divisible by 8. Figure 5 shows this sequence of matrices. Notice that at k=4, Q_n^τ n^2/2 is approximately an anti-diagonal matrix which flips the initial condition. For k=2,6, Q_n^τ n^2k/8 becomes a weighted sum of the identity approximation and the vector flip approximation. The remaining (odd) values of k result in Q_n^τ n^2k/8 becoming a weighted sum of approximations of the identity matrix, the vector flip matrix, a matrix which swaps the top and bottom halves of the vector, and a matrix which flips the top and bottom half of the vector separately.



The right plot of Figure 2 shows significant detail at a smaller scale as well. We observe that entropy minima occur approximately at times t=τ n^2p/8q where p,q∈ are sufficiently small, in a manner similar to Thomae's function <cit.>. Moreover, the right plot of Figure 4 suggests that for gcd(p,q)=1, the distribution |Q_n^tψ _0|^2 has q peaks. This observation can be resolved by noting that letting τ =4p/π y q leads to an extra factor of exp(2π ik^2 p/q) in equations (14) and (17). This causes the eigenvalues to align on a finite set of lines in the complex plane, the number of which is equal to the number of quadratic residues in the ring of integers modulo q. By considering the eigenvectors of Q_n from equation (13) as crude approximations of sin (π kx), the mechanism behind these fractional quantum revivals becomes clear. 



However, from the estimate of (λ _β√(n),n^± e^∓ iϕ)^τ n^2+ρ n in equation (17), we see that the phases of the top O(√(n)) eigenvalues never perfectly align. While letting τ =4/π yp/q and ρ =0 gives a good estimate of the time locations of minimum entropy, we can see from Figure 5 that the actual locations of minimum entropy occur at slightly later times as indicated by the improved resolution from the middle to the bottom row of plots. Notice that the eigenvalues at the time of minimum entropy are contained in a narrower band about the real axis than are the eigenvalues at the approximation t=τ n^2/2. In Figure 6, we see various estimates of ρ which lead to entropy minimization. The left plot appears to confirm that ρ converges to a finite value as n→∞, while the second plot illustrates how ρ changes as a function of |a|. A true estimation of ρ would require an estimate of entropy in the system, and this requires a better estimate of the eigenvectors than has been given. Further still, no easily deducible heuristic gives a usable approximation for ρ as a function of y and τ.



These fractional quantum revivals are not unique to the absorbing quantum walk and have manifested in a variety of other quantum systems; the bottom plot in Figure 4 is a fractal that is referred to as a quantum carpet <cit.> <cit.> <cit.>, and was first observed by Henry Talbot in 1836 in the context of optical science <cit.>. In the case of the particle in an infinite potential well, the spacing of energies arising from the Schr odinger equation precisely scales at k^2, leading to exact revivals. In the absorbing quantum walk operator Q_n this spacing is not exact, particularly at higher energies. However, only the top O(√(n)) eigenstates contribute to the conditional probability distribution at times t=O(n^2), and the spacing among these eigenvalues is such that approximate revivals are obtained, though the fidelity of these revivals worsens over time until the stable t=O(n^3) regime is reached. This argument breaks down for several purely unitary quantum walks where all eigenstates are relevant. Here, the eigenvalues irrationally wind around the unit circle such that approximate revivals occur only after extremely long times scaling with the size of the lattice; approximate revivals of continuous time quantum walks on the cycle have only been observed for very small lattice sizes. <cit.>





§ EXTENSION TO TWO-DIMENSIONAL ABSORBING GROVER WALK


As seen in the previous section, fractional quantum revivals arise because the top eigenvalues of Q_n have regular spacing in phase, and the remaining eigenvalues decay to zero exponentially as t=O(n^2). It should not be surprising that other sufficiently symmetric absorbing quantum walk systems also share this property. For example, consider the two-dimensional absorbing Grover walk operator Q_x,y=Π _no^B_x,yQ↔ ( ^2,C_2,G_4,B_x,y). Here, C_2={ (0,1),(0,-1),(1,0),(-1,0)} represents the cardinal directions in ^2, G_n=2/n 1_n-I_n where 1_n is the n× n matrix filled with ones, and B_x,y={ (a,b):a=1 or a=x,b∈}∪{ (a,b):a∈ ,b=1 or b=y} forms an absorbing “box". The corresponding 4xy× 4xy operator matrix requires tensor methods to decompose and we postpone this analysis to a later study. From <cit.> <cit.>, localized eigenvectors with eigenvalue λ =1 take nonzero values on 2× 2 areas in the interior of B_x,y. Since these eigenvectors are the only eigenvectors of Q_x,y with eigenvalues |λ |=1, from Proposition 2.2 in Kuklinski <cit.> an initial condition ϕ _0 which is orthogonal to each of these eigenvectors will eventually decay in norm to zero under Q_x,y^t. If we let x=y and ϕ _0 be one such orthogonal initial conditions localized to (x/2,x/2), then one of the stable distributions in Figure 7 are eventually achieved. These stable distributions correspond to the non-localized top eigenvectors of Q_x,y.



We document the existence of fractional quantum revivals in the absorbing Grover walk, both for square absorbing boxes and also rectangular absorbing boxes. Figure 8 plots entropy of the systems over time; these graphs depict a similar periodic stratification of entropy minima as the plot in Figure 2, albeit with less regularity. We speculate that these entropy minima occur at times t=τ zn^2 for sufficiently simple z∈. Figure 9 displays three of these distributions of the Q_200,200 absorbing Grover walk at entropy minima; perhaps unsurprisingly the peaks arise in an evenly spaced square grid pattern, although there also appear to be non-negligable diagonal patterns. However for the rectangular Q_300,150 absorbing Grover walk, the minimum entropy distributions displayed in Figure 10 do not lend themselves so easily to a simple geometric description.











§ CONCLUSION


In this paper we have computed eigensystems for one-dimensional finite absorbing quantum walks. The eigenvalues of the corresponding operator Q_n uniformly approach two sectors of the unit circle at O(n^-1), while the eigenvectors are appoximations of sine waves up to phase. As we consider larger powers Q_n^t, we find that the eigenvalues rotate about the origin, and the top O(√(n)) eigenvalues approximately align in the complex plane at regular intervals. This gives rise to fractional quantum revivals described in Section 4. This behavior is found in other sufficiently regular quantum mechanical systems with spacing of eigenvalues proportional to k^2.

Several areas of this paper should be expanded upon in future study. If a more robust approximation of the eigenvectors of Q_n are found, one could then make a more informed approximation of entropy for the purpose of entropy minimization. It may also be possible to compute a characteristic polynomial recursion of Q_x,y, which would then facilitate computation of the stable distributions in Figure 7. Connections to relativistic quantum mechanics could prove fruitful as well; as the quantum walk has been compared to the evolution of a Dirac free particle <cit.> <cit.>, one could potentially expand results on Dirac particles in the presence of absorbing boundaries to gather a more general understanding of fractional quantum revivals in dissipative systems <cit.> <cit.>. Absorbing quantum walks may also find application in scattering theory <cit.>. Perhaps an ideal extension of this research would be to find applications of fractional quantum revivals to quantum algorithms. For quantum algorithms involving iterated measurements or absorption, these quantum revivals could provide insight into the behavior of the rest of the quantum state. Furthermore, an absorbing quantum walk could be used imperfectly clone delta potential quantum states <cit.> or to purposefully “low-pass" a quantum state.



plain



 
