Xiwang CAO Keqin FENG Ying-Ying TAN

Abstract Recently,there are extensive studies on perfect state transfer(PST for short)on graphs due to their significant applications in quantum information processing and quantum computations.However,there is not any general characterization of graphs that have PST in literature.In this paper,the authors present a depiction on weighted abelian Cayley graphs having PST.They give a unified approach to describe the periodicity and the existence of PST on some specific graphs.

Keywords:Perfect state transfer,Cayley graph,Eigenvalues of a graph,Weighted graph,Random walk

1 Introduction

Throughout this paper,we use Z,Q,R and C to stand for the ring of integers,the field of rational numbers,the field of real numbers and the field of complex numbers,respectively.

A weighted graphΓis a triple system(V,E;α),where V={v1,···,vn}is a finite set,E is a subset of V×V,and α is a complex-valued function,called a weight function,on E.The adjacency matrix ofΓis defined as

The eigenvalues of A will be referred to as the eigenvalues or the spectra of the graphΓ.A graph is named an integral graph if all its eigenvalues are integers.

Suppose that G is a finite group.A weighted Cayley graphΓ=Cay(G;α)is just a triple system(G,E;α),where E⊆G×G and α is a complex-valued function such that the weight function,which is also denoted by α,satisfies

We assume that there is no edge from g to gh if α(h)is zero.If the value set of the weight function α is{0,1}and the support set of α,i.e.,S={g∈G|α(g)=1},generates G,then Γis a Cayley digraph,denoted by Cay(G,S).Particularly,if S is symmetric,i.e,S=S−1:={s−1|s∈S}and S does not contain the identity element of G,thenΓis an undirected graph and is the usual Cayley graph.All the graphs considered in this paper are simple graphs,i.e,undirected connected graphs without loops.

A continuous random walk onΓis determined by a family of matrices of the form M(t),indexed by the vertices ofΓand parameterized by a real positive time t.The(u,v)-entry of M(t)represents the probability of starting at vertex u and reaching vertex v at time t.Define a continuous random walk onΓby setting

For quantum computations,Fahri and Gutmann[10]proposed an analogue continuous quantum walk.For a connected simple graphΓwith adjacency matrix A,they define the transfer matrix ofΓas the following n×n matrix:

where n=|V|is the number of vertices inΓ.

Definition 1.1LetΓbe a graph.For u,v∈V,we say thatΓexhibits perfect state transfer(PST for short)from u to v at a time t(>0)if the(u,v)-entry of H(t),denoted by H(t)uv,has absolute value 1.Further,when|H(t)uu|=1,we say thatΓis periodic at u with period t.IfΓis periodic with period t at every point,thenΓis named periodic.

We say thatΓadmits PST if there are two vertices u and v such thatΓhas PST from u to v at some time t>0.

Since H(t)is a unitary matrix,if PST happens in the graph from u to v,then the entries in the u-th row and the entries in the v-th column of H(t)are all zero except for the(u,v)-th entry.That is,the probability starting from u to v is absolutely 1,which is an idea model of state transferring.In other words,quantum walks on finite graphs provide useful simple models for quantum state transport.This phenomenon was first discovered by Bose[4]and was applied to spin chains for communication links in quantum computing.Some new quantum algorithmic computing techniques in this aspect were provided by Childs[7]and Farhi et al[10]around the same time.These algorithms are remarkable since they provably beat the corresponding classical resource bounds.For more background of applications of PST,we refer the readers to[4,9]and the references therein.

Quantum walks on weighted graphs have been proposed as an efficient way to transfer quantum states(and therefore quantum information)with perfect fidelity without requiring external control(see[8]).Casaccino et al.[5]noticed that it is possible to achieve PST by using suitable energy shifts(by adding weighted self-loops)on two vertices of complete graphs,or on complete graphs with a missing link(even though there is no PST in certain unweighted cases).

In a previous paper[18],we presented a characterization on connected simple Cayley graphs Γ=Cay(G,S)having PST.We gave a unified interpretation of many previously known results.We provided several new results including the answers to the questions raised in[2,11–12].

