Sensitivity of quantum PageRank
Hirotada Honda








Faculty of Information Networking for Innovation and Design, Toyo University

1-7-11 Akabanedai 115-0053, Japan

E-mail: honda012@toyo.jp
Phone:+81-3-5924-2658



addtoresetequationsection
.equation



 
In this paper, we discuss the sensitivity of quantum PageRank.
By using the finite dimensional perturbation theory, we estimate the change of the quantum PageRank under a small analytical perturbation on the Google matrix. In addition, we will show the way to estimate the lower bound of the convergence radius as well as the error bound of the finite sum in the expansion of the perturbed PageRank.
 



Key words:Quantum walk, PageRank, perturbation theory.



Sensitivity of quantum PageRank
    Hirotada Honda
    ...
===============================








§ INTRODUCTION

Quantum information has recently attracted attention.
Especially, quantum walks have been actively discussed from both the theoretical and practical viewpoints <cit.>. 

A major breakthrough was the quadratic speedup in the search algorithms of quantum walks <cit.>. The paper <cit.> extended the random walk concept on a graph to quantum walks on a directed graph.

Based on the ideas presented in <cit.> and <cit.>, he introduced an unitary operator that works on a Hilbert space whose elements are made of 
pairs of edges and the components of the state transition matrix. Recently, studies on the mixing time of the quantum walk on the graph has also been accelerated <cit.>. 

In parallel with these researches, the ranking process has been actively discussed in classic network studies. A prominent ranking process is Google's PageRank algorithm, which appropriately sorts web pages in order of their importance and impact.  

Quantum walk research on PageRank was pioneered in <cit.>, who proposed a quantum version of the PageRank algorithm. Based on Szegedy's ideas <cit.>, they quantized the behavior of a random walker modeled in the Google matrix and defined the unitary operator. They derived some interesting relations between the quantum and original versions of PageRank. For instance, the eigenvalues and eigenvectors of the unitary operator in the quantum PageRank can be represented by those of a matrix composed of the Google-matrix elements. They also numerically computed some characteristics of quantum PageRank and revealed its similarities to and differences from the classical PageRank.

Previously, we studied the behavior of the classical PageRank subjected to small perturbations.
Because the Perron–Frobenius theorem ensures good characteristics of the principal eigenvalue of the Google matrix, the PageRank could be analytically perturbed by analytically perturbing the Google matrix.

However, the perturbations of the quantum PageRank are less tractable because all the eigenvalues of the unitary operator have unity magnitude.
Therefore, we should consider the behavior of all eigenvalues and their corresponding eigenvectors under a perturbation.
To overcome these difficulties, we will exploit the characteristics of normal operators, the reduction process, and the transformation functions in analytical perturbation theory. 

The remainder of this study is organized as follows. The next section introduces the terms and notations used throughout this study. Section 3 reviews the previous arguments concerning classical and quantum PageRanks. Our main results are presented in Section 4 and are proven in Section 5. The conclusions are presented in Section 6. 



§ TERMS AND NOTATIONS

 In this study, N denotes an arbitrary natural number, and the vectors are labeled as |ψ⟩.
The tensor product of two spaces C^N is denoted as C^N ⊗ C^N, and its elemts are
|ϕ⟩⊗|ψ⟩ or simply |ϕ , ψ⟩. 
The transposed row vector of |ψ⟩ is ⟨ψ|, and the inner product of two column vectors
|ϕ⟩ and |ψ⟩ is denoted as ⟨ϕ | ψ|$⟩.

A general complex number and its conjugate are denoted aszandz^*, respectively (z, z^* ∈C).Re(z)andIm(z)are the real and imaginary parts ofz ∈C, respectively.
The imaginary unit isi=√(-1).

Thep-norm of a general vectoru = (u_1,u_2, …, u_N)^Tis defined as 


    u_p ≡( 
        ∑_j=1^N |x_j|^p
      )^1/p   (p ∈ [1,∞)),

andu_∞≡max_1 ≤j ≤N |u_j|.For a squared matrixM = [m_ij] ∈M_N ×N(whereM_N ×Nis a set ofNtimesNmatrices), we define 


    M_∞ = max_1 ≤ i ≤ N∑_j=1^N |m_ij|, 
         M_1 = max_1 ≤ j ≤ N∑_i=1^N |m_ij|.

We also define the  operator norm
M ≡sup_ x 0 M x/x,
where the norm on the right-hand side is the usual norms of vector spaces:x_p. Additionally, we simply denote the vector norm·_2by ·and apply the corresponding operator norms. 

For a matrixM, we define the set of eigenvalues, resolvent set, trace, and spectral radius asσ(M),P(T),tr(M),
 andspr( M), respectively. That is,spr(  M) = lim_n →∞ M^n^1/n.(See for instance <cit.>).  The multiplicity ofλ∈σ(M)is denoted asm(λ).
Whenm(λ)=1,λis simple.

We also defineR(M)as the range of the maps represented byM.


For a pointx ∈R^Nand a general setS ⊂R^N, we havedist(x,S) ≡min_y ∈S |x-y|, where|x-y|is the usual Euclidean distance 
between two pointsxandyinR^N. 

In an unitary spaceHwith its inner product(·, ·),if an operatorM^*satisfies( M^*x,y )=( x, My )   ∀x,   y ∈H,thenM^*is called as the  adjoint operator ofM.

An operatorMis called  normal if it commutes with its conjugate operator:MM^*=M^*M.

The term  isolation distance of an eigenvalueλ_hof a matrixMmeans the distance betweenλ_hand the other eigenvalues ofM, that is,dist(λ_h,σ(M)).

It is often convenient to setπ_1 = 1for a PageRank vectorπ,but Tikhonov's theorem <cit.> states that norms in a finite-dimensional vector space are equivalent. 
Ther-th derivative of a general functionfwith a single argument is sometimes denoted asD^r f   (r ∈N).




§ BACKGROUND



 §.§ Google matrix and PageRank

The PageRank algorithm was originally proposed in <cit.>. 
Many researchers have subsequently made computational and theoretical contributions to this algorithm. Although thorough sensitivity analyses of the PageRank vector exist in the literature <cit.>, we consider that more general situations will appear in practical situations, which warrant further discussion.

The author's previous paper <cit.> presented a sensitivity analysis of PageRank under small analytic perturbations.
We now briefly define a Google matrix and overview its characteristics.
The Internet is modeled as a directed graphG(V,E), whereVandEare the sets of nodes and edges, respectively. 
The notationN=# Vdescribes the number of nodes in this graph. For later use, the elements ofVare labeled as1,2,…,N.

The row-stochastic matrixWis defined byW = H + a/Ne^T, wherea=(a_j).
We seta_j=1if web pagejis a  dangling node (a node without any outgoing links) anda_j=0otherwise <cit.>. 


 The  hyperlink matrixH =[h_ij]is a weighted adjacency matrix defined byh_ij =1/D_iif there is a link from web pageito web pagej, andh_ij=0otherwise, whereD_iis the number of
outgoing links from nodei.

The Google matrixGis defined by
G = αW + (1-α)/N ev^T,
whereeis a column vector whose elements are all1, andvis a 
non-negative vector satisfyingv_1=1(called the  personalization vector). The constantα∈(0,1), is called the  damping factor. The quantity(1-α)represents the 
probability that an Internet surfer navigates from one web page(i)to another(j).
By definition,Gis completely dense, primitive, and irriducible <cit.>.


The following lemma is the foundation of Google matrix theory. 


The Google matrix G has a simple principal eigenvalue η_1=1. All eigenvalues {η_n}_n of G satisfy
η_1 = 1 > | η_2 |  ≥ |η_3| ≥….
Additionally, there exists a non-negative left-eigenvector π corresponding to the principal eigenvalue η_1=1,
which is known as the PageRank vector.


 §.§ Quantum PageRank

The PageRank vector denotes the probability that a random walker on the Internet stays on each node during the stationary state. Recently, this concept has been replaced by the quantum walk. To our knowledge, quantum walk on a directed graph was introduced in <cit.>.
Based on this idea, the authors of <cit.> studied the quantum PageRank. They started their arguments by introducing vectors of the form: 


    |ψ_j⟩≡|j⟩_1 ⊗∑_k=1^N √(g_jk)|k⟩_2
        (j=1,2,…, N),

whereg_jkis the(j,k)element of the Google matrixG.
Here, the indices| ·⟩_l   (l=1,2)show the start and end nodes of the edges, respectively. It is easily seen that


    ⟨ψ_j | ψ_k|=⟩δ_jk  ∀ j,k,

whereδ_jkis the Kronecker's delta.
Therefore,{ |ψ_j⟩ }_jforms an orthonormal basis in a subspace ofℋ ≡C^N ⊗C^N.
The authors of <cit.> also defined the operators


    B≡∑_j=1^N |ψ_j⟩⟨ψ_j|,   
     U≡ S_w ( 2  B -  I),

whereIis theN-dimensional squared unit matrix, andS_wis the swap operator:


    S_w ≡∑_j,k=1^N |k,j⟩⟨j,k|.

Clearly,Uis an unitary operator onℋ<cit.>. 
Now, let us denote its eigenvalues and corresponding normalized eigenvectors as{ μ}and{ | μ⟩ }, respectively. Note that becauseUis 
unitary,{ |μ⟩ }forms an orthonormal basis inℋ.

Now, let us think of the subspaceH_dspanned by{ |ψ_j ⟩ }_jand{ S_w |ψ_j⟩ }_j<cit.>. We also consider its orthogonal subspaceH_d^⊥, on whichUacts as-S_wwhose eigenvalues 
are just±1.