However,even though there are a lot of researches on PST,there is no general characterization on graphs which exhibit PST in literature.In this paper,we extend the results in[18]to weighted abelian Cayley graphs.We give a unified characterization of weighted abelian Cayley graphs having PST.Since weighted graphs and Cayley graphs are special kinds of weighted Cayley graphs,we can use our main results(Theorems 2.1–2.2)to explain many prior results on the existence of PST on circulant graphs(the underlying group is a cyclic group)and cubelike graphs(the underlying group is the addition group of a finite field of characteristic two).In[18],we proved that ifΓ=Cay(G,S)is a connected simple abelian Cayley graph with 4<|G|≡2(mod 4),then G cannot have PST between two distinct vertices.As an application of Theorem 2.2,we show that the same conclusion holds for integral weighted abelian Cayley graphs under certain conditions(Theorem 2.4).Conversely,if we assign the weight function properly,then we can get a connected simple weighted graphΓ=Cay(G;α)having PST even if the order of G is not doubly even(Theorem 2.5).We provide a lower bound on the minimum time t at which a weighted Cayley graph has PST between two distinct vertices(Theorem 3.1)and show that this bound is tight(Theorem 3.2).

2 A Characterization on Weighted Abelian Cayley Graphs Having PST

Note that in this paper,from now on,all the groups are abelian(additive)and the identity element of the concerned group is denoted as 0.“gcd(···)”stands for the greatest common divisor of some integers.In order to compute the transfer matrix of the weighted Cayley graph,we need to diagonalize the adjacency matrix A.Before doing that,we need some preliminaries on the dual group of an abelian group.Assume that an abelian group G has the following decomposition

where Zm=(Z/mZ,+)is a cyclic group of order m.For every x=(x1,···,xr)∈G,the mapping

is a character of G,where ωns=is a primitive ns-th root of unity in C.Obviously,we have χx(g)=χg(x)for all x,g∈G.

For spectrum of the weighted Cayley graphΓ=Cay(G;α),we have the following result.

Lemma 2.1(see[15])Let G be an abelian group of order n and{λg|g∈G}be the set of spectra of the weighted Cayley graphΓ=Cay(G;α).Then we have

Consider the following n×n matrix

By the orthogonal relation of characters,we know that P is a unitary matrix,i.e.,PP*=In=P*P,where P*means the conjugate transpose of P.

Let D be the following diagonal matrix

where δg,h=1 if g=h and 0 otherwise.Let A be the adjacency matrix ofΓ=Cay(G;α)and let AP=(ηg,h),PD=(νg,h).Then for every g,h∈G,

Note that the last equality follows from Lemma 2.1.Moreover,

Thus P*AP=D and

H(t)=exp(ıtA)=P exp(−ıtD)P*=P·diag(exp(−ıtλg):g∈G)·P*=(Hg,h(t))g,h∈G,where

where a=g−h.Therefore,

Lemma 2.2Let G be an abelian group and{λg|g∈G}be the set of spectra of the weighted Cayley graphΓ=Cay(G;α).Assume that for every z∈G,=α(−z).For g,h∈G,let a=g−h.Then the following statements are equivalent:

(1)Γhas PST between vertices g and h at time t>0;

As a consequence,we have the following simple corollaries.

Corollary 2.1Let G be an abelian group of order n.Let α be a weight function satisfying=α(−z)for every z∈G andΓ=Cay(G;α)be the corresponding weighted abelian Cayley graph.Then for g,h∈G,Γhas PST between g and h if and only ifΓhas PST between g+z and h+z for all z∈G.

ProofIt follows directly from Lemma 2.2(2).

Corollary 2.2Let G be an abelian group of order n andΓ=Cay(G;α)be a weighted abelian Cayley graph with the weight function satisfying=α(−z)for every z∈G.Let Γ′=Γ′(G;α′)be another weighted graph,where the weight function α′is defined by α′(z)=α(z)+s for all z∈G,s is a real number.Suppose thatThen for g,h∈G,the following statements are equivalent:

(1)Γhas PST between g and h at time t>0;

(2)Γ′has PST between g and h at time t>0.

ProofAssume thatΓhas PST between g and h at a time t>0.Then by Lemma 2.2(2),for any x(0)∈G,χa(x)=exp(ıt(λ0−λx)),where a=g−h.Now,α(−z)+s=α′(−z)for all z∈G and

and

Thus

By Lemma 2.2(2)again,Γ′has PST between g and h at time t.By symmetry,the stated equivalence follows.This completes the proof.

Moreover,we have the following result on weighted abelain Cayley graphs having PST.

Proposition 2.1LetΓ=Cay(G;α)be a weighted abelian Cayley graph withα(−z)∈Z for every z∈G and n=|G|≥3.Assume thatΓhas PST between a pair(g,h)of vertices.Then

(1)Γis an integral graph.Namely,λx∈Z for all x∈G.

Proof(1)Suppose thatΓhas PST between g and h∈G.By Lemma 2.2,the equality

holds for every x∈G.Let m be the order of a=g−h∈G.Since aχagives an isomorphism of G andthe order of χais also m.Thus we can write

Then the condition(2)of Lemma 2.2 becomes

Denote t=2πT.From(2.1),we get

and

Now,we consider λ−x.By(1),λx∈Z,thus

and

Thus,ia(−x)≡−ia(x)(mod m).By(2.3),we have

Combining(2.3)and(2.4)together,we haveSince gcd(ia(x),m)=1,we get that m=2.

Next,we discuss the periodicity of a simple weighted ableian Cayley graphΓ=Cay(G;α).By Corollary 2.2,we may assume that α(g)≥0 for all g∈G.In order to get integral graphs,we need further assume that α(z)∈Z for all z∈G.Based on these assumptions,we can state the following result.

Theorem 2.1Let G be a finite abelian group.Let α be a function on G satisfying 0≤α(z)=α(−z)∈Z for all z∈G.LetΓ=Cay(G;α)be the corresponding weighted abelian Cayley graph.Let λ0and···,λn−1be the eigenvalues ofΓand n(≥3)be the order of G.IfΓ is an integral graph,then for every g∈G,Γis periodic at vertex g and the set

ProofFirstly,sinceΓis integral,the number N=gcd(λ0−λx:0x∈G)is well-defined.Secondly,from the proof of Proposition 2.1,we know thatΓhas PST at the vertex g if and only if

Now,we consider those integral weighted abelian Cayley graphs which admit PST between two distinct vertices g and h.Denote a=g−h.By Proposition 2.1,the order of a is two and so is the order of χa.Therefore for every x∈G,we have χa(x)=±1.Define two subsets of G by

It is easy to see that Ω+is a subgroup of G and G is a disjoint union of Ω+and Ω−.MoreoverDenote

Obviously,N0and N1are well-defined and N=gcd(λ0−λx:0x∈G)=gcd(N0,N1).

Recall that the 2-adic exponential valuation of rational numbers is defined by

The evaluation v2has the following properties.For β,β′∈Q,

(P1)v2(ββ′)=v2(β)+v2(β′);

(P2)v2(β+β′)≥min(v2(β),v2(β′)),and equality holds if v2(β)v2(β′).

After the above preparation,we present our main result as follows.

Theorem 2.2Let G be an abelian group of order n and α be a function on G satisfying α(z)=α(−z)∈Z for all z∈G.Assume thatΓ=Cay(G;α)is the associated Cayley graph.Then for g,h∈G,a=g−h0,Γhas PST between g and h if and only if the following three conditions hold:

(1)Γis an integral graph,i.e.,the eigenvalues ofΓare all integers;

(2)the order of a is two;

(3)for all x∈Ω−,the 2-adic valuations of the numbers λ0−λxare equal,say ρ,and v2(N0)≥ρ+1,where N0is defined by(2.6).

Moreover,if the conditions(1)–(3)are satisfied,then the set

ProofConditions(1),(2)follow directly from Proposition 2.1.ThusΓhas PST between g and h at the time t:=2πT if and only if the following two conditions hold:

Next,we present an example to illustrate our results.

Example 2.1Let G=Z/6Z be a cyclic group of order 6 and the weight function is defined by α(0)=α(3)=0,α(1)=α(5)=1,α(2)=α(4)=2.LetΓ=Cay(G;α)be the corresponding weighted Cayley graph.Then the adjacency matrix ofΓis

The eigenvalues of A are

A direct computation shows that the transfer matrix H(t)=(hij(t))1≤i,j≤6satisfies

and