The eigenvalues ofU(other than those ofS_w) are then expressed in the form
μ= λ±i √(1-λ^2),
where the eigenvaluesλof the positive symmetric matrixT = [ t_ij]lie in[0,1]<cit.>, andt_ij = √(g_ijg_ji) (see also <cit.>).  Hereafter, the number of eigenvalues ofT(excluding multiple values) is denoted ass.
That is,σ(T) = {λ_h}_h=1^s.Now, the subspace ofℋwhich is spanned by the eigenvectors ofUcorresponding toμ= λ±i √(1-λ^2)is denoted asH_ehereafter. 

The quantum PageRank for nodei ∈Vat timem ∈Nis then defined as


    I_q(i,m | ψ(0) ) = 
     |
      ∑_μ∈ H_e,  j ∈ Vμ^2m⟨j,i | μ|⟨%s|%s⟩⟩μ | ψ(0)|^2 
    
       ≡| N_q( i,m |ψ(0)) |^2,

whereψ(0)is the initial state of the walk, which lies in the subspaceH_dspanned by{ |ψ_j ⟩ }_jand{ S_w |ψ_j⟩ }_j<cit.>. In addition, the notationμ∈H_eunder the summation symbol
implies that we take the sum over eigenvalues whose corresponding eigenvectors
belong toH_e. The definition (3.1) implies that we consider the spectrum decomposition 
ofUon the spaceH_e, that is, we project the spaceH_dontoH_e.


The authors of <cit.> used the notation 


    I_q(P_i,m) = ∑_μμ^2m _2 ⟨i | μ|⟨%s|%s⟩⟩μ | ψ(0)^2,

which does not clarify the meaning of the projection. In addition, as the contents are scalar values, we adopt the absolute-value notation here. 





 §.§ Formulation and settings

In this paper, we impose a small perturbation on the Google matrixG ∈M_N ×N.
The perturbed Google matrix is denoted asG(χ) = [g_ij(χ)], whereχ∈C.
Likewise, the perturbedWis denoted asW(χ). The perturbation is presumed not to remove any nodes or edges, and to preserve the characteristics ofGandW, both of which are row-stochastic, irreducible, and primitive. 
In this article, we impose an analytic perturbation on the Google matrix, as discussed in <cit.>:


    G(χ) =  G + χ G^(1) + χ^2   G^(2) + ….

We assume that 


    G^(l)≤ A_0B_0^l-1   l=1,2,….

whereA_0andB_0are positive constants independent ofl. Assuming that (3.2) converges, such constants certainly exist. 
We also define the matrixT(χ) = [t_ij(χ)]witht_ij(χ) = √( g_ij(χ) g_ji(χ)), and| ψ_j(χ) ⟩ = |j⟩_1 ⊗∑_k=1^N √(g_jk(χ))|k⟩_2.




Then,T(χ)is holomorphic with respect toχwhen|χ|is sufficiently small, and can be expanded as an infinite sum:


    T(χ) =  T + ∑_l=1^∞χ^l  T^(l).

The corresponding eigenvalues of the perturbedT(χ)are denoted as{ λ(χ)}:
obviously,λ(0)=λfor each eigenvalue. To introduce the quantum walk, we further defineB(χ) = ∑_j=1^N |ψ_j (χ)⟩⟨ψ_j (χ)|,    U(χ) =  S_w ( 2 B(χ) -  I).The corresponding eigenvalues and normalized eigenvectors of the perturbedU(χ)are denoted as{ μ(χ)}and{ |μ(χ)⟩ }, respectively. 
As the above-definedUis an unitary operator onℋ, all of its eigenvalues have unity magnitude.
The quantum PageRank at timemunder perturbation is then found by


    I_q^(χ)(i,m | ψ(0) ) = |
     ∑_μ∈ H_e,  j ∈ V (μ(χ))^2m⟨j,i | μ (χ)|⟨%s|%s⟩⟩μ(χ) | ψ(0)|^2,

where the summation is taken over the set of corresponding unperturbedμ's
 inH_e. The perturbation is assumed to be very small, such that|μ(χ)| < 1   ∀μ=μ(0) ∈ H_e.§ MAIN RESULTS

We now give the main statement in this article.


Let m ∈ N be arbitrary, and assume that there exists at least one dangling node in the network. Then, when χ∈ C is sufficiently small, 
the temporal quantum PageRank is holomorphic with respect to χ on the real axis. That is, within a neighborhood of the real axis, it can be represented in the form:


    I_q^(χ)(i,m |ψ(0)) = I_q(i,m|ψ(0))
      + ∑_n=1^∞χ^l I_q^(n) (i,m |ψ(0)) 
    
       ∀ i=1,…,N,  ∀ψ(0) ∈ H_d.

Under Assumption  (3.3), the convergence radius of this expansion is determined by N, m, A_0, B_0, the elements of G, and the isolation distance of T.

In addition, each term in the right-hand side of  (4.1) is estimated from above in the region stated as above: 


    |I_q^(n) (i,m |ψ(0)) | ≤ A_1B_1^n-1  (n=1,2,…),

where the constants A_1,   B_1>0 depend on the same quantities as the convergence radius.


The term `holomorphic on the real axis' means that the quantum PageRank is holomorphic in a neighborhood of the real axis.I_q(i,m|ψ(0))is oscillatory, and and is not temporally convergent in general. Instead, the following quantity is convergent: 




The average temporal quantum PageRank is defined as:
I̅_q(t,i|ψ(0)) ≡1/t∑_m=0^t-1 I_q(i,m | ψ(0) )
   ∀ t ∈ N.


In this definition, we can state the following facts. 


The average of the temporal quantum PageRank converges as time tends to infinity. The limit is given by


    I_∞(i | ψ(0) ) ≡lim_t →∞I̅_q(t,i | ψ(0)) 
    
       
     = ∑_p,q∑_j ∈ V⟨μ_p | ψ(0)|⟨%s|%s⟩⟩μ_q | ψ(0)^*
          ⟨j,i | μ_p |⟨%s|%s⟩⟩μ_q | j,i,

where the first summation is taken over the pairs of eigenvalues (μ_p,μ_q) satisfying μ_p=μ_q.


If all eigenvalues of T are simple, then 


    I_∞(i | ψ(0) )
      = ∑_h=1^N∑_j ∈ V  | ⟨μ_h | ψ(0)||⟩^2 | ⟨ j,i | μ_h||⟩^2


This statement directly derives from the results of <cit.>.
They also discussed the upper bound of the mixing time:


The following inequality holds: 


    |I̅_q(t,i| ψ(0)) - I_∞ (i| ψ(0))|
      ≤∑_μ_p, μ_q ∈ H_e μ_p μ_q2 | ⟨μ_p | ψ(0)||⟩^2 / t |μ_p - μ_q|.



It is seen thatI̅_q(t,i | ψ(0)) andI_∞(i | ψ(0) )are not usually analytic under an analytic perturbation onG.
Actually (as seen later), some eigenvalues ofU(χ)may split into several eigenvalues asχgrows.

 In that case, 
the terms in the summation on the right-hand side of (4.2) will increase, meaning that they may change drastically under even a small perturbation.



§ PROOF OF THEOREM 4.1

This section will prove Theorem 4.1. The proof is divided into several steps. 



 §.§ Perturbation on G

Assuming an analytic perturbation onG, we defineg_ij(χ) = g_ij + χ g_ij^(1) + χ^2 g_ij^(2) + …≡ g_ij + g̃_ij(χ).The elements ofT(χ) = [t_ij(χ)]are then given as


    t_ij(χ) 
     = √(( g_ij + g̃_ij(χ) )  (g_ji + g̃_ij(χ) ))
    
    
     = t_ij + ∑_n=1^∞χ^n t_ij^(n),

for smallχthat satisfies|g̃_ij(χ)| < 1.  Note that each element of the Google matrix differs from zero <cit.>, andt_ij^(n)is defined ast_ij^(n) = 1/n!(  d/ dχ)^n t_ij(χ) |_χ=0,(see <cit.> for instance). By Leibnitz's rule, we have 


    (  d/ dχ)^n t_ij(χ)  = 
     t_ij∑_k=0^n  _nC_k
      (  d/ dχ)^k
       [
        √(1+ğ_ij(χ) )] 
    
    
      (  d/ dχ)^n-k[
        √(1+ğ_ji(χ) )],

whereğ_ij(χ)
  ≡g̃_ij(χ)/g_ij≡ g_ij(χ) - g_ij/g_ij .(Note thatğ_ij(0) = g̃_ij(0) = 0). 
By the derivative formula of composite functions <cit.>, and settingf(z)=√(1+z), we have


    (  d/ dχ)^n
        [
         √(1+ğ_ij(χ) )] 
    
    
     = (  d/ dχ)^n
        f(ğ_ij(χ)) 
    
        
    = ∑_r=1^n D^r f(ğ_ij (χ))/r!
    
     ∑_p_1+… + p_r=n  p_i ≥ 1n!/p_1! p_2! … p_r!( D^p_1ğ_ij)
         ( D^p_2ğ_ij) …( D^p_rğ_ij).

Noting that

    (  d/ dχ)^r   [ √(1+z)]
     =  _1/2 C_r( 1+z )^-(2r-1)/2,

andD^p_i ğ_ij(χ)|_χ=0 =  p_i! g_ij^(p_i)/ g_ij   ( i=1,2,…,r), we have



    (  d/ dχ)^n   [
        √(1+ğ_ij(χ) )] |_χ=0
    =
     n! ∑_r=1^n  _1/2 C_r/ g_ij^r∑_p_1+… + p_r=n  p_i≥ 1∏_τ=1^r g_ij^(p_τ).

In terms of this expression,t_ij^(n)becomes


    t_ij^(n) = 
     t_ij[
      ∑_r^'=1^n _1/2 C_r^'/g_ji^r^'∑_p_1+… + p_r^'=n  p_i ≥ 1∏_τ^'=1^r^'
         g_ji^(p_τ^')] 
    
       
     +t_ij∑_k=1^n-1
     [
      ∑_r=1^k  _1/2 C_r/g_ij^r∑_p_1+… + p_r=k  p_i ≥ 1∏_τ=1^r g_ij^(p_τ)] 
    
    
    [
      ∑_r^'=1^n-k _1/2 C_r^'/g_ji^r^'∑_p_1+… + p_r^'=n-k  p_i ≥ 1∏_τ^'=1^r^'
         g_ji^(p_τ^')] 
    
       
    + t_ij[
      ∑_r=1^n _1/2 C_r/g_ij^r∑_p_1+… + p_r=n  p_i ≥ 1∏_τ=1^r
         g_ij^(p_τ)] 
    
       ≡ I_1(n)^(i,j)+I_2(n)^(i,j)+I_3(n)^(i,j).

For instance, we have 


    t_ij^(1) 
     = 1/2t_ij( g_ij^(1) g_ji + g_ji^(1) g_ij).


 §.§ Perturbation on T

Based on the discussion in the previous subsection, we represent


    T(χ) =  T + ∑_n=1^∞χ^n  T^(n)  
     (|g̃_ij (χ)| < 1  ∀ i,j ∈ V).


Note thatTandT(χ)forχ∈Rare symmetric, and consequently semisimple.
The resolvent ofTis denoted asR(ζ) ≡ ( T -ζ I )^-1,and the eigenprojection corresponding to eigenvalueλ_hisP_h ≡ -1/2π i∫_Γ_h R(ζ)   dζ.Here,Γ_his an arbitrary convex loop enclosingλ_hin the complex plain, excluding all other eigenvalues ofT.
We now represent the resolvent and eigenprojection under a small perturbation. We denote the resolvent ofT(χ)byR(ζ,χ) ≡( T(χ) - ζI)^-1,
whereζ∈C ⋂σ(T(χ))^c.R(ζ,χ)is defined for allζ∉σ(T(χ)). We know thatR(ζ,χ)is holomorphic with 
respect toζandχfor such aζ(see Theorem II.1.5 in <cit.>),
and is expanded as follows: 


    R(ζ,χ) 
     =  R(ζ) [  I +  A(χ)  R(ζ) ]^-1
    
    
     =  R(ζ) + ∑_l=1^∞χ^l  R^(l)(ζ),

whereA(χ) = T(χ) - T, and 


    R^(l)(ζ) ≡∑_ν_1+… + ν_p=l ν_j ≥ 1
     (-1)^p  R(ζ)  T^(ν_1) R(ζ)  T^(ν_2)…
    
         R(ζ)  T^(ν_p) R(ζ).

Here,  the summation on the right-hand side is taken over all possible values ofp ∈Nand(ν_1, …, ν_p)meeting the condition below the summation symbol.
Integrating the infinite series (5.2) overΓ_h, the perturbation of the projection operatorP_h(χ)is rendered as


    P_h(χ) = -1/2π i∫_Γ_h R(ζ,χ)   dζ
        =  P_h + ∑_l=1^∞χ^l  P_h^(l).P_h(0) =P_h 
 = -1/2πi ∫_Γ_h R(ζ)   dζ.
In (5.3),P_h^(l)is given by


    P_h^(l)  
     = - 1/2π i∑_ν_1+… + ν_p=l, ν_k ≥ 1
    
    
       (-1)^p ∫_Γ_h R(ζ)   T^(ν_1) R(ζ)   T^(ν_2)… R(ζ)   T^(ν_p) R(ζ)    dζ.

We also defineS_h =  -1/2π i∫_Γ_h (ζ -λ_h)^-1 R(ζ)   dζ,which satisfiesP_hS_h = S_hP_h = O, whereOis the zero matrix. 

Additionally, we have
TP_h = λ_h P_h + D_h,
whereD_his referred as the  eigennilpotent operator ofT.
For later use, withq ∈Zwe define:


    S_h^(0) = - P_h,    S_h^(q) =  S_h^q   (q>0), 
       S_h^(q) =  O  (q<0).

Here, we have used the fact thatUis unitary, and therefore normal, meaning that its corresponding eigennilpotent operator vanishes.
Using the same fact, we will later discuss the form of the eigenvalues ofUunder a perturbation.
For simplicity, we omit the subindexhprovided there is no ambiguity.



 §.§ Perturbation on eigenvalue of T

We now expandλ_h(χ), the eigenvalues ofT(χ). Using the resultant representation, we will later find the form of the perturbed eigenvalues ofU.
We first discuss whetherλ_h(χ)is holomorphic on a certain region in the complex plane. To answer this question, we need the following facts from <cit.>.


Let X be an unitary space and let χ_0 ∈ D_0 for a certain simply connected
region D_0 ⊂ C.
In addition, let a sequence {χ_n} converges to χ_0, and let T(χ_n)   (n=1,2,…) be normal.

All eigenvalues and eigenprojections of T(χ), denoted as λ_h(χ) and P_h(χ) respectively, are then holomorphic at χ=χ_0.


Let { T(χ) }_χ be a general family of normal matrices,
 that are holomorphic with respect to χ∈ R. Then, their eigenvalues {λ_h(χ)} are also
holomorphic with respect to χ on R.

In our case,TandUare symmetric and unitary operators, respectively, so satisfy Theorem 5.1 and Corollary 5.1, respectively.
Therefore,λ_h(χ)andμ_h(χ)are holomorphic on the real axis. Within a neighborhood of the real axis, they can be expressed in the form


    λ_h(χ) = λ_h + ∑_n=1^∞χ^n λ_h^(n),  
    μ_h(χ) = μ_h + ∑_n=1^∞χ^n μ_h^(n).

Hereafter, the first and second equalities in (5.6) are denoted as (5.6)_1and (5.6)_2, respectively.

Our next question is: how do we find and estimate the coefficients of the above expansion?
The estimates of coefficients are also needed for finding the error bounds, as discussed later. 
Ifλ_his a simple eigenvalue ofT, we can write


    λ_h^(n) = ∑_p=1^n (-1)^p/p∑_ν_1 + … + ν_p=n  k_1+ … + k_p = p-1 tr  T^(ν_1) S_h^(k_1)… T^(ν_p) S_h^(k_p).

We also have an estimate of the form 


    |λ_h^(n) | ≤ϱ_h  r_h^-n,

wherer_his the convergence radius of (5.6)_1, andϱ_h = max_ζ∈Γ_h |ζ-λ_h|withΓ_has defined in Section 5.2. 

To find the convergence radius of (5.6)_1, we first definer^(h)(ζ)>0whereζ∈Γ_has a number satisfying∑_n=1^∞( r^(h)(ζ) )^n  T^(n) R(ζ) =1.Then, for|χ| < r^(h)(ζ),
∑_n=1^∞|χ|^n T^(n) R(ζ) <1
holds.

For suchχ, the infinite sumA(χ)  R(ζ) 
 = (∑_n=1^∞χ^n   T^(n))  R(ζ)converges to a value less than1, meaning that (5.2) and (5.3) also converge there. That is,r_h =min_ζ∈Γ_h r^(h)(ζ).
Actually, asTis normal, the lower bound ofr_his given by( 2A̅/d_h + B̅ )^-1for some constantsA̅,   B̅>0and the isolation distanced_hofλ_h.
 The convergence radius is then given by 


    r_1 = min{min_i,j ∈ V r_ij, min_h=1,2,… ,s{ r_h }},

wherer_ijis the value ofχsatisfyingg̃_ij(χ) = 1. For lowern's, (5.7) simplifies to


    λ^(1) = (  T^(1)ϕ, ψ), 
    
       λ^(2) = (  T^(2)ϕ, ψ)
     - ∑_j (λ_j-λ_h)^-1(  T^(1)ϕ, ψ_j )
     (  T^(1)ϕ_j, ψ).

Here,ϕis an eigenvector corresponding toλ,ψis the eigenvector ofT^*corresponding toλ^*(whereT^*is the adjoint operator ofT),{λ_j }are the eigenvalues ofTwith corresponding eigenvectors{ ϕ_j },
and{ψ, ψ_j}is the basis ofX^*adjoint to the basis{ϕ, ϕ_j}ofX.

In general, some eigenvalues may not be simple whenχ=0, and may split asχgrows.
In this case, Eq. (5.6)_1only sums the perturbed eigenvalues, and the expansion of each eigenvalue remains unknown.
To calculate the explicit expansion of each eigenvalue, we apply the  reduction process (for details, see <cit.>).

Algorithm 1 shows the overall process for finding the explicit expansions of all eigenvalues, along with descriptions of each process. Our idea is to construct a `tree of eigenvalues'
(see Figure 1). 





The top level contains the eigenvalues ofT, which may include simple and non-simple types.
The edges of the non-simple eigenvalues are extended to the descendant eigenvalues in the next level, found through the reduction process.
On the other hand, the simple eigenvalues have no further edges. We now derive the descendant eigenvalues from the non-simple eigenvalues in the former level. 

For a certain non-simple eigenvalueλ_hofT, we can expand a perturbed eigenprojection of the form (5.3). We thus obtain


    (  T (χ) - λ_h  I)  P_h(χ) 
     = ∑_n=1^∞χ^n  T_0^(n),

where 


    T_0^(n) 
     = -1/2π i∑_ν_1 + ν_2 + … + ν_p=n ν_j ≥ 1
    
      ∫_Γ_h R(ζ)  T^(ν_1)… T^(ν_p) R(ζ) (ζ-λ_h)   dζ
    
        
     = - ∑_p=1^n (-1)^p
        ∑_ν_1 + ν_2 + … + ν_p=n  k_1+… +k_p+1 = p-1,
        ν_j ≥ 1, k_j ≥ 0
    
          S_h^(k_1) T^(ν_1)… S_h^(k_p) T^(ν_p) S_h^(k_p+1).

Using this expression, we introduceT_0(χ) ≡(  T(χ) - λ_h  I)/χ P_h(χ)
 = ∑_n=0^∞χ^n  T_0^(n+1),AsTis symmetric,λ_his semisimple, so the terms are simplified.