The other entries(except for hii(t),i=1,···,6 and hi,i+3(t),hi+3,i(t),i=1,2,3)have the form(exp(6tı)+s1exp(−tı)+s2exp(−3tı)+s3exp(2tı)),where s1,s2,s3∈{−1,1},and thus their absolute value are less than 1 for every real number t.ThusΓcannot have PST between vertices g and h when g−h.ButΓis periodic at any vertex g∈G.These results are consistent with Theorem 2.2.Indeed,x∈Ω−if and only if x∈{1,3,5}.Now,v2(λ0−λ1)=0,v2(λ0−λ3)=2.Thus the condition(3)in Theorem 2.2 does not hold and thusΓcannot have PST between vertices g and h when g−h.

In view of Theorem 2.2,we need to investigate integral weighted abelian Cayley graphs.Note that,for abelian Cayley graph,this topic has been discussed by many authors,see for example[1,11,13,19]and the references therein.

We consider integral weighted abelian Cayley graphΓ=Cay(G;α)with the weight function α satisfying α(z)=α(−z)∈Z for all z∈G.Let e=exp(G)be the least common multiple of the order of the elements in G.Since the eigenvalues ofΓ=Γ(G;α)are{λx:x∈G},they are contained in the cyclotomic field Q(ωe),here ωeis a primitive e-th root of unity in C.It is well-known that Q(ωe)/Q is a Galois extension and the Galois group of this extension is

Meanwhile,

Thus,λx∈Z for all x∈G if and only iff or allℓ∈Z with gcd(ℓ,e)=1 and all x∈G.By the orthogonality of characters,λx∈Z for all x∈G if and only if α(ℓg)=α(g)for all g∈G andℓ∈Z with gcd(ℓ,e)=1.

We define an equivalent relation“～”on G by setting g～h if and only if there exists an elementℓ∈such that g=ℓh.The equivalent class containing g is denoted by[g].A function f is called a c-function if it is a constant on each equivalent class.That is,if f is a c-function,and g～h,then f(g)=f(h).Using this notation,we have the following result.

Theorem 2.3Assume thatΓ=Cay(G;α)is a weighted abelian Cayley graph,where the weight function α satisfies α(z)=α(−z)∈Z for all z∈G.Then the following statements are equivalent:

(2)λx=λℓxfor all x∈G andℓ∈,that is,λxis a c-function defined on G;

(3)α(g)=α(ℓg)for all g∈G andℓ∈,that is,α(g)is a c-function defined on G.

We note that,whenΓis an abelian Cayley graph Cay(G;S),then Theorem 2.3 is reduced to the following result obtained independently by Bridge[3]and Klotz[14].

Corollary 2.3(see[3,14])Let G be a finite abelian group,S⊆G.Then the Cayley graph Γ=Cay(G;S)is integral if and only if S is a disjoint union of several equivalent classes of G.

We have shown that if a weighted abelian Cayley graphΓ=Cay(G;α)has PST between two distinct vertices g and g+a in G,then the order of a should be two and then the order of G is even.For integral circulant Cayley graphs Cay(G,S)having PST,Petkovic[17]proved that the order of G should be doubly even,i.e.,4||G|.In[18],we proved that ifΓ=Cay(G,S)is a connected simple abelian Cayley graph with 4≤|G|≡2(mod 4),then G cannot have PST between two distinct vertices.In other words,we generalized Petkovic’s result(see[17])to abelian Cayley graphs.As another application of Theorem 2.2,we can show that the same conclusion holds for integral weighted abelian Cayley graphs under certain conditions.Conversely,if we assign the weight function suitably,then we can get a simple weighted graphΓ=Cay(G;α)having PST even if the order of G is not doubly even.

Theorem 2.4LetΓ=Γ(G;α)be a connected weighted integral abelian Cayley(simple)graph and 4

ProofWe use Theorem 2.2 to prove this result.Since 4

Thus,by(2.5),we know that

By Theorems 2.2–2.3,we can obtain v2(λx−λy)=ρ for all x∈Ω+,y∈Ω−and the weight function α is a class function.Letting x=(0,h)∈Ω+,y=(1,h)∈Ω−,we get

and

Therefore,we have

and

Particularly,taking h=0,we get

Since a=(1,0)is the unique element in Ω−whose equivalent class has odd size(if z∈Ω−,then the size of[z]is ϕ(ord(z)),here ϕ is the Euler phi-function).Since Ω−is a union of some equivalent classes,we obtain that|Ω−|is odd.Moreover,α is a c-function on G,we know that(mod 2).We define a function f on H as follows:

The Fourier transformation of f(z)is

By inverse Fourier transformation,

By Theorem 2.2,for any x=(0,h)∈Ω+,y=(1,h)∈Ω−,we have v2(λ0−λx)≥ρ+1,v2(λ0−λy)=ρ.By Property(P2),it follows that

Thus

Therefore,

We define a function g on H as follows:

The Fourier transformation of g(z)is

By inverse Fourier transformation again,

SinceΓis a simple graph,α((0,0))=0,we get that λ0≡2ρ−1(mod 2ρ).

Combining(2.8)and(2.10),we get

Thus we get a contradiction with the assumption that there exists an element g∈G such that v2(α(g))≤v2(a).

For the converse of Theorem 2.4,we show that for some abelian groups of order 2m with odd integer m,there exists a weight function α such thatΓ=Cay(G;α)has PST.More specifically,we have the following result.

Theorem 2.5Let G=(Z2m,+)be an abelian group,where m>1 is an odd integer.Let Γ=Γ(G;α)be a weighted(simple)graph,where the weight function α is defined by α(0)=0,α(m)=1,α(g)=2 for all g∈G and g0,m.Then for every g∈G,Γhas PST between g and g+m at time

ProofSince G is in fact a cyclic group,the dual group of G is also cyclic.By Lemma 2.1,a direct calculation shows that the eigenvalues ofΓare

And it is easy to see that

Therefore,

By Theorem 2.2,we know thatΓhas PST between two distinct vertices at time

For the graph in the Example 2.1,if we change the weight function according to Theorem 2.5,then we get the following weighted graph which has PST.

Example 2.2Let G=Z/6Z be a cyclic group of order 6 and the weight function is defined by α(0)=0,α(3)=1,α(1)=α(5)=α(2)=α(4)=2.LetΓ=Cay(G;α)be the corresponding weighted Cayley graph.Then the adjacency matrix ofΓis

The eigenvalues of A are

Note that

and

By Theorem 2.2,there exists PST between g and g+3 for every g∈G.Indeed,let P=where γij=Then P is a unitary matrix and

A direct computation shows that the transfer matrix H(t)=(hij(t))1≤i,j≤6satisfies

In[18],we showed that ifΓ=Cay(G,S)is a cubelike abelian Cayley graph with|S|≥1,then N=gcd(λ0−λx,x∈G)is a power of two.Next,we show that this result can be extended to weighted Cayley graphs.We believe that the following result has its own independent interest in graph theory.

Lemma 2.3Let G be an abelian group and α be a weight function from G to Z.Assume that gcd(α(z):z∈G)=1 and letΓ=Cay(G;α)be a simple weighted Cayley graph.Then N=gcd(λ0−λx,x∈G)is a divisor of|G|.Consequently,if G is a p-group,then N is a power of p.

ProofBy definition,we know that for any x∈G,N|(λ0−λx).Assume that λx=λ0−Nθ(x),θ(x)∈Z.Noticing that

is the Fourier transform of α(z),by the inverse transform formula,we get

Due to gcd(α(z):z∈G)=1,there exist|G|integersℓ(z),z∈G such thatFrom(2.11),we get

The right hand side of(2.12)is an algebraic integer,and the left hand side of(2.12)is a rational number.Thus both of them are integers.This completes the proof.

The following corollary follows immediately.

Corollary 2.4Suppose thatΓ=Cay(G,S)is an integral abelian Cayley graph with|S|=s and λ0(=s),λ1,···,λrare the eigenvalues ofΓ.Then N=gcd(s−λi:1≤i≤r)is a divisor of|G|.

3 PST on Weighted Cubelike Cayley Graphs

In this section,we let G be the additive group of the finite field Fq,where q=2n.Let α be a weight function from G to Z.We can view Fqas an n-dimensional vector space over F2.There are two ways to represent the additive characters of Fq.The first one is

in which x·z is the usual inner product of x,z∈.The second one is

here tr(·)is the trace mapping.