For instance, the spectral decomposition ofT_0^(1)inR(P_h)is given as


    T_0^(1) =  P_h  T^(1) P_h
      = ∑_j^(1)λ_0 ,j^(1) P_0, j^(1).

Here,{ λ_0,j^(1) }_j^(1) are the 
eigenvalues ofT_0^(1)inR(P_h).
We call these eigenvalues the descendant eigenvalues ofλ_0in level-1.

Note thatT_0^(1) = T_0(0) ≡T_0.
Actually, if we setλ_has the top node of the tree, the descendant eigenvalues{ λ_0, j^(1) }_j^(1) are clearly derived fromλ_h.

At the beginning of the process, we initialize a set of non-simple eigenvalues ofTasΦ_(0). 
 IfΦ_(0)=ϕ, no further processing is required, and each eigenvalue ofTis explicitly expanded by Eq. (5.6)_1.

Otherwise, we find the descendant eigenvalues of each element inΦ_(0), and initialize a setΦ_(1)of non-simple eigenvalues in level-1 (line 7 in Algorithm 1).
IfΦ_(1) = ϕ, each eigenvalue in level-1 is explicitly expanded by Eq. (5.6)_1.
The eigenvaluesλ_0, j^(1) (χ)are then explicitly expanded asλ_0, j^(1) (χ) = λ_0, j^(1)
  + ∑_n=1^∞χ^n λ_0, j^(1)^(n),and the corresponding eigenvalue ofT(χ)are expressed as


    λ_h(χ) = λ_h + χλ_0,j^(1)(χ)
    
       
    =λ_h + χλ_0,j^(1)
      + ∑_n=1^∞χ^n+1λ_0,j^(1)^(n).

The λ_0,j^(1)^(n)are given by (5.7), withT^(ν)andS_h^(k)replaced byT_0^(ν+1)andS_1^(k)(defined later), respectively. 

IfΦ_(1) ϕ, the reduction process is reiterated to find the descendant eigenvalues of those inΦ_(1).

We now explain our procedure in detail, denotingλ_0,,j^(1) byλ_0,1andP_hbyP_0for simplicity.
Letλ_0,1 ∈Φ_(1)be the eigenvalue ofT_0, and the descendant eigenvalue of a certainλ_0.
We also take the corresponding perturbed eigenvalueλ_0,1(χ)as the eigenvalue ofT_0^(1)(χ).
The eigenprojectionP_0,1corresponding to thisλ_0,1inR(P_0)is computed as 


    P_0,1 = ∫_Γ_0,1 R_0,1 (ζ)   dζ,

whereR_0,1 (ζ) = (  T_0 - ζI)^-1, andΓ_0,1is a closed curve isolatingλ_0,1from all other eigenvalues ofT_0.

We thus defineT_0,1 = P_0,1  T_0^(2) P_0,1,
and


    P_0,1^(n) = 
      -∑_p=1^n (-1)^p 
        ∑_ν_1+ … +ν_p=n  k_1 + … +k_p+1=p, ν_j ≥ 1, k_j ≥ 0
    
    
         S_1^(k_1) T_0^(ν_1+1)… S_1^(k_p) T_0^(ν_p+1) S_1^(k_p+1), 
    
        T_0,1^(n) = -∑_p=1^n (-1)^p
    ∑_ν_1+… +ν_p = n  k_1+… + k_p+1=p-1,  ν_j ≥ 1,   k_j ≥ 0
    
    
     S_1^(k_1) T_0^(ν_1+1)… S_1^(k_p) T_0^(ν_p+1) S_1^(k_p+1).