In 2012,Godsil[12]raised a question:Are there some cubelike graphs that have PST at time t,which can be arbitrarily small?In 2013,Chan[6]gave a confirmative answer to this question by presenting some deterministic constructions of such graphs.She utilized some Hamming schemes to get an infinite family of graphs having PST at an arbitrarily small time.In this section,we also give positive answers to the above mentioned question.By Theorems 2.1–2.2,the minimum time t of PST in cubelike graphΓ=Cay(G,α)iswhere N=gcd(λ0−λz:z(0)∈G).Firstly,we know that N should be a power of 2(see Lemma 2.3).Then we provide a lower bound on the time t such thatΓ=Cay(G,α)has PST between two distinct vertices(see Theorem 3.1)and show that this lower bound is tight(see Theorem 3.2).

First of all,we have the following two lemmas.

Lemma 3.1Let G=(Fq,+)be the additive group of Fq,q=2nandΓ=Cay(G;α)be a weighted abelian Cayley graph with α(z)∈Z for every z∈G.Let c∈andΓ′=Γ′(G;α′)be another weighted graph,where the weight function α′is defined by α′(z)=α(cz)for all z∈G.Then the following statements are equivalent:

(1)Γhas PST between g and h at time t>0;

(2)Γ′has PST between c−1g and c−1h at time t>0.

ProofIt is easy to see that the spectrum ofΓ′is

Thus by Lemma 2.2,Γ′has PST between c−1g and c−1h at time t>0 if and only if for all x∈G,it holds that

where

if and only if

if and only ifΓhas PST between g and h at the time t>0.

Lemma 3.2Let G=(Fq,+)be the additive group of Fq,q=2nandΓ=Cay(G;α)be a weighted abelian Cayley graph with α(z)∈Z for every z∈G.Assume that gcd(α(z):z∈G)=d and letΓ′=Cay(G;α′)be a cubelike weighted Cayley graph,where the weight function α′is defined byThen the following statements are equivalent:

(1)Γhas PST between g and h at time t>0;

(2)Γ′has PST between g and h at time dt>0.

The proof of Lemma 3.2 is straightforward and thus is omitted.Thus,without loss of generality,we assume that gcd(α(z):z∈G)=1 in the following context.

ProofWithout loss of generality,we can assume that a=(1,0,···,0)∈by Lemma 3.1.In this case,we can find that(see(2.5))

IfΓhas PST between g and g+a,then by Theorem 2.2,there is a nonnegative integer ρ such that v2(λ0−λy)=ρ for all y∈Ω−and v2(λ0−λx)≥ρ+1 for all x∈Ω+.Therefore min(v2(λ0−λz),z∈G)=ρ.By Lemma 2.3,we have 2ℓ=N=2ρand thus ρ=ℓ.By Theorems 2.2–2.3,we obtain that v2(λx−λy)=ρ for all x∈Ω+,y∈Ω−.Taking x=(0,h)∈Ω+and y=(1,h)∈Ω−,we get

and

Thus there exists an odd integer θ(h)such that

By the inverse formula,we have

Therefore,

Thus

Remark 3.1WhenΓis a cubelike Cayley graph,then the parameter M in Theorem 3.1 is 1,and then we haveℓ=In[18],we provided some graphs which exhibit PST at the time meeting the lower bound in Theorem 3.1 when n is even.This means that the upper bound forℓin Theorem 3.1 is tight.

In what follows,we present a result which shows that the upper bound forℓin Theorem 3.1 is also tight when n is odd.Before doing that,we need some preparations.

Definition 3.1Let n be a positive integer,f:→F2be a Boolean function.The Walsh transformation of f is Wf:→Z defined by

LetΓ=Cay(G;α)be the cubelike weighted Cayley graph associated with the weight function α.Then

Proof(1)SinceΓis a complete graph,it is obviously connected.

(2)By(2.5),it is easy to see that

For x=(0,x′)∈Ω+,y=(1,y′)∈Ω−,we have

Particularly,λ0=−1.Meanwhile,

Since f is a bent function,Wf(y′)=±2m,thus we get that

By Theorem 2.2 and Lemma 2.3,we can get the result in the item(2).

(3)It is a direct consequence of Theorem 2.1.

AcknowledgementThe authors would like to express their grateful thankfulness to the editor for his/her valuable comments and suggestions which improve the quality and presentation of this paper.