Here,


    S_1^(k) = 
     {[ [  S_1^' - 1/λ_0,1(  I- P_0 ) ]^k    (k ≥ 1),;                               - P_0,1   (k=0) ].

withS_1^'≡ -∑_λ_0,1^'λ_0,1 P_λ_0,1^'/|λ_0,1 - λ_0,1^'|.Above we assumed thatλ_0,1 0, andP_λ_0,1^'is an eigenprojection corresponding toλ_0,1^'.
The summation runs over all eigenvalues ofT_0exceptλ_0,1. We then define


    P_0,1(χ) =
       P_0,1 + χ P_0,1^(1) + χ^2  P_0,1^(2) + …, 
    
        T_0,1 (χ) ≡(  T_0(χ) - λ_0,1 I) /χ P_0,1(χ)
     = ∑_n=0^∞χ^n  T_0,1^(n+1).

From (5.10), it is seen thatT_0,1 ≡T_0,1 (0) =  T_0,1^(1) = P_0,1 T_0^(2) P_0,1.Now, the eigenvalues ofT_0,1andT_0,1(χ)(denoted asλ_0,1,2andλ_0,1,2(χ), respectively)
are the descendant eigenvalues ofλ_0,1in level-2. This procedure is applied to all eigenvalues inΦ_(1)in level-1.

Now, if the eigenvalueλ_0,1,2ofT_0,1(0)=T_0,1is simple, its perturbed value is represented asλ_0,1,2 (χ) = ∑_n=0^∞χ^n λ_0,1,2^(n).The λ_0,1,2^(n)are given by (5.7), replacingT^(ν)andS_h^(k)byT_0,1^(ν+1)andS_2^(k)(defined later), respectively. 
The corresponding eigenvalue ofT(χ)is represented as


    λ (χ) = λ_0 + χλ_0,1 + χ^2 ∑_n=0^∞χ^n λ_0,1,2^(n).

If all of these eigenvalues are simple, they can be determined by Eq. (5.6)_1, and the procedure terminates.
Otherwise, we should recheck whether all eigenvalues in level-2 are simple. For this purpose, we initialize a setΦ_(2)of non-simple eigenvalues in level-2, and discuss the caseΦ_(2) ϕ.
We first introduce


    P_0,1,2 = ∫_Γ_0,1,2 R_0,1,2 (ζ)   dζ,

whereR_0,1,2 (ζ) = (  T_0,1- ζI)^-1, andΓ_0,1,2is a closed curve that isolatesλ_0,1,2from all other eigenvalues ofT_0,1.

We also define:


    P_0,1,2^(n) = -∑_p=1^n (-1)^p
    ∑_ν_1+… +ν_p = n  k_1+… + k_p+1=p,  ν_j ≥ 1,   k_j ≥ 0
    
      S_2^(k_1) T_0,1^(ν_1+1)… S_2^(k_p) T_0,1^(ν_p+1) S_2^(k_p+1),
    
        T_0,1,2^(n) = -∑_p=1^n (-1)^p
    ∑_ν_1+… +ν_p = n  k_1+… + k_p+1=p-1,  ν_j ≥ 1,   k_j ≥ 0
    
      S_2^(k_1) T_0,1^(ν_1+1)… S_2^(k_p) T_0,1^(ν_p+1) S_2^(k_p+1),

where


    S_2^(k) = 
     {[ [  S_2^' - 1/λ_0,1,2(  I- P_0,1) ]^k    (k ≥ 1),;                                - P_0,1,2   (k=0) ].

withS_2^'≡ -∑_λ_0,1,2^'λ_0,1,2 P_λ_0,1,2^'/|λ_0,1,2 - λ_0,1,2^'|.We assume thatλ_0,1,2 0, and letP_λ_0,1,2^'be an eigenprojection corresponding toλ_0,1,2^'.
The summation of the right-hand side runs over all eigenvalues ofT_0,1exceptλ_0,1,2. 
We then introduce


    P_0,1,2(χ) =  P_0,1,2 + ∑_j=1^∞χ^j  P_0,1,2^(j),
    
        T_0,1,2 (χ) ≡(  T_0,1(χ) - λ_0,1,2 I) /χ P_0,1,2(χ)
     = ∑_n=0^∞χ^n  T_0,1,2^(n+1).

Again, we note thatT_0,1,2 ≡T_0,1,2 (0) 
 = T_0,1,2^(1) = P_0,1,2 T_0,1^(2) P_0,1,2.Now, the eigenvalues ofT_0,1,2andT_0,1,2(χ),
denoted asλ_0,1,2,3andλ_0,1,2,3(χ), respectively, 
are the descendant eigenvalues ofλ_0,1,2in level-3.
This procedure is applied to all eigenvalues inΦ_(2)in level-2.
Repeating this procedure until none of the eigenvalues split, we obtain the exact representations of all eigenvalues.  
Note that the procedure halts within a finite number of iterations (at most level-N iterations). 

Without loss of generality, we have assumed that all eigenvalues (including the descendant ones) do not vanish. If some eigenvalues do vanish, 
the unit ofχcan be adjusted so that all eigenvalues that appear in the iteration prodedure always remain non-vanishing. 


While tracing the tree, the convergence radius should be updated as the minimum of r_1 computed by  (5.9) or the convergence radius of the eigenvalue at the bottom of each path. 
Because this procedure expires after finitely many iterations, we can obtain the final convergence radius, and assign it to r_1.
In addition, the estimated expression  (5.8) holds for all λ_h.

By resetting the constants, we can replace ϱ_h and r_h with constants independent of h, hereafter denoted as ϱ_1 and r_1, respectively. 

This fact is summarized as a proof at the end of this subsection. 


Assume that  (3.3) holds. In the above expressions of λ_h(χ), we have |λ_h^(n)| ≤ϱ_1 r_1^n   (n=1,2,…,   h=1,2,…, s) 
with constants ϱ_1,   r_1 > 0 independent of h.


For the eigenvalues of T, it is sufficient to assume (5.33) (see Lemma 5.4 for proof). It remains to show that  Lemma 5.1 holds for the descendant eigenvalues.
Now, take a simple eigenvalue λ_0,1,…,L+1 of T_0,1,…,L in level-(L+1), and perturb it as λ_0,1,…,L+1(χ).
The perturbed eigenvalue is an eigenvalue of T_0,1,…,L(χ) = ∑_n=0^∞χ^n  T_0,1,…,L^(n+1).
The corresponding eigenvalue of T is then denoted as 


    λ(χ) = λ_h + χł + λ_0,1 + … +χ^L λ_0,1,…,L
    +χ^L+1∑_n=0^∞χ^n λ_0,1,…,L+1^(n).

It is sufficient to show that T_0,1,…,L^(n) are estimated as 


    T_0,1,…,L^(n)≤A_L B_L^n-1  n=1,2,….

We show this by induction. First consider the case L=0. As T is normal, we have 
S_h≤ 1/min_λ_k λ_h |λ_k - λ_h|.
Using this, we can write 


    T_0^(n)≤∑_p=1^n 
      | 1/min_λ_k λ_h |λ_k - λ_h| |^p-1∑_ν_1+… +ν_p=n  k_1 + … + k_p+1 = p-1 A_2^p B_2^n 
    
       
     = B_2^n ∑_p=1^n | 1/min_λ_k λ_h |λ_k - λ_h| |^p-1
       A_2^p  _n-1 C_n-p _2p-1 C_p-1
    
       ≤ 2^2n-1 B_2^n C_h^-1[ C_h A_2 ( 1 + C_hA_2 )^n-1] ,

where C_h ≡| 1/min_λ_k λ_h |λ_k - λ_h| |.
Thus, (5.12) holds for L=0. 
Next, assume that (5.12) holds for L=(l-1). Then, for L=l, 


    T_0,1,…,l^(n) = 
     -∑_p=1^n (-1)^p
       ∑_ν_1+… +ν_p=n  k_1 + … + k_p+1 = p-1,ν_j ≥ 1,k_j ≥ 0
    
         S_l^(k_1) T_0,1,…, l-1^(ν_1+1)… S_l^(k_p) T_0,1,…, l-1^(ν_p+1) S_l^(k_p+1).

Assuming (5.12), we have T_0,1,…,l-1^(n)≤A_l-1B_l-1^n-1.
Recall also that


    S_l^(k) = 
     {[ [  S_l^' - 1/λ_0,1,…,l(  I- P_0,1,…,l) ]^k    (k ≥ 1),;                                     - P_0,1…,l   (k=0) ].

with 


    S_l^'≡ -∑_λ_0,1,…,l^'λ_0,1,…,l P_λ_0,1,…,l^'/min|λ_0,1,…,l - λ_0,1,…,l^'|, 
    
        P_0,1,…,l = ∫_Γ_0,1,…,l R_0,1,…,l(ζ)   dζ,   
    
     R_0,1,…,l(ζ) = (  T_0,1,…, l-1^(1) -ζ I)^-1,

where Γ_0,1,…,l encloses the eigenvalue λ_0,1,…,l. 

As T_0,1,…,l^(1) is normal, we have P_0,1,…,l and P_λ_0,1,…,l^' = 1. We also observe that 


    S_l^(k)≤max{ 1, ( 1/min |λ_0,1,…,l - λ_0,1,…,l^'|  
           + 1/λ_0,1,…,l)^k }
    
      ≡max{ 1, C_l^k }.

We thus arrive at


    T_0,1,…,l^(n)≤∑_p=1^n
       ∑_ν_1+… +ν_p=n  k_1 + … + k_p+1 = p-1,ν_j ≥ 1,k_j ≥ 0
    
    
       max{ 1, C_l^p-1}A_l-1^pB_l-1^n 
    
       
      = B_l-1^n ∑_p=1^n 
         max{ 1, C_l^p-1}A_l-1^p  _n-1C_n-p _2p-1C_p-1,

where A_l-1 and B_l-1 are some positive constants.
The desired estimate T_0,1,…,l^(n)≤A_l B_l^n-1 is then deduced as described for (5.13).



 §.§ Perturbation on U

This subsection discusses the form ofUunder a perturbation. We first consider the expansion of|ψ_j (χ)⟩ 
  = |j⟩_1 ⊗∑_k=1^N √(g_jk(χ)) |k⟩_2with respect toχ. For this purpose, we find the expansion of√(g_jk(χ)).
Now,√(g_jk(χ)) = √(g_jk (1+ğ_jk(χ))), whereğ_jk(χ) ≡(g_jk(χ) - g_jk)/g_jk.

The coefficient of√( 1+ğ_jk(χ)) ofχ^n, denoted asa_(j,k)^(n), is represented as


    a_(j,k)^(n) = 1/n!(  d/ dχ)^n
     [ √( 1+ğ_jk(χ))]
      |_χ=0.

Now, 


    (  d/ dχ)^n
        [ √( 1+ğ_jk(χ))]
         |_χ=0
    
     = ∑_r=1^n  _1/2 C_r
         ∑_p_1+… p_r=n  p_j ≥ 1n !/p_1 ! … p_r !∏_i=1^r 
           ( p_i! g_jk^(p_i)/g_jk) 
    
       
     =  n! ∑_r=1^n  _1/2 C_r ∑_p_1+… p_r=n  p_j ≥ 1∏_i=1^r   g_jk^(p_i)/g_jk.

Therefore, we have 


    a_(j,k)^(n) = ∑_r=1^n  _1/2 C_r ∑_p_1+… p_r=n  p_j ≥ 1∏_i=1^r   g_jk^(p_i)/g_jk,

which gives


    |ψ_j(χ)⟩
     
      
       
    
    
     = |ψ_j⟩ + ∑_n=1^∞|ψ_j^(n)⟩χ^n.

The convergence radius of (5.14) is lower-bounded byr_1.B(χ)is then expanded as 


    B(χ) = ∑_j=1^N |ψ_j(χ)⟩⟨ψ_j(χ)|
     =  B + ∑_n=1^∞ B^(n)χ^n,

whereB^(n)  
= ∑_j=1^N ∑_l=0^n |ψ_j^(l)⟩⟨ψ_j^(n-l)|.For simplicity, we have used the notation|ψ_j^(0)⟩ = |ψ_j⟩. Expanded as (5.14) and (5.15), the operatorUunder a perturbation is represented as 


    U(χ) =  S_w ( 2  B(χ) -  I)
     =  U +  ∑_n=1^∞ U^(n)χ^n,

where 


    U^(n) = 2  S_w   B^(n)
     = 2 S_w ∑_j=1^N ∑_l=0^n 
      |ψ_j^(l)⟩⟨ψ_j^(n-l)|.


The infinite sum (5.16) converges as far as|ψ(χ)⟩, so their convergence radii are alsor_1.We now define the eigenprojection ofUfor each eigenvalue ofU.

Note thatUandU(χ)are unitary, and consequently semisimple. The resolvent ofUis defined as
R̂(ζ) ≡(U -ζI )^-1,
and the eigenprojection corresponding to eigenvalueμ_h(recall thatμ_hcan be±1) isP̂_h ≡
  -1/2π i∫_Γ̂_h R̂(ζ)   dζ.Here,Γ̂_his an arbitrary convex loop in the complex plain that isolatesμ_hfrom all other eigenvalues ofU. 
We now represent the resolvent and eigenprojection under a small perturbation. 
We denote the resolvent ofU(χ)byR̂(ζ,χ) ≡( U(χ) - ζI)^-1, whereR̂(ζ,χ)is defined for allζ∉σ(U(χ)). We know that for such aζ,R̂(ζ,χ)is holomorphic with respect to bothζandχ, and is hence expanded as follows: 


    R̂(ζ,χ) 
     =R̂(ζ) [  I + Â(χ) R̂(ζ) ]^-1
    
    
     = R̂(ζ) + ∑_l=1^∞χ^l R̂^(l)(ζ),

whereÂ(χ) = U(χ) - U, and 


    R̂^(l)(ζ) ≡∑_ν_1+… + ν_p=l ν_j ≥ 1
     (-1)^p R̂(ζ)  U^(ν_1)R̂(ζ)  U^(ν_2)…
                 R̂(ζ)  U^(ν_p) R(ζ).

Integrating the infinite series (5.18) overΓ̂_h, we have


    P̂_h(χ) = -1/2π i∫_Γ̂_hR̂(ζ,χ)   dζ
        = P̂_h + ∑_l=1^∞χ^l P̂_h^(l).

Equation (5.19) satisfiesP̂_h(0) = P̂_h
 = -1/2πi ∫_ Γ̂_h R̂(ζ)   dζ.
In (5.19),P̂_h^(l)is given by


    P̂_h^(l)  
     = - 1/2π i∑_ν_1+… + ν_p=l ν_k ≥ 1
       (-1)^p ∫_Γ̂_hR̂(ζ)   U^(ν_1)
    
    
         R̂(ζ)   U^(ν_2)…R̂(ζ)   U^(ν_p)R̂(ζ)    dζ.

We also defineŜ_h =  -1/2π i∫_Γ̂_h  (ζ -μ_h)^-1R̂(ζ)   dζ,which satisfiesP̂_h Ŝ_h= Ŝ_hP̂_h= O.

Additionally, we have
U P̂_h = μ_h P̂_h .
For later use, whenq ∈Zwe define:


    Ŝ_h^(0) = -P̂_h,   Ŝ_h^(q) = Ŝ_h^q   (q>0), 
      Ŝ_h^(q) =  O  (q<0).

Here, we have used the fact thatUis unitary, and therefore normal.
Later, these expressions will be used for deriving the transformation function of{ |μ⟩ }.



 §.§ Perturbation on the eigenvalues of U

We now represent the eigenvalues ofU(χ). 





















The eigenvalues ofU(other than those of-S_w) are given byμ = λ± i√( 1-  λ^2).Accordingly, the eigenvalues ofU(χ)areμ(χ) = λ(χ) + i ( 1- ( λ(χ) )^2 )^1/2forχsufficiently close to the real axis, whereλ(χ)'s are the eigenvalues ofT(χ).

Note that|χ|is sufficiently small that|λ(χ)|<1.
Therefore, denoting byr_2the value|λ(χ)|=1for|χ|=r_2, the convergence radius of (5.6) isr_0 = min{ r_1, r_2}.As far as|λ(χ) |<1is satisfied, the branches of( 1- ( λ(χ) )^2 )^1/2are holomorphic with respect toχ.

Therefore, expanding thisμ(χ)as a series ofχ, we getμ(χ) = μ + ∑_n=1^∞χ^n μ^(n).To show this, we first expand√( 1- ( λ(χ) )^2),and recallμ^(n) = 1/n!(  d/ dχ)^n μ(χ) |_χ=0  (n=1,2,…).We now discuss 


    1/n!(  d/ dχ)^n 
     ( √(1-(λ(χ))^2))
     |_χ=0.

Settingf(z)=√(1-z^2), we have 


    (  d/ dχ)^n ( f(λ(χ)) ) |_χ=0
     = ∑_r=1^n D^r f(λ(χ))) /r!
     
    
      ∑_p_1+… +p_r=n  p_i≥ 1n!/ p_1! … p_r!( D^p_1λ(χ) ) …( D^p_rλ(χ) )|_χ=0
    
       
     =  n! ∑_r=1^n D^r f(λ(χ))) /r!|_χ=0∑_p_1+… +p_r=n  p_i ≥ 1∏_j=1^r λ^(p_j),

where we have usedD^p_j λ(χ) |_χ=0 = p_j ! λ^(p_j).To express the termD^r fin (5.23) above, we seth(w)=√(1-w)andl(t)=t^2, thus obtaining


    (  d/ dt)^r h(l(t))
     = ∑_r^'=1^r D^r^' h(l(t))) /r^'!
    
     ∑_p_1^'+… +p_r^'^'=r  p_i^'≥ 1r!/ p_1^' ! … p_r^'^' !( D^p_1^' l) …( D^p_r^'^' l).

We also note thatp_i^'∈{1,2}   (i=1,2,…,r^')and 


    D^p_i^' l = 
     {[ 2t    (p_i^'=1),;  2    (p_i^'=2). ].

On the other hand, we can write


    D^r^'[ √(1-w)] 
     = (-1)^r^' r^' !  _1/2 C_r^'  (1-w)^-(2r^'-1)/2 .

We thus have 


    μ^(n) = λ^(n) +  i∑_r=1^n
     
     [
       ∑_r^'=1^r
       (-1)^r^' _1/2 C_r^'  (1-λ^2)^-(2r^'-1)/2
    
    
    
      ∑_p_1^'+… +p_r^'^'=r  p_i^'>02^r^'λ^(2r^' - ∑ p_i^')/ p_1^' ! 
        … p_r^   '^' !] 
    
    
    
     ∑_p_1+… +p_r=n  p_i ≥ 1∏_j=1^r λ^(p_j),

which gives an explicit representation ofμ(χ).



 §.§ Perturbation on the eigenvectors of U

This subsection considers the perturbed eigenvectors ofU. Note that the spaceℋ = C^N ⊗C^Nhas the orthogonal decomposition:ℋ = H_d + H_d^⊥,whereH_dis the space spanned by{ |ψ_j⟩ }_jand{ S_w |ψ_j⟩ }_j(called  the dynamical space in <cit.>),
 on whichUoperates as an non-trivial operator. Meanwhile, onH_d^⊥(which is spanned by vectors orthogonal to{ |ψ_j⟩ }_j),Uacts as-S_w. 

AsUis unitary, its eigenvectors (here called eigenstates) normalized to unit length form an orthonormal basis inℋ.
Especially, the eigenvectors inH_eform an orthonormal basis there.

Because the imposed perturbation preserves the unitarity ofU(χ), we can take a set of its eigenvectors{ | μ(χ) ⟩ }of unit length as an orthogonal basis ofH_eunder small perturbation. This method will be shown later on.

Similarly, a set of perturbed eigenvectors{ |μ(χ)⟩ }corresponding to the eigenvalues of-S_wforms an orthogonal basis of the space orthogonal toH_e(denoted asH_e^⊥). 

Now, applying the transformation function, we can write 


    |μ(χ) ⟩=  V(χ) |μ⟩,

whereV(χ)is an oprator satisfying


    {[ d/ dχ V(χ) =  Q(χ) V(χ),;               V(0) =  I, ].

withQ(χ) = - ∑_h=1^s P̂_h(χ)
  d / dχ P̂_h(χ). 

AsQ(χ)is holomorphic within a certain region ofC, Eq. (5.25) is guaranteed to have a unique holomorphic solutionV(χ)with an inverse matrixV(χ)^-1.
Actually, this solution satisfiesV(χ)  P(0)  V(χ)^-1 =  P(χ)    (h=1,2,…,s).Using the expansion ofP̂_h(χ)in (5.19), we expandQ(χ)as a series inχ:


    Q(χ) = 
     -∑_h=1^s {P̂_h  
      + ∑_n^'=1^∞χ^n^'P̂_h^(n^')}
    
    
       {P̂_h^(1) 
        + ∑_n=1^∞ (n+1) χ^n P̂_h^(n+1)}
    
       ≡ Q + χ Q^(1) + χ^2  Q^(2)….

Comparing the coefficients, we have 


    Q = -∑_h=1^s P̂_h P̂_h^(1), 
    
        Q^(r) = -∑_h=1^s
     [
       (r+1)P̂_h P̂_h^(r+1)
    
    
    + ∑_r_1=1^r (r-r_1+1) P̂_h^(r_1)P̂_h^(r-r_1+1)] 
    
         (r=1,2,… ).

For instance,Q^(1) = -2 ∑_h=1^s P̂_hP̂_h^(2)-∑_h=1^s
 ( P̂_h^(1))^2.We now seek the solution to (5.25) as an infinite series ofχ:V =   V_0 + ∑_n=1^∞χ^n   V^(n),and formally representV^(n)by comparing the coefficients.
We then observe thatV^(n)'s are estimated from above with certain quantities in order to estimate the convergence radius.

First, from the initial condition, we have V_0 = I.
It is then easily seen that  


    V^(1) =  Q,   V^(2) =  Q^2 +  Q^(1)/2,   V^(3) =  Q^3 +  Q Q^(1)/6.

Likewise, we observe that 


    V^(n)  = ∑_j=0^n-1 Q^(j) V^(n-1-j)/n   (n=4,5,6,…).

Using this, we expand| μ(χ)⟩as


    |μ(χ) ⟩ = |μ⟩ + ∑_n=1^∞χ^n |μ^(n)⟩,

where 


    |μ^(n)⟩ =  V^(n)|μ⟩.

When discussing PageRank, it is sufficient to consider the|μ⟩ ∈H_e.Near the real axis,I_q(χ)can be expanded as follows. First we have 
We have 


    N_q^(χ)( i,m|ψ(0) ) = N_q( i,m |ψ(0)) 
    
     + ∑_r=1^∞χ^r N_q^(r)( i,m |ψ(0))    ∀ i,

where 


    N_q^(n)( i,m |ψ(0))  
    
    
    = ∑_μ∈ H_e  j ∈ V∑_0 ≤ r_1+r_2 ≤ n  r_j ≥ 0[
    μ^2m∑_r^'=1^min{r_1,2m} _2m C_r^'μ^-r^'
    
    
    
     ∑_p_1+… + p_r^'=r_1  p_i ≥ 1∏_τ=1^r^'μ^(p_τ)] 
    
       ×⟨μ^(r_2) | ψ(0)|⟨%s|%s⟩⟩ j,i | μ^(n-r_1-r_2).

This is derived by observing the coefficients ofχ^r_1in the expansion of( μ(χ) )^2m:


    μ^2m∑_r^'=1^min{r_1,2m} _2m C_r^'μ^-r^'∑_p_1+… + p_r^'=r_1  p_i ≥ 1∏_τ=1^r^'μ^(p_τ).

The derivation follows that oft_ij(χ)in Subsection 5.1.  The coefficientsa_1(n;m)ofχ^nin the expansion of(μ(χ))^2mare denoted as


    a_1(n;m) = 1/n!( 
        d/ dχ)^n
     ( μ(χ) )^2m|_χ=0
    
    
    = μ^2m/n!( 
        d/ dχ)^n
     ( 1 + μ̃(χ) )^2m|_χ=0,

whereμ̃(χ)  = (μ(χ) -μ)/μ= ∑_n=1^∞χ^n μ^(n)/μ.Then, settingf(z)=(1+z)^2m, and exploitingD^p_j μ̃(χ) |_χ=0 = p_j ! μ^(p_j)/μ, we have 



    (  d/ dχ)^n ( f(μ̃( χ )) )|_χ=0
     = ∑_r=1^n D^r f(μ̃(χ ))) /r!
    
    
      ∑_p_1+… +p_r=n  p_i ≥ 1n!/ p_1! … p_r!( D^p_1μ̃) …( D^p_rμ̃) 
    
       
     =  n! ∑_r=1^n D^r f(μ̃( χ))) /r! μ^r|_χ=0∑_p_1+… +p_r=n  p_i>0∏_j=1^r μ^(p_j).

Because


    D^r [ ( 1 + z )^2m]
    = {[ _2m C_r
       (1+z)^2m-r
      
         (r=0,1,…, 2m),;                              0   (r ≥ 2m+1). ].

the indexrin (5.30) actually runs from1tomin{ 2m, n}.From these considerations, we have


    a_1(n;m) = μ^2m∑_r=1^min{ 2m, n} _2m C_rμ^-r∑_p_1+… +p_r=n  p_i>0∏_j=1^r μ^(p_j),

which yields (5.29).

We now seek the form ofI_q^(r)(i,m|ψ(0) )   (r=1,2,…).By definition, we have 


    I_q^(χ)(i,m|ψ(0) ) =
     ( 
       ∑_μ(χ) ( μ(χ) )^2m∑_j ⟨ j, i | μ(χ)|⟨%s|%s⟩⟩μ(χ) | ψ(0) ) 
    
       ×( 
       ∑_μ(χ) ( μ(χ) )^2m∑_j ⟨ j, i | μ(χ)|⟨%s|%s⟩⟩μ(χ) | ψ(0) )^* 
    
       
     = ( N_q ( i,m |ψ(0)) 
         + ∑_n=1^∞χ^n N_q^(n) ( i,m |ψ(0))  ) 
    
       ×( N_q ( i,m |ψ(0))
         + ∑_n=1^∞χ^n N_q^(n)( i,m |ψ(0))
       )^* 
    
       
     = I_q(i,m|ψ(0) ) + ∑_n=1^∞χ^n I_q^(n)(i,m|ψ(0) )

By comparing the coefficients, we have 


    I_q^(r) (i,m | ψ(0)) 
     = N_q^(r) ( i,m |ψ(0)) N_q^* ( i,m |ψ(0)) 
    
       
      + ∑_i=1^r-1 N_q^(r-i) ( i,m |ψ(0)) N_q^(i)*( i,m |ψ(0)) 
    
       
      + N_q( i,m |ψ(0)) N_q^(r)* ( i,m |ψ(0)) 
    
    
        (r=1,2,…).


 §.§ Error bounds

We now estimate the latter part of  Theorem 4.1. To this end, we estimate each termI_q^(l)(i,m|ψ(0))   (l=1,2,…,)in 
the perturbed quantum PageRank. We first prepare  the following lemmas.


Assume  (3.3) holds. Then, for l=1,2,…, we have 


    |ψ_j^(l)⟩≤ A_1B_1^l-1  (j=1,2,… ,N,  l=1,2,…),

where the constants A_1,  B_1>0 depend on N and G.


This can be proved using the representation of |ψ_j(χ)⟩ (Eq. (5.14)  in Subsection 5.4).
As |j⟩_1, |k⟩_2 are unit vectors, it is sufficient to estimate a_(j,k)^(n). Under assumption (3.3), we have 


    | 
       ∑_k=1^N 
         [
          ∑_r=1^n g_jk^1/2-r _1/2 C_r
           ∑_p_1 + … + p_r=n  p_j ≥ 1(
              ∏_i=1^r g_jk^(p_i)) 
         ]
      |  
    
    
    
     ≤∑_k=1^N 
         [
          ∑_r=1^n g_jk^1/2-r|  _1/2 C_r |       
           ∑_p_1 + … + p_r=n  p_j ≥ 1
            A_0^r B_0^n-r] 
    
       ≤∑_k=1^N 
       ∑_r=1^n g_jk^1/2-r|  _1/2 C_r |       
        A_0^r B_0^n-r _n-1 C_r-1
       
     = g_jk^1/2 B_0^n ∑_k=1^N ∑_r=1^n
         |  _1/2 C_r |       ( A_0/B_0 g_jk) ^r
           _n-1 C_r-1

Taking δ∈ (0,1), and defining

A_0/B_0 g_jk = δ× A_0/δ B_0 g_jk≡δε_0,
we have


    g_jk^1/2 B_0^n ∑_k=1^N ∑_r=1^n
       |  _1/2 C_r |       ( A_0/B_0 g_jk) ^r
         _n-1 C_r-1
    
    
      ≤
       g_jk^1/2 B_0^n ∑_k=1^N
        ( ∑_r=1^n |  _1/2 C_r | δ^r )
         ( ∑_r=1^n ε_0^r  _n-1 C_r-1) 
    
       
     = g_jk^1/2 B_0^n N
        { 
          1-(1-δ)^1/2}ε_0 ( 1 + ε_0 )^n-1.

Now taking A_1 = N g_jk^1/2{ 1-(1-δ)^1/2}ε_0
and B_1= (1+ε_0), we arrive at our statement.

From the above, we have 


Assume  (3.3) holds. Then, for n=1,2,…, we have


    U^(n)≤ A_2B_2^n-1  (n=1,2,…),

where the constants A_2,  B_2>0 depend on N and G.



Given (5.17), it is sufficient to estimate B^(n).
From the definition and Lemma 5.2, we have 


    B^(n)≤∑_j=1^N ∑_l=0^n
       ( A_1 B_1^l-1 ) ( A_1 B_1^n-l) 
     = A_1^2 B_1^n-1nN.

As n ≤ e^n   (n=1,2,…), we have
nB_1^n-1≤ e ( eB_1)^n-1, yielding the desired estimate.



Assume  (3.3) holds. Then, for n=1,2,…, we have


    T^(n)≤ A_3B_3^n-1  (n=1,2,…),

where the constants A_3,  B_3>0 depend on N and G.



Recalling Eq. (5.1) in Subsection 5.1, and following the discussions in Lemma 5.1, we obtain an estimate of the form:


    |I_τ(n)^(i,j)| ≤ A_4 B_4^n-1   (τ=1,3).

Likewise, we have 


    |
     ∑_r=1^k  _1/2 C_r/g_ij^r∑( ∏_τ=1^r g_jk^p_τ)
       |
        ≤
         A_5 B_5^k-1,   
    
    |
     ∑_r=1^n-k _1/2 C_r/g_ij^r∑( ∏_τ=1^r g_jk^p_τ)
       |
    
     ≤
     A_5 B_5^n-k-1,

from which we obtain


    |I_2(n)^(i,j)| ≤ 
     |t_ij| ∑_k=1^n-1 A_5^2B_5^n-2
    
      = | t_ij| (n-1) A_5^2 B_5^n-2.

As described in the proof of Lemma 5.3, this is estimated by A_5 B^n-1 with sufficiently large B.


Assume  (3.3) holds. Then, for n=1,2,…, we have 


    P̂_h^(n)≤ A_6 B_6^n-1  (h=1,2,… ,s),

where the constants A_6,  B_6>0 depend on N, elements of G, and the isolation distance of T.



From (5.20), we have 


    P̂_h^(n)≤1/2π∑_ν_1+ … + ν_p = n ν_1, …, ν_p ≥ 1∏_r=1^p  U^(ν_r)∫_Γ̂_hR̂ (ζ) ^p+1  dζ,

where Γ̂_h is introduced in (5.20), and the summation on the right-hand side is taken over all possible values of 
p ∈ N and (ν_1, …, ν_p) meeting the condition below the summation symbol. By the normality of U, we have


    R̂(ζ)  = 1/ dist (ζ, σ( U))  ∀ζ∈ P( U).

Note that in this case, the convergence radius r_h of the series (5.18) and (5.19) is lower-bounded by 


    r_h = ( 2A_2/d̂_h + B_2 )^-1,

where A_2 and B_2 are given in Lemma 5.3, and d̂_h is the isolation distance of μ_h. Taking Γ̂_h as a circle of radius d̂_h/2 surrounding μ_h, we have 
R̂(ζ)  = 2/d̂_h   ∀ζ∈Γ̂_h.

Then,


    ∫_Γ̂_hR̂(ζ) ^p+1≤πd̂_h ×( 2/d̂_h )^-(p+1)
        = 2^-(p+1)πd̂_h^-p.

Thus, we have 


    P̂_h^(n)≤ 
      B_2^n 2^-2∑_ν_1+ … + ν_p = l ν_1, …, ν_p ≥ 1( A_2/2B_2 d̂_h )^p

Note that, from the relationship
μ_h = λ_h ± i√( 1 - λ_h^2),
the isolation distance d_h is estimated from below
by that of the corresponding λ_h.
Now, let us consider the summation on the right-hand side. 

This sum is taken over all possible values of p and (ν_1, …, ν_p) meeting the condition below the summation symbol, meaning that p runs from 1 to l.

For fixed p   (1 ≤ p ≤ l), the number of sets (ν_1, …, ν_p) satisfying
ν_1+ … + ν_p = l and ν_1, …, ν_p ≥ 1 is 
_l-1 C_l-p. Thus, defining c_0 ≡( A_2/2B_2 d̂_h ), we have 


    B_2^n ∑_ν_1+ … + ν_p = l ν_1, …, ν_p ≥ 1 c_0^-p
     = (B_2/c_0)^n c_0^n 
       ∑_p=1^l  _n-1 C_n-p c_0^-p
    
       
     = (B_2/c_0)^n (1+c_0)^n-1,

leading to an estimate of the desired form.


The following lemma naturally follows by combining (5.26)–(5.27) and Lemma 5.5.


Assume  (3.3) holds. Then, for n=1,2,…, we have 


    Q^(n)≤ A_7 B_7^n-1,

where the constants A_7,   B_7>0 depend on N, elements of G, and the isolation distance of T.


As U is normal, P̂_h=1 for h=1,2,…,s. By virtue of
(5.26)–(5.27), we then have Q≤ s and


    Q^(n)≤∑_h=1^s [
       ∑_r_1=1^r (n-r_1+1)  P̂_h^(r_1)P̂_h^(n-r_1+1)
    
    
    
     +   (n+1) P̂_h^(n+1)]    (n=1,2,…).

From Lemma 5.5, we then have


    P̂_h^(r+1)≤ A_6 B_6^r, 
    
       P̂_h^(r_1)P̂_h^(r-r_1+1)≤ A_6 B_6^r_1-1× A_6B_6^r-r_1
     = A_6^2B_6^r-1    (r_1=1,2,…,r), 
    
       P̂_h^(r)P̂_h^(1)≤ A_6B_6^r-1× A_6 
     = A_6^2B_6^r-1,

and therefore


    Q^(n)≤∑_h=1^s
     [
        (n+1) A_6B_6^n  + A_6^2B_6^n-1
    
    
    + ∑_r_1=1^n-1 (n-r_1+1) A_6B_6^n-1],

leading to the desired estimate.

Lemma 5.7 below then follows from Lemma 5.6. 


Assume  (3.3) holds. Then, for n=1,2,…, we have 


    |μ^(n)⟩≤ A_8 B_8^n-1   (n=1,2,…),

where the constants A_0,  B_0>0 depend on N, elements of G, and the isolation distance of T.



From (5.28) and given that |μ⟩=1, it is sufficient to show that 


    V^(n)≤ A_9 B_9^n-1   (n=1,2,…).

The desired estimate is found by induction. Assuming V^(j)≤ A_9B_9^j-1 for j=2,3,4,…,n-1, and noting that
Q≤ s, we have


    V^(n)≤1/n{ s+ A_7A_9 ∑_j=2^n-2 B_7^j-1B_9^n-2-j}
    
       ≤ s + A_7A_9 ( B_7+B_9)^n-1.

Setting B̅ = max{1, ( B_7+B_9) }, we have 


    V^(n)≤ sB̅ + A_7A_9 B̅^n-1≤( s+ A_7A_9 ) B̅^n-1,

which is the desired estimate.  As |ν⟩=1, the estimate of |ν^(n)⟩ is the same as the above.




 §.§ Estimate of |N_q^(n) (i,m|ψ(0))|

We now estimate|N_q^(n)(i,m|ψ(0)) |forn=1,2,…. 



Assume  (3.3) holds. Then, for n=1,2,…, we have 


    | N_q^(n)(i,m|ψ(0)) | ≤ A_11B_11^n-1,

where the constants A_11,  B_11>0 depend on N, m, and on
elements and the isolation distance of G.



Recall the representation (5.29).
From Lemma 5.7, |ψ(0)⟩ = 1,
and given that |j,i⟩ forms an orthonormal basis in ℋ, we have


    | ⟨μ^(r_2) | ψ(0)|⟩| | ⟨j,i | μ^(n-r_1-r_2)|⟩| 
     ≤ A_8^2 B_8^n-r_1-2.


To estimate |μ^(n)|, we recall that 
μ^(n) = (  d/ dχ)^n μ(χ) |_χ=0
 = λ^(n)
   + 
     i/n!(  d/ dχ)^n 
 ( 1-(λ(χ))^2 )^1/2|_χ=0. 

We estimate the second term of the right-most equality in the above expression. By Eq. (5.8), Remark 5.1, and using r_0 in Subsection 5.5,
we have |λ^(p_j) | ≤ϱ_0 r_0^p_j  (j=1,2,…,r).
We also note that p_1^' ! … p_r^'^' ! ≥ 1. We then have 


    | ( 1-(λ(χ))^2 )^1/2| ≤  r_1^-n∑_r=1^n
    ϱ_1^r  _n-1C_r-1
    
    
    
      ∑_r^'=1^r
       2^r^' _r-1C_r^'-1|
         _1/2 C_r^'|
        ( 1-λ^2 )^-(2r^'-1)/2.


Letting
|λ |^2 < 1-ε_1,
and defining ε_1^-1 = δ_1 × (δ_1 ε_1)^-1 with some  
 δ_1 ∈ (0,1), we can write


|1-λ^2|^-r^' < δ_1^r^'  (δ_1 ε_1)^-r^'.

We then have


    ∑_r^'=1^r (2/(δ_1ε_1) )^r^' _r-1C_r^'-1|
         _1/2 C_r^'|
     
     δ_1^r^'
    
     ≤(
      ∑_r^'=1^r (2/(δ_1ε_1) )^r^' _r-1C_r^'-1)
     
     ( 
       ∑_r^'=1^r
       |
         _1/2 C_r^'|  δ_1^r^') 
    
       
     = (2/(δ_1ε_1) )
      {
       1+(2/(δ_1ε_1) )
      }^r-1{ 
       1 - ( 1-δ_1 )^1/2}
    
       ≡ A_12B_12^r.

From these expressions, we can estimate (5.35). We have 


    | ( 1-(λ(χ))^2 )^1/2| 
     ≤ 
     A_12
     r_1^-n∑_r=1^n
     (ϱ_1B_12)^r  _n-1C_r-1
    
       
     = A_12B_12
        r_1^-nϱ_1 
        ( 1 + ϱ_1 B_12)^n-1.

Combining this expression with the estimate of |λ^(n) |, we obtain
the estimate |μ^(n)| ≤ A_13B_13^n-1
with constants A_13,   B_13 > 0. Actually, recalling (5.31), and
noting that |μ|=1, we obtain


    |a_1(n;m)| ≤∑_r=1^min{2m,n} _2mC_r A_13^rB_13^n-r _n-1 C_n-r
    
       ≤ 
     B_13^n ( ∑_r=1^2m _2mC_r )
     ( ∑_r=1^n _n-1C_n-r( A_13/B_13)^r ) 
    
       
     =
     B_13^n 2^2m( A_13/B_13) 
     ( 1 + ( A_13/B_13) )^n-1,

which yields an estimate of the form 

|a_1(n;m)| ≤ A_14B_14^n-1
with constants A_14,   B_14 > 0.
Thus, we have 


    |N_q^(n)(i,m|ψ(0))| ≤∑_μ, j∑_0 ≤ r_1+r_2 ≤ n
        A_14 B_14^r_1-1 A_8^2 B_8^n-r_1-2
    
       ≤ n A_8^2 A_14 B_8^n-2 B_14^-1∑_r_1=0^n ( B_14/B_8 )^r_1
    
       ≤ nA_11B_14^n,

where A_11 = A_8^2A_14B_8^-2 / (B_14-B_8). Without losing generality, we assume that B_8 > B_14 and again assume a sufficiently large constant B_11>0
(in case B_8< B_14, we have a similar estimate).
The right-most-hand side in the above expression is then estimated from above by A_11B_11^n.


We now estimate|I_q^(n) (i,m|ψ(0))|.
By Lemma 5.8, we have|N_q(i,m|ψ(0)) | ≤A_11and|N_q^(l)(i,m|ψ(0)) | ≤A_11B_11^l-1   (l=1,2,…). Together with (5.32),
this gives


    |I_q^(n) (i,m | ψ(0)) | ≤{2B_11 + (n-1) }A_11^2B_11^n-2   (n ≥ 2).

Note that{ 2B_11 + (n-1) }^1/n-1 ≤∃c_0wherec_0is some 
positive constant. Actually, without loss of generality, we can assumeB_11>1and 


    log{ 2B_11 + (n-1) }^1/n-1  = 
     1/n-1log{ 2B_11 + (n-1) }.

However,log{ 2B_11 + (n-1) } ≤2B_11+n-2, meaning thatlog{ 2B_11 + (n-1) }^1/n-1 is bounded.
Accordingly,{ 2B_11 + (n-1) }^1/n-1is also bounded, which
 completes the proof of Theorem 4.1.



§ CONCLUSION

This paper discussed the sensitivity analysis of quantum PageRank proposed in
<cit.>. 
We analytically showed that perturbing the original Google matrix alters the temporal value of quantum PageRank. In addition, we found the lower limit of the convergence radius of the expansion of the perturbed PageRank. 
On the other hand, the temporally averaged value of quantum PageRank and its temporal limitation did not analytically depend on the perturbation in general. 
In future study, we will extend the definition of quantum PageRank and the sensitivity analysis to graph limits (called graphons). 



99
Aharonov_2001
D. Aharonov et al. (2001),
“Quantum walks on graphs,”
 In: Proceedings of ACM Symposium on Theory of Computation (STOC'01), July 2001, p. 50-59.

Ambainis_2004
 A. Ambainis, 
 “Quantum walk algorithm for element distinctness,”
 In Proc. of the 45th IEEE Symposium on Foundations of Computer Science (FOCS), 22-31 (2004).

Batkai_2017 
  A. Bátkai, M. K. Fijavž and A. Rhandi,
  “Positive Operator Semigroups : From Finite to Infinite Dimensions, ”
  Birkhäuser Basel, 2017.
  <DOI:10.1007/978-3-319-42813-0>

Brin_and_Page_1998
S. Brin and L. Page (1998),
“The Anatomy of a Large-Scale Hypertextual Web Search Engine,”
 In: Seventh International World-Wide Web Conference (WWW 1998), Brisbane, Australia, 1998.

Grover_1996
 L. K. Grover, 
 “A fast quantum mechanical algorithm for database search,”
 In Proc. of the 28th Annual ACM Symposium on the Theory of Computing (STOC), 212-219 (1996).

Honda_2018
 H. Honda,
 Revisiting the sensitivity analysis of Googlefs PageRank,
 IEICE Communications Express, 2018, Volume 7, Issue 12, Pages 444–449.

Kato_1980
 T. Kato,
  “Perturbation Theory for Linear Operators,”
 Springer, Berlin, 1980.

Knopp_1945
K. Knopp. (1945),
“Theory of functions (English translation), Part I,”
 Dover, New York.

Langville_2006 
 A. N. Langville and C. D. Meyer,  Google's PageRank and Beyond: The Science of Search Engine Rankings, Princeton University Press, Princeton, 2006.


McKiernan_1956
 M. McKiernan,
 On the nth derivative of composite functions,
 Amer. Math. Monthly, 1956, Volume 63, Pages 331–333.

Nielsen_2011
 M. A. Nielsen and I. L. Chuang (2011),
  “Quantum Computation and Quantum Information: 10th Anniversary Edition,”
    Cambridge University Press New York, 2011.

Paparo_2012
  G. D. Paparo and A. Martin-Delgado,
  “Google in a Quantum Network,”
  Nature scientific reports, 2012.

Szegedy_2004
 M. Szegedy, 
 “Quantum speed-up of Markov Chain based algorithm,”
 Proc. the 45th Annual IEEE Symp. Foundations of Computer Science, 32–41 (2004).



 
   

Watrous_2001
 J. Watrous, 
 “Quantum simulations of classical random walks and undirected graph connectivity,”
 Journal of Computer and System Sciences, vol.62, 374–391 (2001).