betaFeedback

WorksMathematics

Peak state transfer in trees and the cost of distance

Abstract

There is peak state transfer between vertices uu and vv in a graph GG if there exists a time tt for which ∣(eitM)u,v∣|(\mathrm{e}^{\mathrm i t M})_{u,v}| saturates the triangle inequality imposed by its spectral decomposition and MM is either the adjacency or Laplacian matrix. We show that peak state transfer at distance dd requires d324(1+o(1))\frac{d^3}{24}(1 + o(1)) edges in the adjacency case, Ω(d2)Ω(d^2) edges in the Laplacian case, and that the leading coefficient in the former is tight. We find a family of graphs with Laplacian peak state transfer at distance dd and Θ(d5)Θ(d^5) edges, showing that peak state transfer is achievable in a polynomial graph size. In contrast, Laplacian perfect state transfer costs at least Ω(2d/2)Ω(2^{d/2}) edges when the distance partition of vertices around one vertex is almost equitable. Finally, we show that Laplacian peak state transfer in trees requires Ω(d!)Ω(d!) edges, and we characterize all trees of diameter ≤4\leq 4 admitting Laplacian peak state transfer, thus answering a pair of questions posed by Coutinho, Guo, and Schmeits.

Introduction

As quantum computers advance in sophistication and performance, there is an increasing need to optimize protocols for quantum computational tasks. Among the simplest computational tasks is the transmission of information from one register to some other, which can be achieved by teleportation, for example. The simplest quantum algorithm is to simply wait, and it is desirable for the most frequently applied operation to be one achieved by the simplest algorithm. To that end, we consider the problem of moving a state across a quantum architecture by time evolution alone.

If registers in the quantum computer are spin-1/2 particles (qubits) interacting with neighbors by Heisenberg interactions, time evolution moves a lone excitation across the quantum computer according to a hopping model on the graph with a vertex for each qubit and an edge for each interaction term [1]. In particular, the Laplacian or adjacency matrices govern the dynamics of single excitations, taking the role of a generator of time translation. Hence, we are faced with a problem of graph theory. How can we construct graphs for which ∣(eitM)u,v∣=1\lvert(e^{itM})_{u,v}\rvert= 1 at some known time tt for MM either the adjacency or Laplacian matrix of a graph? This problem is called perfect state transfer [2].

Let LL be the Laplacian matrix of a connected graph GG, with spectral decomposition L=∑θ∈spec⁡(L)θEθL = \sum_{\theta\in\operatorname{spec}(L)} \theta E_\theta over distinct eigenvalues θ\theta. Following [3], the bounding matrix is BL:=∑θ∈spec⁡(L)∣Eθ∣B_L := \sum_{\theta\in\operatorname{spec}(L)} \lvert E_\theta\rvert where ∣⋅∣\lvert\cdot\rvert denotes entrywise absolute values. By the triangle inequality, ∣(eitL)u,v∣≤(BL)u,v\lvert(e^{itL})_{u,v}\rvert\le(B_L)_{u,v} for all times tt. If there exists some time for which the inequality is saturated for some pair of vertices uu and vv, we say that there is Laplacian peak state transfer between uu and vv. We may likewise define adjacency peak state transfer.

If (BM)u,v=1(B_M)_{u,v} = 1, we say that uu and vv are strongly cospectral. Perfect state transfer is exactly equivalent to peak state transfer between strongly cospectral vertices. As such, peak state transfer is a natural relaxation of perfect in that the transfer amplitude may be bounded away from one in exchange for an exactly computable transfer time. Coutinho, Guo, and Schmeits [3] establish lower bounds on qubit transfer fidelity in terms of (BL)u,v(B_L)_{u,v} alone, motivating several optimization problems over graphs.

As our motivation is the construction of quantum wires, we recognize it is desirable to construct graphs with favorable transfer properties that have the smallest possible number of edges and vertices. In the case of perfect state transfer, there are no known families of graphs admitting perfect state transfer with a number of edges only polynomial in the transfer distance. Although the best known bound requires only a polynomial number of edges [4], it is natural to ask whether peak state transfer is accompanied by its own unavoidable cost. To that end, Coutinho, Guo, and Schmeits again posed:

Problem 1.1 (of Coutinho, Guo, and Schmeits [3]). If GG admits peak state transfer between uu and vv at distance dd and has mm edges, find a bound for mm in terms of dd.

We provide m=Ω(d2)m = \Omega(d^2) in the Laplacian peak state transfer case, and furnish a family of graphs with m=Θ(d5)m = \Theta(d^5), thereby showing that Laplacian peak state transfer at arbitrary distance is achievable with only a polynomial number of edges. This construction improves upon the best known examples, which have m=Ω(ed)m = \Omega(e^d). Furthermore, we show that Laplacian perfect state transfer across the diameter of a graph between vertices whose distance partitions are equitable requires m=Ω(2⌊d2/2⌋)m = \Omega(2^{\lfloor d^2/2\rfloor}) edges, and the aforementioned family of examples shows that Laplacian peak state transfer does not; thus exhibiting an exponential separation between peak and perfect state transfer, albeit in a setting with additional assumptions.

In the case of adjacency peak state transfer, we show m≥124(d3+o(1))=Ω(d3)m \ge\frac{1}{24}(d^3 + o(1)) = \Omega(d^3). The latter bound is tight to leading order in dd including its prefactor, which is provided by a family of graphs exhibited by Coutinho, Guo, and Schmeits in [3]. Specializing the Laplacian edge bound to the case of trees, we find that Laplacian peak state transfer in trees is, in fact, incompatible with only a polynomial number of edges. In particular, we find that m=Ω(d!)m = \Omega(d!).

Trees with at least three vertices are incompatible with Laplacian perfect state transfer and adjacency perfect state transfer never occurs in a tree with at least four vertices [5, 6]. In contrast, [3] show that no such theorem can apply in the case of Laplacian peak state transfer. For example, the star graphs K1,n−1K_{1,n-1} have nn vertices and generally admit Laplacian peak state transfer. [3] also found a single non-star tree with 10 vertices admitting Laplacian peak state transfer, and they posed the problem:

Problem 1.2 (of Coutinho, Guo, and Schmeits [3]). Determine whether there are infinitely many trees, not isomorphic to the star graph, that admit Laplacian peak state transfer.

We resolve this problem with a full classification of trees with diameter at most four that admit Laplacian peak state transfer, and we find that there are indeed infinitely many non-star trees admitting Laplacian peak state transfer. In particular, there is a single two-parameter family of balanced trees with diameter four that admit Laplacian peak state transfer, and we prove that the two-parameter family together with the stars are exhaustive. However, Laplacian peak state transfer in trees does not generally require balance, as we construct an infinite family of unbalanced trees of diameter six exhibiting peak state transfer.

Preliminaries

For a matrix MM, we write θ∈spec⁡(M)\theta\in\operatorname{spec}(M) to mean that ker⁡(M−θI)\ker(M-\theta I) is nontrivial. When the sorted order of eigenvalues is important, we index eigenvalues by their sorted order as θ1≤θ2≤⋯\theta_1 \le\theta_2 \le\cdots, and otherwise omit the subscript. We write (M)i,j(M)_{i,j} to mean the entries of MM.

We recall definitions from [3], which will be necessary throughout. For a symmetric matrix M=∑θ∈spec⁡(M)θEθM=\sum_{\theta\in\operatorname{spec}(M)}\theta E_\theta with spectral idempotents EθE_\theta, the positive and negative mutual eigenvalue supports are

ev⁡M+(u,v)={θ∈spec⁡(M):(Eθ)u,v>0}\operatorname{ev}^{+}_{M}(u,v)=\{\theta\in\operatorname{spec}(M):(E_\theta)_{u,v}>0\}
ev⁡M−(u,v)={θ∈spec⁡(M):(Eθ)u,v<0}.\operatorname{ev}^{-}_{M}(u,v)=\{\theta\in\operatorname{spec}(M):(E_\theta)_{u,v}<0\}.

and ev⁡M(u,v)=ev⁡M+(u,v)∪ev⁡M−(u,v)\operatorname{ev}_{M}(u,v)=\operatorname{ev}^{+}_{M}(u,v)\cup\operatorname{ev}^{-}_{M}(u,v). Likewise, we write ev⁡M(u):=⋃w≠uev⁡M(u,w)\operatorname{ev}_{M}(u):=\bigcup_{w\ne u}\operatorname{ev}_{M}(u,w). (M,u,v)(M,u,v) is eligible if ev⁡M(u,v)\operatorname{ev}_{M}(u,v) consists of algebraic integers and is closed under algebraic conjugation. If MM is either the Laplacian or adjacency matrix of a graph and uu and vv are vertices of that graph, then (M,u,v)(M,u,v) is eligible.

For real time tt,

∣(eitM)u,v∣≤∑θ∈spec⁡(M)∣eitθ(Eθ)u,v∣=∑θ∈spec⁡(M)∣(Eθ)u,v∣.(1)\left|(\mathrm{e}^{\mathrm{i}tM})_{u,v}\right|\le\sum_{\theta\in\operatorname{spec}(M)}\left|\mathrm{e}^{\mathrm{i}t\theta}(E_\theta)_{u,v}\right|=\sum_{\theta\in\operatorname{spec}(M)}\left|(E_\theta)_{u,v}\right|. \tag*{(1)}

by the triangle inequality. We define (BM)u,v=∑θ∈spec⁡(M)∣(Eθ)u,v∣(B_M)_{u,v}=\sum_{\theta\in\operatorname{spec}(M)}\left|(E_\theta)_{u,v}\right| and say that there is peak state transfer between uu and vv with respect to MM if there exists a time tt at which ∣(eitM)u,v∣=(BM)u,v\left|(\mathrm{e}^{\mathrm{i}tM})_{u,v}\right|=(B_M)_{u,v} or equivalently when (1) is saturated.

We recall a helpful fact about resolvent matrices.

Lemma 2.1. Let MM be a symmetric matrix with spectral idempotents EμE_\mu. As rational functions,

[(M−θI)−1]i,j=∑μ∈spec⁡(M)(Eμ)i,jμ−θ.\left[(M-\theta I)^{-1}\right]_{i,j}=\sum_{\mu\in\operatorname{spec}(M)}\frac{(E_\mu)_{i,j}}{\mu-\theta}.

In particular, [(M−θI)−1]i,j[(M-\theta I)^{-1}]_{i,j} has only simple poles, its pole set is exactly ev⁡M(i,j)\operatorname{ev}_{M}(i,j), and

(Eμ)i,j=lim⁡θ→μ(μ−θ)[(M−θI)−1]i,j.(E_{\mu})_{i,j}=\lim_{\theta\to\mu}(\mu-\theta)[(M-\theta I)^{-1}]_{i,j}.

If the entry is written in lowest terms as p(θ)/q(θ)p(\theta)/q(\theta), then (Eμ)i,j=−p(μ)/q′(μ)(E_{\mu})_{i,j}=-p(\mu)/q'(\mu).

A pair of results of Coutinho, Guo, and Schmeits relate the admission of peak state transfer to the arithmetic of the spectrum of MM, which we will use repeatedly.

Theorem 2.2 (Coutinho-Guo-Schmeits [3] Theorem 5.3). Let MM be a symmetric n×nn\times n matrix and let u≠vu\ne v be vertices with (M,u,v)(M,u,v) eligible and ev⁡M(u,v)\operatorname{ev}_{M}(u,v) nonempty. There is peak state transfer between uu and vv with respect to MM if and only if:

(i) every eigenvalue in ev⁡M(u,v)\operatorname{ev}_{M}(u,v) is a quadratic integer: there exist a squarefree integer D≥1D\ge1, an integer aa, and for each θr∈ev⁡(u,v)\theta_r\in\operatorname{ev}(u,v) an integer brb_r of the same parity as aa, such that

θr=12(a+brD);\theta_r=\frac{1}{2}(a+b_r\sqrt{D});

(ii) fixing θs∈ev⁡+(u,v)\theta_s\in\operatorname{ev}^{+}(u,v) and setting

cr:=θs−θrD=bs−br2,g=gcd⁡{cr:θr∈ev⁡(u,v)},c_r:=\frac{\theta_s-\theta_r}{\sqrt{D}}=\frac{b_s-b_r}{2},\qquad g=\gcd\{c_r:\theta_r\in\operatorname{ev}(u,v)\},

cr/gc_r/g is even if and only if θr∈ev⁡+(u,v)\theta_r\in\operatorname{ev}^{+}(u,v), and odd if and only if θr∈ev⁡−(u,v)\theta_r\in\operatorname{ev}^{-}(u,v).

If these hold, peak state transfer occurs precisely at all odd multiples of t0=π/(gD)t_0=\pi/(g\sqrt{D}), with phase factor eitθse^{it\theta_s}.

The specialization of Theorem 2.2 to the case of Laplacians is particularly useful for us.

Corollary 2.3 (Coutinho-Guo-Schmeits [3] Corollary 5.4). Let LL be the Laplacian matrix of a connected graph GG. There is peak state transfer between distinct vertices uu and vv with respect to LL if and only if:

(i) every θr∈ev⁡L(u,v)\theta_r\in\operatorname{ev}_{L}(u,v) is an integer

(ii) with g=gcd⁡(ev⁡L(u,v))g=\gcd(\operatorname{ev}_{L}(u,v)), for all θr∈ev⁡L(u,v)\theta_r\in\operatorname{ev}_{L}(u,v): θr/g\theta_r/g is even if and only if θr∈ev⁡L+(u,v)\theta_r\in\operatorname{ev}_{L}^{+}(u,v), and odd if and only if θr∈ev⁡L−(u,v)\theta_r\in\operatorname{ev}_{L}^{-}(u,v).

If these hold, peak state transfer occurs precisely at all odd multiples of π/g\pi/g with phase factor 11.

Corollary 2.3 is powerful for our purposes because the demand of integrality of eigenvalues can be exploited in a number of ways. Among these are the facts that distinct integers must also have an integer difference, which we later use to prove edge bounds via the trace. Another useful implication is that the denominator of the resolvent entry between a pair of vertices with peak state transfer must be reducible as a polynomial over Z\mathbb{Z}. Finally, the integrality of elements of ev⁡L(u,v)\operatorname{ev}_{L}(u,v) also provides a means by which to use arithmetic techniques. In the main sections of the paper, we prove a number of results on Laplacian peak state transfer that are seemingly difficult to adapt to the adjacency case, and the reason is most often that the integrality provided by Corollary 2.3 is special to Laplacians.

Grounded Weyl functions

Throughout, we will let TT be a tree and zz its centre, or root.

Definition 2.4. Define the grounded Laplacian and grounded Weyl function as

R(T,z)=L(T)+ezezTR(T,z)=L(T)+e_z e_z^{\mathsf{T}}
W(T,z;θ)=[(R(T,z)−θI)−1]z,zW(T,z;\theta)=\left[(R(T,z)-\theta I)^{-1}\right]_{z,z}

respectively. For rooted trees with root z≠vz\ne v, we abbreviate Wv:=W(Bv,v;θ)W_v:=W(B_v,v;\theta) to mean the grounded Weyl function of the subtree BvB_v of TT rooted at vv.

The matrix R(T,z)R(T,z) is the principal submatrix of the Laplacian matrix of a hypothetically extant tree with TT as a rooted subtree. This idea leads to the following recurrence relation:

Lemma 2.5. Let zz be the root of a tree TT, and label the neighbors of zz as u1,u2,…,ulu_1,u_2,\ldots,u_l. Then, we have

Wz=(l+1−θ−∑i=1lWui)−1W_z=\left(l+1-\theta-\sum_{i=1}^{l}W_{u_i}\right)^{-1}

and Wz(0)=1W_z(0)=1 and Wz′(0)=nW'_z(0)=n. If TT contains only zz, then we have Wz=(1−θ)−1W_z=(1-\theta)^{-1}.

Proof. Write

D=⨁i=1l(R(Bi,ui)−θI)D=\bigoplus_{i=1}^{l}\left(R(B_i,u_i)-\theta I\right)

and observe that R(T,z)R(T,z) admits a partition

R(T,z)−θI=(l+1−θ−qT−qD)R(T,z)-\theta I= \begin{pmatrix} l+1-\theta& -q^{\mathsf{T}}\\ -q & D \end{pmatrix}

where q=∑i=1leuiq=\sum_{i=1}^{l}e_{u_i}, and then the Sherman-Morrison-Woodbury formula provides

Wz=ezT(R(T,z)−θI)−1ez=(l+1−θ−qTD−1q)−1W_z=e_z^{\mathsf{T}}(R(T,z)-\theta I)^{-1}e_z =\left(l+1-\theta-q^{\mathsf{T}}D^{-1}q\right)^{-1}

and qTD−1q=∑i=1lWuiq^{\mathsf{T}}D^{-1}q=\sum_{i=1}^{l}W_{u_i}.

For singleton graphs, Wz(θ)=(1−θ)−1W_z(\theta)=(1-\theta)^{-1}, Wz(0)=1W_z(0)=1, and Wz′(0)=1W'_z(0)=1 are obvious. If Wui(0)=1W_{u_i}(0)=1, then Wz=(l+1−∑i=1lWui(0))−1=1W_z=\left(l+1-\sum_{i=1}^{l}W_{u_i}(0)\right)^{-1}=1. Finally, Wz′=Wz2(1+∑iWui′)W'_z=W_z^2\left(1+\sum_i W'_{u_i}\right), so a similar recurrence gives Wz′(0)=nW'_z(0)=n. □

It will be useful to define the function, for integer ll,

ϱl(θ):=θ2−(l+2)θ+1\varrho_l(\theta):=\theta^2-(l+2)\theta+1

which appears repeatedly since

W(K1,n−1,z;θ)=1−θϱn−1(θ).(2)W(K_{1,n-1},z;\theta)=\frac{1-\theta}{\varrho_{n-1}(\theta)}. \tag*{(2)}

Moreover, we will denote the solutions of ϱl(θ)=0\varrho_l(\theta)=0 as

γl±=12(l+2±(l+2)2−4)\gamma_l^{\pm}=\frac{1}{2}\left(l+2\pm\sqrt{(l+2)^2-4}\right)

which are irrational whenever l>0l>0 and positive, satisfying γl+γl−=1\gamma_l^+\gamma_l^-=1.

Lemma 2.6. Again, suppose u1,u2,…,ulu_1,u_2,\ldots,u_l are the neighbors of zz, which root their own subtrees B1,B2,…,BlB_1,B_2,\ldots,B_l. Set

sz(θ):=1Wz(θ)−1=l−θ−∑i=1lWui.s_z(\theta):=\frac{1}{W_z(\theta)}-1=l-\theta-\sum_{i=1}^{l}W_{u_i}.

If ww is some vertex in TT and the unique path from zz to ww traverses vertices z=v0,v1,…,vk=wz=v_0,v_1,\ldots,v_k=w, then as rational functions,

[(L−θI)−1]z,z=sz(θ)−1[(L-\theta I)^{-1}]_{z,z}=s_z(\theta)^{-1}
[(L−θI)−1]z,w=1sz(θ)∏j=1kWvj.[(L-\theta I)^{-1}]_{z,w}=\frac{1}{s_z(\theta)}\prod_{j=1}^{k}W_{v_j}.

Moreover, sz(0)=0s_z(0)=0, and sz′<0s'_z<0 off the poles. Finally, sz′(0)=−ns'_z(0)=-n.

Proof. The first equality can be acquired in a way analogous to Lemma 2.5. To get the second, again recall q=∑i=1leuiq=\sum_{i=1}^{l}e_{u_i}, D=⨁i=1l(R(Bi,ui)−θI)D=\bigoplus_{i=1}^{l}(R(B_i,u_i)-\theta I), and consider the partitioned form of

ewT(L−θI)−1ez=(l−θ−qT−qD)−1ez=ewTD−1ql−θ−∑iWuie_w^{\mathsf T}(L-\theta I)^{-1}e_z= \begin{pmatrix} l-\theta& -q^{\mathsf T}\\ -q & D \end{pmatrix}^{-1} e_z =\frac{e_w^{\mathsf T}D^{-1}q}{l-\theta-\sum_i W_{u_i}}

again by the Sherman–Morrison–Woodbury formula. Furthermore,

ewTD−1q=∑i=1l([(R(Bi,ui)−θI)−1]ui,w)=[(R(B,v1)−θI)−1]v1,we_w^{\mathsf T}D^{-1}q=\sum_{i=1}^{l}([(R(B_i,u_i)-\theta I)^{-1}]_{u_i,w})=[(R(B,v_1)-\theta I)^{-1}]_{v_1,w}

where we write BB to mean the subtree rooted at v1=uiv_1=u_i for some ii, a neighbor of zz along the path from zz to ww. Repeating this procedure, we find that

[(R(B,v1)−θI)−1]v1,w=Wv1[(R(B′,v2)−θI)−1]v2,w[(R(B,v_1)-\theta I)^{-1}]_{v_1,w}=W_{v_1}[(R(B',v_2)-\theta I)^{-1}]_{v_2,w}

where now B′B' is the subtree rooted at v2v_2. Continue until reaching ww, at which point the product terminates. To see that sz(0)=0s_z(0)=0, observe that Wz(0)=1/(sz(0)+1)=1W_z(0)=1/(s_z(0)+1)=1 by Lemma 2.5, sz′<0s'_z<0 away from poles, and sz′(0)=−ns'_z(0)=-n similarly follow from Wz′(0)=nW'_z(0)=n.

Laplacian peak state transfer in trees

Classification of Laplacian peak state transfer in shallow trees

The following definition will aid us in our treatment of trees with bounded diameter.

Definition 3.1. Fix y≥0y\geq0 and positive integers N1,N2,…,NyN_1,N_2,\ldots,N_y and accompanying pairwise distinct b1≥0b_1\geq0 and b2,…,byb_2,\ldots,b_y each positive. Construct the tree T((N1,b1),(N2,b2),…,(Ny,by))T((N_1,b_1),(N_2,b_2),\ldots,(N_y,b_y)) by attaching to zz, which we call the root, NiN_i children who each have bib_i children of degree 1. Such a tree is called shallow.

Trees have either a unique centre or a pair of centres; for a shallow tree, the vertex zz that we call the root is one of the centres. Furthermore, note that all trees of diameter four or less are shallow, and all shallow trees have diameter at most four.

Shallow trees admit automorphic symmetries exchanging pairs of NiN_i vertices of degree bib_i, which makes Lemma 2.5 helpful in constructing the grounded Weyl functions of shallow trees. The following specialization of Lemma 2.5 to the case of shallow trees is of particular convenience:

Lemma 3.2. For a shallow tree T=T((N1,b1),(N2,b2),…,(Ny,by))T = T((N_1,b_1),(N_2,b_2),\ldots,(N_y,b_y)) with root zz, we have

Wz=W(T,z;θ)=(∑i=1yNi+1−θ−∑i=1yNi1−θϱbi(θ))−1W_z = W(T,z;\theta) = \left(\sum_{i=1}^{y} N_i + 1 - \theta- \sum_{i=1}^{y} N_i \frac{1-\theta}{\varrho_{b_i}(\theta)}\right)^{-1}

if b1>0b_1 > 0, and

Wz=W(T,z;θ)=(∑i=1yNi+1−θ−N11−θ−∑i=2yNi1−θϱbi(θ))−1W_z = W(T,z;\theta) = \left(\sum_{i=1}^{y} N_i + 1 - \theta- \frac{N_1}{1-\theta} - \sum_{i=2}^{y} N_i \frac{1-\theta}{\varrho_{b_i}(\theta)}\right)^{-1}

if $b_1 = 0.

Proof. We use Lemma 2.5 together with (2).

Shallow trees are not generally pairwise nonisomorphic; for example T((l,0),(1,r))≃T((r,0),(1,l))T((l,0),(1,r)) \simeq T((r,0),(1,l)). The following proposition demonstrates the reason for which we are unconcerned with this ambiguity: among shallow trees, only balanced trees with a single centre are capable of hosting Laplacian peak state transfer.

Proposition 3.3. For T=T((N1,b1),(N2,b2),…,(Ny,by))T = T((N_1,b_1),(N_2,b_2),\ldots,(N_y,b_y)) a shallow tree, Laplacian peak state transfer between any pair of vertices is forbidden whenever y>1y > 1.

Proof. Since sz=Wz−1−1s_z = W_z^{-1} - 1, Lemma 3.2 tells us that szs_z has poles at θ=1\theta= 1 if b1=0b_1 = 0 and γbi−\gamma_{b_i}^{-} in (0,1](0,1], which are pairwise distinct since the bib_i’s are. Let ρ1<ρ2≤1\rho_1 < \rho_2 \leq1 be the two smallest such poles of szs_z, which must exist as y>1y > 1. Lemma 2.6 shows that sz(0)=0s_z(0) = 0, and sz′(θ)<0s_z'(\theta) < 0 away from the poles of szs_z, so sz(θ)<0s_z(\theta) < 0 on (0,ρ1)(0,\rho_1) and it furthermore runs monotonically from lim⁡θ→ρ1+sz(θ)=∞\lim_{\theta\to\rho_1^+}s_z(\theta) = \infty to lim⁡θ→ρ2−sz(θ)=−∞\lim_{\theta\to\rho_2^-}s_z(\theta) = -\infty on (ρ1,ρ2)(\rho_1,\rho_2), and hence sz(θ)s_z(\theta) has exactly one zero in (ρ1,ρ2)(\rho_1,\rho_2), say λ\lambda. λ\lambda is a root of the monic integral characteristic polynomial of LL and hence an algebraic integer, and the only rational algebraic integers are ordinary integers, of which there are none in (ρ1,ρ2)⊂(0,1)(\rho_1,\rho_2) \subset(0,1), so λ\lambda is irrational.

For each vv adjacent to zz with bib_i children, we have that Wv(λ)=(1−λ)/ϱbi(λ)≠0W_v(\lambda) = (1-\lambda)/\varrho_{b_i}(\lambda) \neq0 since λ\lambda is strictly between ρ1\rho_1 and ρ2≤1\rho_2 \leq1. Likewise λ\lambda is neither a pole nor a zero of (1−θ)−1(1-\theta)^{-1}. λ\lambda is a simple zero of sz(θ)s_z(\theta) since sz′(λ)<0s_z'(\lambda) < 0 by Lemma 2.6, and no WviW_{v_i} has a pole or zero there—which was established in the preceding sentence—so λ\lambda is a pole of every resolvent entry in the zz row, and λ∈ev⁡L(z,u)\lambda\in\operatorname{ev}_L(z,u) for every vertex uu not equal to zz by Lemma 2.1.

If λ\lambda had multiplicity ≥2\geq2 one could choose an eigenvector ψ\psi with ψ(z)=0\psi(z) = 0; then ψ\psi restricts on some subtree to a null vector of R(Bv,v)−λIR(B_v,v)-\lambda I, and spec⁡R(Bv,v)={γbi−1−,1(bi−1),γbi+}\operatorname{spec} R(B_v,v) = \{\gamma_{b_i-1}^{-},1(b_i-1),\gamma_{b_i}^{+}\}, so λ\lambda is a pole or a zero of WvW_v, a contradiction. Hence, λ\lambda is a simple eigenvalue whose eigenvector is nowhere vanishing because (Eλ)z,u(E_\lambda)_{z,u} is nowhere vanishing. Therefore, λ\lambda is an element of ev⁡L(u,v)\operatorname{ev}_L(u,v) for any pair of vertices, and Corollary 2.3 then forbids Laplacian peak state transfer.

We now see the utility of the grounded Weyl functions; because of the recurrence structure provided by the hierarchical structure of a tree, it is inexpensive to calculate the grounded Weyl functions of shallow trees with a great number of vertices.

The surviving candidates for Laplacian peak state transfer are trees T((N1,0))≃K1,N1T((N_1,0)) \simeq K_{1,N_1} and T((N1,b1))T((N_1,b_1)) with b1>0b_1 > 0. The authors of [3] record that the former class universally admits Laplacian peak state transfer by virtue of their totally integral spectrum, and so we concern ourselves primarily with the second class of trees. As such, we will discard the second pair of parentheses when writing T((N1,b1))T((N_1,b_1)) and instead simply write T(N,b)T(N,b). The authors of [3] identified a single tree nonisomorphic to a star graph admitting peak state transfer from the root to one of its neighbors, namely T(3,2)T(3,2).

The fact that T(3,2)T(3,2) exhibits peak state transfer from the root to its children is not an accident; the recurrence structure of grounded Weyl functions makes it clear, by a similar argument, that Laplacian peak state transfer in trees of diameter four is permitted only involving roots.

Proposition 3.4. Let T=T(N,b)T=T(N,b) be a shallow, balanced tree with N≥2N\ge2, b≥1b\ge1 and root zz. If uu and vv are distinct from each other and from zz, there is an irrational number in ev⁡L(u,v)\operatorname{ev}_{L}(u,v), and hence peak state transfer between uu and vv is forbidden.

Proof. As in the proof of Proposition 3.3, we note that γb±\gamma_b^{\pm} is a pole of Wvi(θ)W_{v_i}(\theta) for each neighbor viv_i of zz, and in turn a pole of sz(θ)s_z(\theta), and not a pole of sz(θ)−1s_z(\theta)^{-1}. Therefore, (Eγb±)z,z=0(E_{\gamma_b^{\pm}})_{z,z}=0 by Lemma 2.1 and hence every γb±\gamma_b^{\pm} eigenvector vanishes on zz, and any γb±\gamma_b^{\pm} eigenvector is restricted to ker⁡(R(Bi,vi)−γb±)\ker(R(B_i,v_i)-\gamma_b^{\pm}) on the subtree rooted by viv_i. Moreover,

R(Bi,vi)=(b+1−1−1⋯−1−11−11⋮⋱−11),R(B_i,v_i)= \begin{pmatrix} b+1 & -1 & -1 & \cdots& -1\\ -1 & 1\\ -1 & & 1\\ \vdots& & & \ddots\\ -1 & & & & 1 \end{pmatrix},

so ker⁡(R(Bi,vi)−γb±)\ker(R(B_i,v_i)-\gamma_b^{\pm}) is one-dimensional and spanned by χ=(1−γb±,1,…,1)\chi=(1-\gamma_b^{\pm},1,\ldots,1) since spec⁡(R(Bi,vi))={γb−,1(b−1),γb+}\operatorname{spec}(R(B_i,v_i))=\{\gamma_b^{-},1^{(b-1)},\gamma_b^{+}\}. Finally, since γb±\gamma_b^{\pm} eigenvectors vanish on zz, their viv_i coefficients must sum to zero, so we have that

Eγb±=1χTχ(IN−1N11T)⊗χχT,E_{\gamma_b^{\pm}}=\frac{1}{\chi^{\mathsf T}\chi}\left(I_N-\frac{1}{N}\mathbf{1}\mathbf{1}^{\mathsf T}\right)\otimes\chi\chi^{\mathsf T},

where the matrix is understood to vanish on the zz row and column. Hence, (Eγb±)u,v(E_{\gamma_b^{\pm}})_{u,v} is nonvanishing for every uu and vv distinct from zz, and ev⁡L(u,v)\operatorname{ev}_{L}(u,v) contains γb±\gamma_b^{\pm}, necessarily irrational. Corollary 2.3 then forbids Laplacian peak state transfer. □

We note that the assumption N≥2N\ge2 precludes T(1,b)≅K1,b+1T(1,b)\cong K_{1,b+1} and b≥1b\ge1 precludes T(N,0)≅K1,NT(N,0)\cong K_{1,N}, the star graphs. This preclusion is important, as stars generally admit peak state transfer between some pair of vertices.

Propositions 3.3 and 3.4 together mean that the only candidates for Laplacian peak state transfer in shallow trees are balanced, and in any such examples, the root of the balanced tree must be one of the vertices in every transfer pair. The fact that peak state transfer must involve the root is convenient, since the grounded Weyl function products from the root of a balanced tree to some other vertex telescope in a pleasing way.

Proposition 3.5. Let T=T(N,b)T=T(N,b) be a balanced, shallow tree. There is Laplacian peak state transfer between the root zz and some other vertex if and only if there exist integers of opposite parity α≥1\alpha\ge1 and β≥2\beta\ge2 such that N=αβ+β−αN=\alpha\beta+\beta-\alpha and b=αβb=\alpha\beta. If α\alpha is odd and β\beta even, there is peak state transfer from root to child with amplitude 2(αβ+β)(α+β)(αβ+β+1)\frac{2(\alpha\beta+\beta)}{(\alpha+\beta)(\alpha\beta+\beta+1)}. If instead β\beta is the odd one, there is peak state transfer from root to leaf with amplitude 2(α+β)(αβ−α+1)\frac{2}{(\alpha+\beta)(\alpha\beta-\alpha+1)}.

Proof. Throughout, let zz be the root, uu any child of the root, and ww any leaf. From Lemma 3.2, we have

Wz=(N+1−θ−N1−θΘb(θ))−1W_z=\left(N+1-\theta-N\frac{1-\theta}{\Theta_b(\theta)}\right)^{-1}

while (2) gives

Wu=1−θϱb(θ)W_u=\frac{1-\theta}{\varrho_b(\theta)}

and trivially Ww=(1−θ)−1W_w=(1-\theta)^{-1}. Combining the three with Lemma 2.6 gives

[(L−θI)−1]z,u=1sz(θ)Wu=WzWu1−Wz=1−θθ(ϱb+N(θ)+bN+N)[(L-\theta I)^{-1}]_{z,u}=\frac{1}{s_z(\theta)}W_u=\frac{W_zW_u}{1-W_z}=\frac{1-\theta}{\theta(\varrho_{b+N}(\theta)+bN+N)}
[(L−θI)−1]z,w=1sz(θ)WuWw=WzWuWw1−Wz=1θ(ϱb+N(θ)+bN+N).[(L-\theta I)^{-1}]_{z,w}=\frac{1}{s_z(\theta)}W_uW_w=\frac{W_zW_uW_w}{1-W_z}=\frac{1}{\theta(\varrho_{b+N}(\theta)+bN+N)}.

In either case, the poles are, by Lemma 2.1,

ev⁡L(z,u)=ev⁡L(z,w)={0,μ,ν},\operatorname{ev}_L(z,u)=\operatorname{ev}_L(z,w)=\{0,\mu,\nu\},

with μ<ν\mu<\nu and

μ=12(2+b+N−(b−N)2+4b)ν=12(2+b+N+(b−N)2+4b)\mu=\frac{1}{2}\left(2+b+N-\sqrt{(b-N)^2+4b}\right) \qquad \nu=\frac{1}{2}\left(2+b+N+\sqrt{(b-N)^2+4b}\right)

and ev⁡L(z,u)⊂Z\operatorname{ev}_L(z,u)\subset\mathbb{Z} is equivalent to the requirement that (b−N)2+4b(b-N)^2+4b is a perfect square since b+N≡(b−N)2+4b(mod2)b+N\equiv(b-N)^2+4b\pmod{2} and a perfect square that is even is also divisible by four. Write

r2=(b−N)2+4b,r^2=(b-N)^2+4b,

and rearrange to see that b=(r+b−N)(r−b+N)/4b=(r+b-N)(r-b+N)/4, which are of the same parity, and even since bb is assumed to be an integer. Write

α=12(r+b−N),β=12(r−b+N),\alpha=\frac{1}{2}(r+b-N),\qquad\beta=\frac{1}{2}(r-b+N),

and note that r=α+βr=\alpha+\beta, so we have further that

N=αβ+β−α,b=αβN=\alpha\beta+\beta-\alpha,\qquad b=\alpha\beta

where we note that the choice of sign in the quadratic formula is the choice that distinguishes β\beta from α\alpha, and the choice is unimportant. Clearly b≥1b\geq1 and N≥2N\geq2 impose α≥1\alpha\geq1 and β≥2\beta\geq2. In terms of α\alpha and β\beta, we have

μ=αβ−α+1,ν=αβ+β+1\mu=\alpha\beta-\alpha+1,\qquad\nu=\alpha\beta+\beta+1

and thus we recognize that

(μ+1)(ν+1)≡αβ(α+1)(β+1)≡0(mod2)μ+ν≡α+β(mod2)(3)(\mu+1)(\nu+1)\equiv\alpha\beta(\alpha+1)(\beta+1)\equiv0\pmod{2} \qquad \mu+\nu\equiv\alpha+\beta\pmod{2} \tag*{(3)}

so, in particular, μ\mu and ν\nu cannot both be even, and are both odd when α\alpha and β\beta have the same parity. Hence, gcd⁡(μ,ν)\gcd(\mu,\nu) is odd, and we now need only to check the hypothesis of Corollary 2.3. Using Lemma 2.1 again, we find,

(E0)z,u=(E0)z,w=1μν>0(E_0)_{z,u}=(E_0)_{z,w}=\frac{1}{\mu\nu}>0
(Eμ)z,u=1−μμ(μ−ν)>0(E_\mu)_{z,u}=\frac{1-\mu}{\mu(\mu-\nu)}>0
(Eν)z,u=1−νν(ν−μ)<0(E_\nu)_{z,u}=\frac{1-\nu}{\nu(\nu-\mu)}<0
(Eμ)z,w=1μ(μ−ν)<0(E_\mu)_{z,w}=\frac{1}{\mu(\mu-\nu)}<0
(Eν)z,w=1ν(ν−μ)>0.(E_\nu)_{z,w}=\frac{1}{\nu(\nu-\mu)}>0.

Hence, the balanced shallow trees that admit Laplacian peak state transfer are precisely those for which μ\mu and ν\nu have opposite parity, namely those for which α\alpha and β\beta have opposite parity, by (11).

Finally, we use Lemma 2.1 once more to get the transfer amplitudes. If α\alpha is odd and β\beta even, there is Laplacian peak state transfer from root to child with amplitude

(BL)z,u=2(ν−1)ν(ν−μ)=2(αβ+β)(α+β)(αβ+β+1)(B_L)_{z,u}=\frac{2(\nu-1)}{\nu(\nu-\mu)}=\frac{2(\alpha\beta+\beta)}{(\alpha+\beta)(\alpha\beta+\beta+1)}

When β\beta is odd and α\alpha even, the peak state transfer is from root to leaf with amplitude

(BL)z,w=2μ(ν−μ)=2(α+β)(αβ−α+1).(B_L)_{z,w}=\frac{2}{\mu(\nu-\mu)}=\frac{2}{(\alpha+\beta)(\alpha\beta-\alpha+1)}.

Up to this point, we have not made use of equitable partitions or the Jacobi matrices that come from them. Propositions 3.3 and 3.4 are greatly aided by the use of Weyl functions over Jacobi matrices, but Proposition 3.5 is arguably less complicated in the language of Jacobi matrices. We have nonetheless elected to forego a treatment in that language, as we have reason to think the Jacobi technology will not be amenable to generalization.

Remark 3.6. Among trees of diameter four, Laplacian peak state transfer amplitude is maximized by T(3,2)T(3,2) which hosts peak state transfer from root to each child at amplitude 8/158/15. This example was found by Coutinho, Guo, and Schmeits in [3], and it is optimal. This is a notable contrast to the adjacency peak state transfer case, where the tree T(n2−1,1)T(n^2-1,1) admits adjacency peak state transfer from each child of the root to the adjacent leaf for n≡1(mod4)n \equiv1 \pmod{4} with amplitude 1−1/(n2+n)→11-1/(n^2+n) \to1 as n→∞n \to\infty. In particular, Proposition 3.4 emphatically does not hold for adjacency peak state transfer. Although adjacency perfect state transfer in trees with more than three vertices is forbidden [5], one can get arbitrarily close.

We now collect Propositions 3.3, 3.4, and 3.5 to prove the main theorem of this section.

Theorem 3.7. Suppose TT is a tree of diameter at most four with four or more vertices. There is Laplacian peak state transfer between some pair of vertices in TT if and only if TT is either a star or a balanced rooted tree T(αβ+β−α,αβ)T(\alpha\beta+\beta-\alpha,\alpha\beta) for some pair of integers α≥1\alpha\ge1 and β≥2\beta\ge2 of opposite parity.

Proof. Proposition 3.3 shows that there are no unbalanced trees of diameter three or four admitting Laplacian peak state transfer between any pair of vertices. Proposition 3.4 shows that Laplacian peak state transfer in balanced trees of diameter four can occur only between the root and some vertex. Proposition 3.5 then classifies all balanced trees of diameter four with Laplacian peak state transfer between the root and some other vertex. It only remains to show that stars always admit some Laplacian peak state transfer from root to leaf. To that end, consider T(N,0)≃K1,NT(N,0) \simeq K_{1,N} with root zz and uu a neighbor of zz. Then,

Wz=(N+1−θ−N11−θ)−1W_z=\left(N+1-\theta-N\frac{1}{1-\theta}\right)^{-1}
Wu=(1−θ)−1W_u=(1-\theta)^{-1}

so

WuWz1−Wz=1θ(θ−N−1)\frac{W_uW_z}{1-W_z}=\frac{1}{\theta(\theta-N-1)}

and Lemma 2.1 then gives ev⁡L+(z,u)={0}\operatorname{ev}^{+}_{L}(z,u)=\{0\}, and ev⁡L−(z,u)={N+1}\operatorname{ev}^{-}_{L}(z,u)=\{N+1\} from whence Corollary 2.3 provides peak state transfer.

Remark 3.8. Perfect state transfer is monogamous in the sense that, if there is perfect state transfer between distinct vertices uu and vv at time tt, and there is perfect state transfer from uu to ww at time tt, then v=wv=w. However, neither strong cospectrality nor peak state transfer are monogamous alone.

Laplacian peak state transfer in deeper trees

A natural conjecture is that Theorem 3.7 is sharp, or that in fact Laplacian peak state transfer in trees is fully resolved therein. Toward extending a classification to deeper trees, a sensible attack would be to attempt to generalize Proposition 3.3 to deeper trees. The first sign that such an attempt might encounter difficulties comes from the fact that the poles of sz(θ)s_z(\theta) are no longer straightforwardly enumerable from the degrees of the neighbors of zz. In particular, each child of a root in a tree of diameter 4 or less either roots a star subtree (in which case it contributes a pole of szs_z in (0,1)(0,1)) or a singleton subtree that contributes a pole at exactly 1. Moreover, a pair of children of the root of a tree of diameter four or less have grounded Weyl functions with equal poles only if they can be exchanged by an automorphism. For deeper trees, however, this is no longer the case. For example, the trees T(N,b)T(N,b) and T(b,N)T(b,N) have the same pole set of the grounded Weyl function at the root, but they are not graph isomorphic. We exploit this fact to show that not only are there infinitely many trees admitting Laplacian peak state transfer beyond diameter four, there are infinitely many that fail to be balanced. In other words, a naive generalization of Proposition 3.3 at arbitrary diameter is false.

Pursuant to the promised result, we need a definition:

Definition 3.9. Fix positive integers b1b_1, b2b_2, N1N_1, and N2N_2 with b1≠b2b_1 \ne b_2, and N1≥N2N_1 \ge N_2. Construct the tree T=T(b1,b2;N1,N2)T=T(b_1,b_2;N_1,N_2) with root zz such that zz has N1N_1 children that are the root of their own T(b1,b2)T(b_1,b_2) subtree and N2N_2 children that are the root of a T(b2,b1)T(b_2,b_1) subtree.

Proposition 3.10. The trees T(4α,8α−2;2α,1)T(4\alpha,8\alpha-2;2\alpha,1) have Laplacian peak state transfer between the root and each of its neighbors of degree 4α+14\alpha+1 for every positive integer α\alpha, with peak amplitude

(BL)z,u=12α[1(4α+1)(8α+1)+12α2−1(2α+1)(6α+1)+8α2−1(2α+1)(4α+1)+4α+1(6α+1)(8α+1)](B_L)_{z,u}=\frac{1}{2\alpha}\left[\frac{1}{(4\alpha+1)(8\alpha+1)}+\frac{12\alpha^2-1}{(2\alpha+1)(6\alpha+1)}+\frac{8\alpha^2-1}{(2\alpha+1)(4\alpha+1)}+\frac{4\alpha+1}{(6\alpha+1)(8\alpha+1)}\right]

Proof. Throughout, we will suppose uu is some neighbor of zz of degree b1+1=4α+1b_1+1=4\alpha+1, and vv is some neighbor of zz of degree b2+1=8α−1b_2+1=8\alpha-1. We proceed by again using the grounded Weyl functions. From Lemma 3.2, we have

Wu=(b1+1−θ−b11−θqb2(θ))−1=qb2(θ)Pb1,b2(θ)W_u=\left(b_1+1-\theta-b_1\frac{1-\theta}{q_{b_2}(\theta)}\right)^{-1}=\frac{q_{b_2}(\theta)}{P_{b_1,b_2}(\theta)}
Wv=(b2+1−θ−b21−θqb1(θ))−1=qb1(θ)Pb1,b2(θ)W_v=\left(b_2+1-\theta-b_2\frac{1-\theta}{q_{b_1}(\theta)}\right)^{-1}=\frac{q_{b_1}(\theta)}{P_{b_1,b_2}(\theta)}

with Pb1,b2(θ):=1−(3+b1+b2+b1b2)θ+(3+b1+b2)θ2−θ3P_{b_1,b_2}(\theta):=1-(3+b_1+b_2+b_1b_2)\theta+(3+b_1+b_2)\theta^2-\theta^3. Hence, we have

Wz=(N1+N2+1−θ−N1Wu−N2Wv)−1=Pb1,b2(θ)(N1+N2+1−θ)Pb1,b2(θ)−N1qb2(θ)−N2qb1(θ)W_z=(N_1+N_2+1-\theta-N_1W_u-N_2W_v)^{-1} =\frac{P_{b_1,b_2}(\theta)} {(N_1+N_2+1-\theta)P_{b_1,b_2}(\theta)-N_1q_{b_2}(\theta)-N_2q_{b_1}(\theta)}

by Lemma 2.5. Now, using Lemma 2.6, we find

[(L−θI)−1]z,u=WzWu1−Wz=qb2(θ)(N1+N2−θ)Pb1,b2(θ)−N1qb2(θ)−N2qb1(θ)(4)\left[(L-\theta I)^{-1}\right]_{z,u} =\frac{W_zW_u}{1-W_z} =\frac{q_{b_2}(\theta)} {(N_1+N_2-\theta)P_{b_1,b_2}(\theta)-N_1q_{b_2}(\theta)-N_2q_{b_1}(\theta)} \tag*{(4)}

We note that, a priori, (4) is a ratio of polynomials of degree nn, but in practice, it is the ratio of a quadratic with a quartic. This simplicity comes from two sources: First, the neighbors of zz root balanced subtrees, meaning that the Weyl functions WuW_u and WvW_v are of lower degree than the generic diameter four case. Secondly, WuW_u and WvW_v have the common denominator Pb1,b2=Pb2,b1P_{b_1,b_2}=P_{b_2,b_1}. These two facts conspire together to induce a cancellation of Pb1,b2P_{b_1,b_2} in the entry of the resolvent that we calculate.

Specializing now to b1=4αb_1=4\alpha, b2=8α−2b_2=8\alpha-2, N1=2αN_1=2\alpha, and N2=1N_2=1, we find

[(L−θI)−1]z,u=θ2−8αθ+1θ(θ3−2(7α+1)θ2+(56α2+16α+1)θ−2α(1+12α+32α2)).(5)[(L-\theta I)^{-1}]_{z,u}=\frac{\theta^2-8\alpha\theta+1}{\theta\left(\theta^3-2(7\alpha+1)\theta^2+(56\alpha^2+16\alpha+1)\theta-2\alpha(1+12\alpha+32\alpha^2)\right)}. \tag*{(5)}

The denominator factors as F(θ)=θ(θ−2α)(θ−4α−1)(θ−8α−1)F(\theta)=\theta(\theta-2\alpha)(\theta-4\alpha-1)(\theta-8\alpha-1), while the numerator is ϱ8α−2(θ)\varrho_{8\alpha-2}(\theta) and has only irrational roots γ8α−2\gamma_{8\alpha-2}, so the poles of (5) are precisely the roots of F(θ)F(\theta) and therefore ev⁡L(z,u)={0,2α,4α+1,8α+1}\operatorname{ev}_L(z,u)=\{0,2\alpha,4\alpha+1,8\alpha+1\}.

Finally, we invoke Lemma 2.1 to find

ϱb2(0)=1,ϱb2(2α)=1−12α2,ϱb2(4α+1)=2−16α2,ϱb2(8α+1)=8α+2.(6)\begin{aligned} \varrho_{b_2}(0)&=1,\\ \varrho_{b_2}(2\alpha)&=1-12\alpha^2,\\ \varrho_{b_2}(4\alpha+1)&=2-16\alpha^2,\\ \varrho_{b_2}(8\alpha+1)&=8\alpha+2. \tag*{(6)} \end{aligned}

and

F′(0)=−2α(4α+1)(8α+1),F′(2α)=2α(2α+1)(6α+1),F′(4α+1)=−4α(2α+1)(4α+1),F′(8α+1)=4α(6α+1)(8α+1).(7)\begin{aligned} F'(0)&=-2\alpha(4\alpha+1)(8\alpha+1),\\ F'(2\alpha)&=2\alpha(2\alpha+1)(6\alpha+1),\\ F'(4\alpha+1)&=-4\alpha(2\alpha+1)(4\alpha+1),\\ F'(8\alpha+1)&=4\alpha(6\alpha+1)(8\alpha+1). \tag*{(7)} \end{aligned}

Combining (6) and (7) as (Eθ)z,u=−ϱb2(θ)/F′(θ)(E_\theta)_{z,u}=-\varrho_{b_2}(\theta)/F'(\theta), we produce the matrix elements of the spectral idempotents

(E0)z,u=12α(4α+1)(8α+1)=1n>0,(E2α)z,u=12α2−12α(2α+1)(6α+1)>0,(E4α+1)z,u=−8α2−12α(2α+1)(4α+1)<0,(E8α+1)z,u=−4α+12α(6α+1)(8α+1)<0.(8)\begin{aligned} (E_0)_{z,u}&=\frac{1}{2\alpha(4\alpha+1)(8\alpha+1)}=\frac{1}{n}>0,\qquad (E_{2\alpha})_{z,u}=\frac{12\alpha^2-1}{2\alpha(2\alpha+1)(6\alpha+1)}>0,\\ (E_{4\alpha+1})_{z,u}&=-\frac{8\alpha^2-1}{2\alpha(2\alpha+1)(4\alpha+1)}<0,\qquad (E_{8\alpha+1})_{z,u}=-\frac{4\alpha+1}{2\alpha(6\alpha+1)(8\alpha+1)}<0. \tag*{(8)} \end{aligned}

2α2\alpha is even while 4α+14\alpha+1 and 8α+18\alpha+1 are odd, so g=gcd⁡(2α,4α+1,8α+1)g=\gcd(2\alpha,4\alpha+1,8\alpha+1) must be odd, and hence μ/g\mu/g has the same parity as μ\mu for μ\mu in ev⁡L(z,u)\operatorname{ev}_L(z,u), and (8) shows that μ\mu in ev⁡L(z,u)\operatorname{ev}_L(z,u) is odd exactly when (Eμ)z,u<0(E_\mu)_{z,u}<0. Explicitly,

ev⁡L+(z,u)={0,2α},ev⁡L−(z,u)={4α+1,8α+1}.\operatorname{ev}^{+}_L(z,u)=\{0,2\alpha\},\qquad\operatorname{ev}^{-}_L(z,u)=\{4\alpha+1,8\alpha+1\}.

Hence, Corollary 2.3 provides Laplacian peak state transfer between zz and uu.

To get the displayed expression for the transfer amplitude, add together the amplitudes of (8).

Remark 3.11. The maximum peak state transfer amplitude achieved by a tree of diameter four in the family described by Proposition 3.10 is (BL)z,u=172/315(B_L)_{z,u}=172/315 achieved at α=1\alpha=1. Notably, 172/315>8/15172/315>8/15, which is to say that the maximum achievable Laplacian peak state transfer in shallow trees is not optimal across the class of non-star trees. It would be interesting to know if there exists a family of trees, none isomorphic to a star, with Laplacian peak state transfer amplitude tending to one.

In trees of diameter four or less, Laplacian peak state transfer can occur only at distances one and two. Likewise the unbalanced family from Proposition 3.10 has peak state transfer at distance one only. It is natural to ask whether Laplacian peak state transfer can occur at larger distances in trees, and the following example shows that it can.

Proposition 3.12. Construct the tree TT with root zz by affixing ll vertices adjacent to zz that each root their own T(N,b)T(N,b) subtree. When l=17l=17, N=26N=26, and b=20b=20, there is Laplacian peak state transfer from zz to every vertex of degree 11 at every odd multiple of t=πt=\pi.

Proof. We proceed as we have before, namely by calculating grounded Weyl functions recursively via Lemma 2.6 and using Lemma 2.1 to find the poles of the resolvent entry connecting zz to some leaf. Suppose that a path from zz to a leaf consists of the vertices uu, vv, and ww with ww a leaf and uu adjacent to zz. Then,

Ww=11−θWv=1−θ(b+1−θ)(1−θ)−bWu=(b+1−θ)(1−θ)−b(N+1−θ)[(b+1−θ)(1−θ)−b]−N(1−θ)Wz=(N+1−θ)[(b+1−θ)(1−θ)−b]−N(1−θ)(l+1−θ)[(N+1−θ)[(b+1−θ)(1−θ)−b]]−l(θ2−(b+2)θ+1)\begin{aligned} W_w &= \frac{1}{1-\theta}\\ W_v &= \frac{1-\theta}{(b+1-\theta)(1-\theta)-b}\\ W_u &= \frac{(b+1-\theta)(1-\theta)-b}{(N+1-\theta)[(b+1-\theta)(1-\theta)-b]-N(1-\theta)}\\ W_z &= \frac{(N+1-\theta)[(b+1-\theta)(1-\theta)-b]-N(1-\theta)}{(l+1-\theta)[(N+1-\theta)[(b+1-\theta)(1-\theta)-b]]-l(\theta^2-(b+2)\theta+1)} \end{aligned}

and we calculate

[(L−θI)−1]z,w=WzWuWvWw1−Wz=(θ4−(3+l+N+b)θ3+(3+N+l(2+N)+b(1+l+N))θ2−(1+l(1+N+bN))θ)−1[(L-\theta I)^{-1}]_{z,w}=\frac{W_zW_uW_vW_w}{1-W_z}=\left(\theta^4-(3+l+N+b)\theta^3+(3+N+l(2+N)+b(1+l+N))\theta^2-(1+l(1+N+bN))\theta\right)^{-1}

where the first equality is Lemma 2.6. Writing

[(L−θI)−1]z,w=1θ(θ−λ1)(θ−λ2)(θ−λ3)[(L-\theta I)^{-1}]_{z,w}=\frac{1}{\theta(\theta-\lambda_1)(\theta-\lambda_2)(\theta-\lambda_3)}

with λ1<λ2<λ3\lambda_1<\lambda_2<\lambda_3 distinct by construction, we conclude that λi/g≡i(mod2)\lambda_i/g\equiv i\pmod{2} where g=gcd⁡(λ1,λ2,λ3)g=\gcd(\lambda_1,\lambda_2,\lambda_3) is equivalent to the desired result by Lemma 2.1 and Corollary 2.3. Since (θ−λ1)(θ−λ2)(θ−λ3)(\theta-\lambda_1)(\theta-\lambda_2)(\theta-\lambda_3) is cubic with three distinct real roots, we can produce a formula for λi\lambda_i in terms of trigonometric functions of ll, NN, and bb.

Specializing now to the case at hand, we find l=17l=17, N=26N=26, b=20b=20 implies ev⁡L(z,w)={0,15,20,31}\operatorname{ev}_L(z,w)=\{0,15,20,31\} which have gcd⁡(15,20,31)=1\gcd(15,20,31)=1 and satisfy the required parity conditions.

It is clear that trees of diameter exceeding four are increasingly permissive, and the rigidity of the grounded Weyl function of shallow trees does not persist in full force for broader trees. For balanced trees of diameter six, like the one in Proposition 3.12, the problem of constructing examples can be reduced to iteratively checking parities of prescribed roots of a cubic polynomial whose integral coefficients can be freely specified. Even for balanced trees, deeper examples generally require computing the roots of a higher-degree polynomial and are thus much more expensive. As we have no reason to suspect that balanced trees are the most prevalent examples in broader trees, we conclude our discussion of Laplacian peak state transfer in trees with the opinion that examples are likely abundant and varied in nature, especially for broader trees. However, the conclusion remains that, toward the motivation as a quantum wire, trees seem like a poor candidate, and peak state transfer in trees generally requires a great number of edges as we will see in the following discussion.

Economic peak state transfer

We now turn our attention to bounding the number of edges required to achieve peak state transfer in a graph GG, not necessarily a tree. The machinery that drives the two theorems of this section is the following elementary lemma:

Lemma 4.1. Let MM be a symmetric matrix such that (Mk)u,v=0(M^k)_{u,v}=0 for k<dk<d. Either ev⁡M(u,v)=∅\operatorname{ev}_M(u,v)=\varnothing or ∣ev⁡M(u,v)∣≥d+1\lvert\operatorname{ev}_M(u,v)\rvert\ge d+1.

Proof. Write (Mk)u,v=∑θr∈ev⁡M(u,v)θrk(Eθr)u,v(M^k)_{u,v}=\sum_{\theta_r\in\operatorname{ev}_M(u,v)}\theta_r^k(E_{\theta_r})_{u,v} and suppose ∣ev⁡M(u,v)∣=s≤d\lvert\operatorname{ev}_M(u,v)\rvert=s\le d. Since (Mk)u,v=0(M^k)_{u,v}=0 for k<dk<d, the invertible s×ss\times s Vandermonde system in distinct eigenvalues θr\theta_r forces (Eθr)u,v=0(E_{\theta_r})_{u,v}=0 for all rr, so ev⁡M(u,v)\operatorname{ev}_M(u,v) is empty. □\square

By relating the number of distinct eigenvalues in ev⁡M(u,v)\operatorname{ev}_M(u,v) to the transfer distance, we can relate the number of edges in a graph to the eigenvalues of either AA or LL via the trace of A2A^2 or LL.

Edge count bounds

Theorem 4.2. Let GG be a simple graph with mm edges admitting peak state transfer with respect to its adjacency matrix between vertices at distance dd. Then,

m≥124d(d+1)(d+2).m\ge\frac{1}{24}d(d+1)(d+2).

Proof. Each θ\theta in ev⁡A(u,v)\operatorname{ev}_A(u,v) is an eigenvalue of AA of multiplicity at least one, and Tr⁡A2=2m\operatorname{Tr} A^2=2m, so 2m≥∑θ∈ev⁡A(u,v)θ22m\ge\sum_{\theta\in\operatorname{ev}_A(u,v)}\theta^2 by Lemma 4.1. By Theorem 2.2, θr=12(a+brD)\theta_r=\frac{1}{2}(a+b_r\sqrt{D}) as above. If D=1D=1, ev⁡A(u,v)={θ1,θ2,…,θN}\operatorname{ev}_A(u,v)=\{\theta_1,\theta_2,\ldots,\theta_N\} consists of NN distinct integers. If NN is odd, then

∑r=1Nθr2≥2∑r=1(N−1)/2r2=112(N3−N)(9)\sum_{r=1}^{N}\theta_r^2\ge2\sum_{r=1}^{(N-1)/2}r^2=\frac{1}{12}(N^3-N) \tag*{(9)}

and otherwise we have

∑r=1Nθr2≥−(N2)2+2∑r=1N/2r2=112N3+16N≥112(N3−N).(10)\sum_{r=1}^{N}\theta_r^2\ge-\left(\frac{N}{2}\right)^2+2\sum_{r=1}^{N/2}r^2=\frac{1}{12}N^3+\frac{1}{6}N\ge\frac{1}{12}(N^3-N). \tag*{(10)}

Hence,

2m≥∑r=1Nθr2≥112(N3−N)≥112d(d+1)(d+2).2m\ge\sum_{r=1}^{N}\theta_r^2\ge\frac{1}{12}(N^3-N)\ge\frac{1}{12}d(d+1)(d+2).

On the other hand, if D>1D>1, (A,u,v)(A,u,v) is eligible and thus ev⁡A(u,v)\operatorname{ev}_A(u,v) is closed under algebraic conjugation, so ∑θr∈ev⁡A(u,v)br=0\sum_{\theta_r\in\operatorname{ev}_A(u,v)}b_r=0, and

∑θr∈ev⁡A(u,v)θr2=Na24+D4∑rbr2≥112N(N−1)(2N−1)≥112d(d+1)(d+2)\sum_{\theta_r\in\operatorname{ev}_A(u,v)}\theta_r^2=\frac{Na^2}{4}+\frac{D}{4}\sum_r b_r^2\ge\frac{1}{12}N(N-1)(2N-1)\ge\frac{1}{12}d(d+1)(d+2)

where we have used D≥2D \ge2, and the fixed parity of brb_r to invoke

∑r=1Nbr2≥16N(N−1)(2N−1)\sum_{r=1}^{N} b_r^2 \ge\frac{1}{6}N(N-1)(2N-1)

by the same means as in (9) and (10). In any case, the theorem is established.

Theorem 4.2 is tight at leading order, including the constant prefactor. In [3], Coutinho, Guo, and Schmeits constructed a family of unweighted graphs YnY_n exhibiting peak state transfer with respect to their adjacency matrices at distance d=2n−2d=2n-2 containing m=d3/24(1+o(1))m=d^3/24(1+o(1)) edges, and hence the only possible improvements to Theorem 4.2 must come at order d2d^2 or lower.

Theorem 4.3. Let GG be a simple graph with mm edges admitting Laplacian peak state transfer between vertices at distance dd. Then,

m≥14d(d+1)m \ge\frac{1}{4}d(d+1)

Proof. By Corollary 2.3 and Lemma 4.1, ev⁡L(u,v)\operatorname{ev}_L(u,v) consists of at least d+1d+1 distinct integers (of which dd must be positive) and integers alone. Moreover, the sum of dd distinct positive integers is at least d(d+1)/2d(d+1)/2. Hence, we have

2m=Tr⁡L≥∑θ∈ev⁡L(u,v)θ≥12d(d+1).2m=\operatorname{Tr}L \ge\sum_{\theta\in\operatorname{ev}_L(u,v)}\theta\ge\frac{1}{2}d(d+1).

In [4], the authors prove that perfect state transfer in a graph of diameter DD requires at least Ω(D3)\Omega(D^3) edges, by first showing that the eccentricity of a vertex bounds below the number of spectral idempotents it supports, and then eigenvalue spacing is provided by periodicity, which is strictly weaker than perfect state transfer. In our arguments, the eigenvalue spacing analogue that allows us to use traces to bound the number of edges is instead provided by the results of [3]. The cost of relinquishing the demand of periodicity is that our edge bounds are stated in terms of peak state transfer distance dd, which are weaker than bounds in terms of the graph diameter.

The ingredients of Theorem 4.3 are the fully integral ev⁡L(u,v)\operatorname{ev}_L(u,v) that cannot have too few elements, and the fact that the trace of a Laplacian gives the number of edges. The matrix-tree theorem relates the number of vertices to a product of eigenvalues, so the same set of ingredients can be made to relate the peak state transfer distance and the number of independent cycles in a graph. The cycle rank of a connected graph, m−n+1m-n+1, is the same as its first Betti number.

Proposition 4.4. In the setting of Theorem 4.3, with maximum vertex degree Δ\Delta, GG has a vertex of degree at least d/2d/2 and cycle rank at least (log⁡d!−log⁡n)/log⁡m(\log d!-\log n)/\log m.

Proof. The maximum eigenvalue of LL is at least dd since ev⁡L(u,v)\operatorname{ev}_L(u,v) contains an integer at least dd. On the other hand, the maximum eigenvalue is bounded above by 2Δ2\Delta [7].

Write φL(x)\varphi_L(x) to mean the characteristic polynomial of LL which is integral and monic, and φ(x):=x∏θ∈ev⁡L(u,v)∖{0}(x−θ)\varphi(x):=x\prod_{\theta\in\operatorname{ev}_L(u,v)\setminus\{0\}}(x-\theta) which is likewise integral and monic by Corollary 2.3. Because exact factorization of monic integral polynomials preserves integer coefficients, φL(x)/φ(x)\varphi_L(x)/\varphi(x) is integral and monic, and hence its evaluation at x=0x=0 is a nonzero integer. Therefore the product of nonzero eigenvalues of LL outside of ev⁡L(u,v)\operatorname{ev}_L(u,v) with multiplicity is at least one. By the matrix-tree theorem, we have immediately

nτ(G)≥∏θ∈ev⁡L(u,v)∖{0}θ≥d!,n\tau(G) \ge\prod_{\theta\in\operatorname{ev}_L(u,v)\setminus\{0\}} \theta\ge d!,

which produces the desired result after using the definition of the cycle rank and the fact that each spanning tree is acquired from GG by deleting some number of edges, so

τ(G)≤(mm−n+1)≤mm−n+1.\tau(G) \le\binom{m}{m-n+1} \le m^{m-n+1}.

Remark 4.5. For trees in particular, Proposition 4.4 specializes to

log⁡n≥log⁡d!,\log n \ge\log d!,

or d=O(log⁡n/log⁡log⁡n)=O(log⁡m/log⁡log⁡m)d = O(\log n/\log\log n) = O(\log m/\log\log m). Therefore, trees require a number of edges that is factorial in the distance of Laplacian peak state transfer. A small number of cycles incorporated into an otherwise tree-like graph is insufficient to improve the asymptotics in question.

An exponential edge bound

We recall a helpful but standard definition.

Definition 4.6. An almost equitable partition of a graph GG is partition of its vertices π={V0,V1,…,Vl}\pi= \{V_0,V_1,\ldots,V_l\} such that every vertex vv in ViV_i has the same number of neighbors in Vi+1V_{i+1} and the same number of neighbors in Vi−1V_{i-1}.

We will write qi=1∣Vi∣∑v∈Vievq_i = \frac{1}{\sqrt{|V_i|}}\sum_{v\in V_i}e_v to mean the class indicators of π\pi, and Q=(q1 q2 ⋯ ql+1)Q=(q_1\ q_2\ \cdots\ q_{l+1}). We say that J=QTLQJ=Q^{\mathsf{T}}LQ is the symmetric compression of LL by π\pi. Finally, we will use a superscript JJ as EθJE_\theta^J to disambiguate the spectral decomposition of JJ from that of LL when both are of interest.

Equitable partitions of the vertices of a graph are also almost equitable. The notion of almost equitable partitions is particularly helpful in the case of Laplacian graph matrices because edges between vertices in the same class do not obstruct the desired compression.

Lemma 4.7. Let GG be a connected graph on nn vertices with Laplacian LL, and let π={V0,V1,…,Vd}\pi=\{V_0,V_1,\ldots,V_d\} be an almost equitable partition of the vertices of GG. Let J=QTLQJ=Q^{\mathsf{T}}LQ be the compression of LL by π\pi. If u∈V0u\in V_0 and v∈Vdv\in V_d satisfy d(u,v)=dd(u,v)=d and ev⁡L(u,v)⊆spec⁡(J)\operatorname{ev}_L(u,v)\subseteq\operatorname{spec}(J), then:

(i) spec⁡(J)={0=θ0<θ1<⋯<θd}\operatorname{spec}(J)=\{0=\theta_0<\theta_1<\cdots<\theta_d\} is simple, and ev⁡L(u,v)=spec⁡(J)\operatorname{ev}_L(u,v)=\operatorname{spec}(J).

(ii) If θ=θr\theta=\theta_r is an eigenvalue of LL, then

(Eθr)u,v=(−1)r∏i=1dθin∏j≠r∣θj−θr∣(E_{\theta_r})_{u,v}=\frac{(-1)^r\prod_{i=1}^{d}\theta_i}{n\prod_{j\ne r}|\theta_j-\theta_r|}

and (Eθ)u,v=0(E_\theta)_{u,v}=0 if θ\theta is not an eigenvalue of JJ.

(iii) there is Laplacian peak state transfer between uu and vv if and only if spec⁡(J)⊂Z\operatorname{spec}(J)\subset\mathbb{Z} and θr/g≡r(mod2)\theta_r/g\equiv r\pmod{2} for all rr, where g=gcd⁡(θ1,…,θd)g=\gcd(\theta_1,\ldots,\theta_d).

Proof. By construction, the column space of QQ is LL-invariant, and so LQ=QJLQ = QJ, and EθQ=QEθJE_{\theta}Q = QE^{J}_{\theta} for every θ\theta.

(i) Connectedness of GG implies that 00 is a simple eigenvalue of JJ with eigenvector ∑vev\sum_v e_v, whose spectral idempotent is nonvanishing in every entry, so ∣evL(u,v)∣≥d+1\lvert e_vL(u,v)\rvert\ge d+1 by Lemma 4.1. Since evL(u,v)⊂spec⁡(J)e_vL(u,v) \subset\operatorname{spec}(J) and ∣spec⁡(J)∣=d+1\lvert\operatorname{spec}(J)\rvert= d+1, we have that the sets must be equal and spec⁡(J)\operatorname{spec}(J) can contain only simple eigenvalues.

(ii) By (i), we must only show that the displayed formula is correct for θr\theta_r in spec⁡(J)\operatorname{spec}(J). To this end, we again consider the resolvent

[(L−θI)−1]u,v=α(θ)φJ(θ)=−∑k=0∞(Lk)u,vθk+1.[(L-\theta I)^{-1}]_{u,v} = \frac{\alpha(\theta)}{\varphi_J(\theta)} = -\sum_{k=0}^{\infty}\frac{(L^k)_{u,v}}{\theta^{k+1}}.

where φJ(θ)=∏r=0d(θr−θ)\varphi_J(\theta) = \prod_{r=0}^{d}(\theta_r-\theta) is the degree d+1d+1 characteristic polynomial of JJ and α(θ)\alpha(\theta) is some other polynomial of finite degree. Taking the limit θ→∞\theta\to\infty, we find that the right hand side becomes −(Ld)u,v/θd+1-(L^d)_{u,v}/\theta^{d+1} since uu and vv separated by distance dd. Since φJ(θ)\varphi_J(\theta) is degree d+1d+1, it follows that α(θ)\alpha(\theta) must be a constant. Connectedness and taking residues gives

(Eθ0)u,v=1n=α(θ)φJ′(0)=α(θ)∏r=1dθr.(E_{\theta_0})_{u,v} = \frac{1}{n} = \frac{\alpha(\theta)}{\varphi'_J(0)} = \frac{\alpha(\theta)}{\prod_{r=1}^{d}\theta_r}.

To get the displayed formula, solve for α(θ)\alpha(\theta) and recognize that φJ′(θr)=(−1)r∏j≠r∣θr−θj∣\varphi'_J(\theta_r) = (-1)^r\prod_{j\ne r}\lvert\theta_r-\theta_j\rvert.

(iii) Apply Corollary 2.3 with the supports in (ii); the peak value is ∑θ∣(Eθ)u,v∣\sum_{\theta}\lvert(E_{\theta})_{u,v}\rvert.

Lemma 4.7 constrains Laplacian peak state transfer at distance dd with the provision that there is some almost equitable partition consisting of d+1d+1 classes whose compression of LL is a lossless descriptor of the state transfer between the vertices of interest. It says nothing about Laplacian peak state transfer at distance dd when there does not exist any such almost equitable partition, even when there is an otherwise suitable almost equitable partition consisting of d+2d+2 classes. Furthermore, when some suitable partition is found such that Lemma 4.7 may be applied, the question of peak state transfer is entirely spectral and can be answered without directly addressing eigenvectors, otherwise unconditional on the details of the underlying structure. The trace arguments of Theorems 4.2 and 4.3 do not lend themselves to exploiting the aforementioned spectral rigidity; the only input from peak state transfer is to provide cancellation of cross terms and to bound the eigenvalue spacing away from zero.

In [8], Kay exploits the spectral rigidity provided by Corollary 2.3 to show that, under the condition that Lemma 4.1 is saturated, perfect state transfer can only occur in graphs with even maximum degree and over even distances.

Lemma 4.8 (of Kay [8]). Let θ0<θ1<⋯<θN−1\theta_0 < \theta_1 < \cdots< \theta_{N-1} be integers with N>3N > 3. Further suppose θr=r mod 2\theta_r = r \bmod2. Then, there exist integers α\alpha and β\beta such that

∑r=0N−11∏j≠r∣θr−θj∣=12β+1⋅2α.(11)\sum_{r=0}^{N-1}\frac{1}{\prod_{j\ne r}\lvert\theta_r-\theta_j\rvert} = \frac{1}{2\beta+1} \cdot2\alpha. \tag*{(11)}

We find that Lemma 4.7 together with Lemma 4.8 is sufficient to force an exponential number of edges under the additional assumption of the existence of a suitable distance partition. At the heart of the result is the dyadic structure resulting in the cancellation of factors of two from the denominator of (11), arising from the alternation in parity of eigenvalues provided by Corollary 2.3.

Theorem 4.9. Let GG be a connected graph on nn vertices with mm edges. If uu is a vertex of GG, the distance partition about uu is almost equitable, and there is Laplacian perfect state transfer between uu and some vertex vv at distance d>1d>1 from uu then,

m+1≥n≥2⌊d/2⌋+1.m+1\ge n\ge2^{\lfloor d/2\rfloor+1}.

Proof. Let π={{u}=V0,V1,…,Vd,Vd+1,…,Vρ}\pi=\{\{u\}=V_0,V_1,\ldots,V_d,V_{d+1},\ldots,V_\rho\} be the distance partition about uu where ρ\rho is the eccentricity of uu and let JJ be the symmetric compression of LL by π\pi. As JJ is a tridiagonal Jacobi matrix with endpoint corresponding to uu, no eigenvector of JJ may vanish on V0={u}V_0=\{u\} or the zero initial condition propagates through the recurrence, forcing the entire eigenvector to vanish. It follows that the eigenvalues of JJ are simple. Likewise, we have assumed perfect state transfer so

0=2(1−(BL)u,v)=∑θ∈spec⁡(L)((Eθ)u,u+(Eθ)v,v−2∣(Eθeu)T(Eθev)∣).0=2(1-(B_L)_{u,v})=\sum_{\theta\in\operatorname{spec}(L)}\left((E_\theta)_{u,u}+(E_\theta)_{v,v}-2\left|(E_\theta e_u)^{\mathsf T}(E_\theta e_v)\right|\right).

Every summand is nonnegative and bounded above by ∥Eθev−σEθeu∥\lVert E_\theta e_v-\sigma E_\theta e_u\rVert for σ=±1\sigma=\pm1. In order for every term to vanish, we must then have

∣(Eθ)u,v∣=∣(Eθ)u,u∣.\left|(E_\theta)_{u,v}\right|=\left|(E_\theta)_{u,u}\right|.

In particular, we have ev⁡L(u,v)=spec⁡(J)\operatorname{ev}_L(u,v)=\operatorname{spec}(J), and Vd={v}V_d=\{v\}.

In order to apply Lemma 4.7, we must first show that ρ=d\rho=d. To that end, suppose d<ρd<\rho, and define

X=∑j=d+1ρ∣Vj∣Y=∑j=0d−1∣Vj∣X=\sum_{j=d+1}^{\rho}|V_j| \qquad Y=\sum_{j=0}^{d-1}|V_j|
xi={∣Vi∣X0≤i<d,0i=d,−∣Vi∣Yd+1≤i≤ρ.x_i= \begin{cases} \sqrt{|V_i|}X & 0\le i<d,\\ 0 & i=d,\\ -\sqrt{|V_i|}Y & d+1\le i\le\rho. \end{cases}

Since JJ is a compression of LL, which is assumed to be connected and has a simple null vector, JJ also has a simple null vector given by

∑j=0ρ(J)i,j∣Vj∣=0.\sum_{j=0}^{\rho}(J)_{i,j}\sqrt{|V_j|}=0.

for all ii. Because 0=∑i=0dxi∣Vi∣0=\sum_{i=0}^{d}x_i\sqrt{|V_i|}, the vector with entries xix_i is orthogonal to the simple null vector of JJ. Moreover, ∑j(J)i,jxj\sum_j(J)_{i,j}x_j is nonzero only when ∣i−d∣≤1|i-d|\le1, JJ is tridiagonal, and xd=0x_d=0, so

∑i=0ρ(J)d−1,ixi=X((J)d−1,d−2∣Vd−2∣+(J)d−1,d−1∣Vd−1∣)=−X(J)d−1,d∣Vd∣\sum_{i=0}^{\rho}(J)_{d-1,i}x_i=X\left((J)_{d-1,d-2}\sqrt{|V_{d-2}|}+(J)_{d-1,d-1}\sqrt{|V_{d-1}|}\right)=-X(J)_{d-1,d}\sqrt{|V_d|}
∑i=0ρ(J)d+1,ixi=Y((J)d+1,d+2∣Vd+2∣+(J)d+1,d+1∣Vd+1∣)=−Y(J)d+1,d∣Vd∣,\sum_{i=0}^{\rho}(J)_{d+1,i}x_i=Y\left((J)_{d+1,d+2}\sqrt{|V_{d+2}|}+(J)_{d+1,d+1}\sqrt{|V_{d+1}|}\right)=-Y(J)_{d+1,d}\sqrt{|V_d|},

but ∣Vd∣=1|V_d|=1, and all vertices in ∣Vd±1∣|V_{d\pm1}| are adjacent to vv, so (J)d±1,d=−∣Vd±1∣(J)_{d\pm1,d}=-\sqrt{|V_{d\pm1}|}, and hence

∑i,j=0ρxi(J)i,jxj∑i=0ρxi2=∣Vd−1∣X2+∣Vd+1∣Y2XY2+YX2<1\frac{\sum_{i,j=0}^{\rho}x_i(J)_{i,j}x_j}{\sum_{i=0}^{\rho}x_i^2} =\frac{|V_{d-1}|X^2+|V_{d+1}|Y^2}{XY^2+YX^2}<1

where the inequality follows from ∣Vd−1∣<Y\lvert V_{d-1}\rvert< Y whenever d>1d > 1 and ∣Vd+1∣≤X\lvert V_{d+1}\rvert\le X since we have assumed ρ>d\rho> d. Now, the vector with entries xix_i must have overlap with some eigenvector whose eigenvalue is strictly between 0 and 1, since the null vector is simple and orthogonal to xix_i, and the inequality above is strict. Eigenvalues of JJ are eigenvalues of LL, and there are no integers in (0,1)(0,1), so spec⁡(J)=ev⁡L(u,v)\operatorname{spec}(J)=\operatorname{ev}_L(u,v) contains an irrational number, contradicting peak and thus perfect state transfer. In particular, we have that ρ=d\rho=d.

Now that we have confirmed ∣ev⁡L(u,v)∣=d+1\lvert\operatorname{ev}_L(u,v)\rvert=d+1, and that ev⁡L(u,v)⊂spec⁡(J)\operatorname{ev}_L(u,v)\subset\operatorname{spec}(J), Lemma 4.7 applies to give

(BL)u,v=∏i=1dθin∑r=0d(−1)r∏j≠r∣θr−θj∣(B_L)_{u,v}=\frac{\prod_{i=1}^{d}\theta_i}{n}\sum_{r=0}^{d}\frac{(-1)^r}{\prod_{j\ne r}\lvert\theta_r-\theta_j\rvert}

and θr/g=r mod 2\theta_r/g=r\bmod2 with g=gcd⁡(θ1,θ2,…,θd)g=\gcd(\theta_1,\theta_2,\ldots,\theta_d). Write λr=θr/g\lambda_r=\theta_r/g, integers of alternating parity, and rewrite

(BL)u,v=∏i=1dλin∑r=0d(−1)r∏j≠r∣λr−λj∣(B_L)_{u,v}=\frac{\prod_{i=1}^{d}\lambda_i}{n}\sum_{r=0}^{d}\frac{(-1)^r}{\prod_{j\ne r}\lvert\lambda_r-\lambda_j\rvert}

since factors of gg cancel. Then, Lemma 4.8 provides that there exist integers α\alpha and β\beta so that

(BL)u,v=∏i=1dλin2α2β+1.(B_L)_{u,v}=\frac{\prod_{i=1}^{d}\lambda_i}{n}\frac{2\alpha}{2\beta+1}.

Now, perfect state transfer is peak state transfer together with (BL)u,v=1(B_L)_{u,v}=1, so

n(2β+1)=2α∏i=1dλi.n(2\beta+1)=2\alpha\prod_{i=1}^{d}\lambda_i.

The right hand side has at least ⌊d/2⌋+1\lfloor d/2\rfloor+1 factors of two since λr≡r mod 2\lambda_r\equiv r\bmod2, and 2β+12\beta+1 is odd, so nn must be divisible by 2⌊d/2⌋+12^{\lfloor d/2\rfloor+1} and the bound is established after recognizing that m≥n−1m\ge n-1 for connected graphs on nn vertices.

To the best of our knowledge, Theorem 4.9 is the first such prohibition of perfect state transfer in a polynomial number of vertices or edges that does not demand to know the details of the underlying graph. We do not expect that the exponent of Theorem 4.9 is tight or even nearly so. There are several prospective routes toward constructing graphs with Laplacian perfect state transfer in a polynomial number of edges that are ruled out by Theorem 4.9. The first of these is that by identifying sets of vertices in a hypercube, one might be able to effectively remove all but polynomially many edges while preserving the compression of the Laplacian and the arithmetic structure therein. Secondly, one might hope more generally to find a graph with exponentially many edges whose compression under some almost equitable partition admits the desired transfer properties, and then ‘unfold’ the compression into some graph with only polynomially many vertices.

A Laplacian family with polynomially many edges

Now, we introduce a family of graphs that will aid us in assessing the tightness of Theorem 4.3.

Definition 4.10. For positive integers b0,b1,…,bdb_0,b_1,\ldots,b_d, construct the chain C(b0,b1,…,bd)C(b_0,b_1,\ldots,b_d) consisting of d+1d+1 pairwise disjoint vertex sets ViV_i of size bib_i with i=0,1,…,di=0,1,\ldots,d such that vertices u∈Viu\in V_i and v∈Vjv\in V_j are adjacent whenever ∣i−j∣=1\lvert i-j\rvert=1.

The chain C(b0,b1,…,bd)C(b_0,b_1,\ldots,b_d) has n=∑i=0dbin=\sum_{i=0}^{d}b_i vertices and m=∑i=0d−1bibi+1m=\sum_{i=0}^{d-1}b_i b_{i+1} edges. If u∈Viu\in V_i and v∈Vjv\in V_j, then d(u,v)=∣i−j∣d(u,v)=|i-j| when i≠ji\ne j, and d(u,v)=2d(u,v)=2 when i=ji=j. For chains, we will use the equitable partition π={Vi}i=0d\pi=\{V_i\}_{i=0}^{d}, and its compression of LL. Explicitly, we write

J=(b1−b0b1−b0b1b0+b2−b1b2−b1b2⋱⋱⋱bd+bd−2−bd−1bd−bd−1bdbd−1).J=\begin{pmatrix} b_1 & -\sqrt{b_0b_1} & & & \\ -\sqrt{b_0b_1} & b_0+b_2 & -\sqrt{b_1b_2} & & \\ & -\sqrt{b_1b_2} & \ddots& \ddots& \\ & & \ddots& b_d+b_{d-2} & -\sqrt{b_{d-1}b_d}\\ & & & -\sqrt{b_{d-1}b_d} & b_{d-1} \end{pmatrix}.

with rows and columns corresponding to the classes of the chain.

If uu and vv are distinct vertices in ViV_i, then L(eu−ev)=deg⁡(u)(eu−ev)L(e_u-e_v)=\deg(u)(e_u-e_v), so the only vector with support purely on ViV_i that can walk down the chain is orthogonal to every such difference. In other words, the only eigenvectors of LL with support on vertices from distinct classes are in the cyclic subspace of the class indicator vectors and ev⁡L(u,v)⊂spec⁡(J)\operatorname{ev}_L(u,v)\subset\operatorname{spec}(J) whenever uu and vv are in different classes. This observation will allow us to use Lemma 4.7 repeatedly.

Theorem 4.11. For every d≥1d\ge1 and 0≤i≤d0\le i\le d, define

bi=12(i+1)(2d+2−i),b_i=\frac{1}{2}(i+1)(2d+2-i),

and Pd=C(b0,b1,…,bd)P_d=C(b_0,b_1,\ldots,b_d). Then,

  1. spec⁡(J)={r(2r+3):0≤r≤d}\operatorname{spec}(J)=\{r(2r+3):0\le r\le d\}

  1. PdP_d admits Laplacian peak state transfer between any vertex uu in V0V_0 and any vv in VdV_d at every odd multiple of t=πt=\pi with amplitude

(BL)u,v=4Γ(5/4)πΓ(d+3/2)(d+1)(d+2)Γ(d+5/4)(B_L)_{u,v}=\frac{4\Gamma(5/4)}{\sqrt{\pi}}\frac{\Gamma(d+3/2)}{(d+1)(d+2)\Gamma(d+5/4)}
  1. The number of edges is m=1120d(d+1)(d+2)(16d2+57d+47)m=\frac{1}{120}d(d+1)(d+2)(16d^2+57d+47)

Proof. Clearly, the hypotheses of Lemma 4.7 apply, so it suffices to compute spec⁡(J)\operatorname{spec}(J). That is,

θϕ(i)=(bi−1+bi+1)ϕ(i)−bibi−1ϕ(i−1)−bibi+1ϕ(i+1)(12)\theta\phi(i)=(b_{i-1}+b_{i+1})\phi(i)-\sqrt{b_i b_{i-1}}\phi(i-1)-\sqrt{b_i b_{i+1}}\phi(i+1) \tag*{(12)}

where, for convenience, we set b−1=bd+1=0b_{-1}=b_{d+1}=0. Pursuant to this goal, we write ϕ(i)=ψ(i)bi\phi(i)=\psi(i)\sqrt{b_i}, and find

θψ(i)=bi+1(ψ(i)−ψ(i+1))+bi−1(ψ(i)−ψ(i−1)).\theta\psi(i)=b_{i+1}(\psi(i)-\psi(i+1))+b_{i-1}(\psi(i)-\psi(i-1)).

Define N=2d+2\mathcal{N}=2d+2, Bi=(i+1)(N−i)/2B_i=(i+1)(\mathcal{N}-i)/2 for 0≤i≤N−10\le i\le\mathcal{N}-1 so that Bi=bN−1−i=biB_i=b_{\mathcal{N}-1-i}=b_i for i≤di\le d, and Bd+1=Bd=bdB_{d+1}=B_d=b_d. We now extend (12) into a restriction of a finite difference operator with polynomial coefficients by defining F(i)=Bi+1F(i)=B_{i+1}, and H(i)=Bi−1H(i)=B_{i-1}. Namely,

(Lψ)(i)=F(i)(ψ(i)−ψ(i+1))+H(i)(ψ(i)−ψ(i−1)).(13)(L\psi)(i)=F(i)(\psi(i)-\psi(i+1))+H(i)(\psi(i)-\psi(i-1)). \tag*{(13)}

Since F(N−1)=H(0)=0F(\mathcal{N}-1)=H(0)=0, and LL is reflection symmetric about i=(N−1)/2i=(\mathcal{N}-1)/2, the even eigenfunctions of LL exactly determine the eigenvectors of JJ. The palindromic extension is necessary on the grounds that JJ itself is a difference operator that fails to have polynomial coefficients. All that remains to find the spectrum of JJ is to note that L\mathcal{L} is triangular with respect to polynomials; if f(i)f(i) is a polynomial of degree kk, then Lf\mathcal{L}f is also. In particular,

Lik=k(H(i)−F(i))ik−1−(k2)(H(i)+F(i))ik−2+⋯\mathcal{L}i^k = k(H(i)-F(i))i^{k-1} - \binom{k}{2}(H(i)+F(i))i^{k-2}+\cdots

so the eigenvalues of L\mathcal{L} are exactly the coefficients of iki^k in Lik\mathcal{L}i^k, which are k(k+3)/2k(k+3)/2. For k=0k=0, the eigenfunction is constant and therefore even, and eigenfunctions alternate in their parity because the centered monomials (i−(N−1)/2)k(i-(N-1)/2)^k are even under the reflection symmetry of L\mathcal{L} exactly when kk is even. Finally, spec⁡(J)={r(2r+3):0≤r≤d}\operatorname{spec}(J)=\{r(2r+3):0\le r\le d\}. Consecutive eigenvalues in sorted order differ by an odd number, so Lemma 4.7 (iii) provides peak state transfer.

Turning our attention toward the transfer amplitude, we write

Cd:=∏i=1d−1bi=d!(2d+1)!2d−1(d+2)!.C_d:=\prod_{i=1}^{d-1}b_i=\frac{d!(2d+1)!}{2^{d-1}(d+2)!}.

and

(BL)u,v=Cd∑r=0d1∏s≠r∣θr−θs∣(B_L)_{u,v}=C_d\sum_{r=0}^{d}\frac{1}{\prod_{s\ne r}|\theta_r-\theta_s|}

by Lemma 4.7 (ii). Since θr−θs=(r−s)(2r+2s+3)\theta_r-\theta_s=(r-s)(2r+2s+3), the beta integral and binomial theorem yield

(BL)u,v=Cd2d+1(d!)2∫01t1/2(1−t)d(1+t)d−1(3+(4d+3)t) dt.(B_L)_{u,v}=\frac{C_d}{2^{d+1}(d!)^2}\int_0^1t^{1/2}(1-t)^d(1+t)^{d-1}(3+(4d+3)t)\,dt.

The integrand can be rewritten as

t1/2(1−t)d(1+t)d−1(3+(4d+3)t)=2ddt[t3/2(1−t2)d]+4dt3/2(1−t2)d−1,t^{1/2}(1-t)^d(1+t)^{d-1}(3+(4d+3)t)=2\frac{d}{dt}\left[t^{3/2}(1-t^2)^d\right]+4dt^{3/2}(1-t^2)^{d-1},

so integration by parts yields

(BL)u,v=4Γ(5/4)πΓ(d+3/2)(d+1)(d+2)Γ(d+5/4),(B_L)_{u,v}=\frac{4\Gamma(5/4)}{\sqrt{\pi}}\frac{\Gamma(d+3/2)}{(d+1)(d+2)\Gamma(d+5/4)},

as desired. Finally, (iii) is trivial counting.

For d=1d=1, P1P_1 has g=5g=5, and transfer times equal to odd multiples of π/5\pi/5. For d>1d>1, PdP_d has g=1g=1, so we have not included this fact about P1P_1 in the statement of Theorem 4.11.

For chains, the optimal lower bound for mm as a function of dd is somewhere between Ω(d2)\Omega(d^2) and Ω(d5)\Omega(d^5), while Theorem 4.3 provides only m=Ω(d2)m=\Omega(d^2). While Theorem 4.3 may or may not be tight across the set of general graphs, it seems unlikely to be tight on the set of chains. Nonetheless, of the previously known families of graphs exhibiting Laplacian peak state transfer at variable distance dd, all have m=Ω(ed)m=\Omega(e^d). See e.g. [9, 10].

The graphs PdP_d exhibit Laplacian peak state transfer across their diameter while having only polynomially many vertices and edges. Theorem 4.9 says that Laplacian perfect state transfer across the diameter of a graph with an almost equitable partition requires at least exponentially many edges. This is not precisely an exponential separation between peak and perfect state transfer in general, as the graphs PdP_d do not have almost equitable distance partitions about any particular vertex that is not in a singleton class. Nonetheless, Laplacian perfect state transfer across the diameter of a chain costs exponentially many edges, while Laplacian peak state transfer across the diameter of a chain costs only polynomially many edges.

Remark 4.12. The known families exhibiting peak state transfer at arbitrary distance with the fewest edges, Yn=C(n,1,n−1,2,…,2,n−1,1,n)Y_n = C(n,1,n-1,2,\ldots,2,n-1,1,n) in the adjacency case, and PdP_d introduced in Theorem 4.11 in the Laplacian case are both chains.

Remark 4.13. If a chain C(b0,b1,…,bd)C(b_0,b_1,\ldots,b_d) is palindromic in the sense that bi=bd−ib_i=b_{d-i} for each ii, and further there is some bj=1b_j=1, then the vertex in the singleton VjV_j and its mirror copy in Vj−dV_{j-d} are strongly cospectral, and JJ is persymmetric (likewise in the case of the adjacency matrix). Additionally, YnY_n has a pair of singleton classes, yielding a pair of strongly cospectral vertices that both admit adjacency peak state transfer to some vertex other than the strongly cospectral partner. Apparently, peak state transfer between a pair of vertices uu and vv at distance dd is only polynomially expensive, even assuming that uu is strongly cospectral to some other vertex ww. Hence, unconditional improvements to the m=Ω(D3)m=\Omega(D^3) bound on perfect state transfer must come from the cost of strong cospectrality and peak state transfer between the same pair of vertices, not just their presence in the same graph, if they are true at all.

Conclusion

We have shown that peak state transfer with respect to Laplacian or adjacency matrices requires and can be accomplished by graphs with a number of edges only polynomial in the distance. Additionally, we find, by a divisibility argument, that Laplacian perfect state transfer across the diameter of a graph cannot be accomplished without an exponential number of vertices.

In contrast, trees require a superexponential number of edges for Laplacian peak state transfer. We classify all of the trees admitting Laplacian peak state transfer between some pair of vertices assuming diameter four or less, and find that there is only a single two-parameter, balanced, and rooted family. Beyond diameter four, we find examples lacking balance, and at greater distances.

Toward a full classification of Laplacian peak state transfer trees, it is natural to ask whether trees are compatible with peak state transfer at any distance. In particular, is there some distance d∗d^* beyond which Laplacian peak state transfer cannot occur in a tree? We suspect that there is not.

The family of graph that we introduce in Theorem 4.11, PdP_d, has a transfer amplitude (BL)u,v=O(d−7/4)(B_L)_{u,v}=O(d^{-7/4}) that tends to 00 as dd increases. It is unclear whether a polynomial number of edges is compatible with a Laplacian peak state transfer amplitude bounded away from zero. A negative resolution would preclude Laplacian perfect state transfer in a polynomial number of edges.

Furthermore, we were able to show m=Ω(d2)m=\Omega(d^2) is required for Laplacian peak state transfer at distance dd but could only construct couples with m=Θ(d5)m=\Theta(d^5). A natural next question is to attempt to either improve the lower bound for mm or to construct examples with fewer edges.

Finally, we have proven that Laplacian perfect state transfer requires an exponentially large graph under the additional assumption that the distance partition about one of the vertices is almost equitable. We regard Theorem 4.9 as a step toward a more general and tighter constraint on the size of a graph with Laplacian perfect state transfer at some distance. Theorem 4.9 forbids perfect state transfer across the diameter of a chain in a polynomial graph size. Perhaps Laplacian perfect state transfer in chains can be forbidden outright by identifying some obstruction to perfect state transfer properly within some chain. Finally, we conjecture that Theorem 4.9 is not tight, and can be improved to m≥2d+o(1)m \ge2^{d+o(1)}.

Acknowledgments

We are grateful to Gabriel Coutinho for reading a very early version of this paper, and suggesting that some classification of Laplacian peak state transfer of trees may be possible. We acknowledge the use of AI tools to brainstorm, check proofs, and implement numerical tests of the claims we present. We take full responsibility for the contents herein.

We acknowledge support from the Co-design Center for Quantum Advantage (C²QA) under Contract No. DE-SC0012704.

Princeton University Professor Andrew Houck is also a consultant for Quantum Circuits Incorporated (QCI). Due to his income from QCI, Princeton University has a management plan in place to mitigate a potential conflict of interest that could affect the design, conduct and reporting of this research.

References

References

  1. [1]S. Bose, Quantum communication through an unmodulated spin chain, Physical Review Letters 91, 207901 (2003).pubmed.ncbi.nlm.nih.gov/14683398
  2. [2]C. Godsil, When can perfect state transfer occur? (2011), arXiv:1011.0231 [math.CO].arxiv.org/abs/1011.0231
  3. [3]G. Coutinho, K. Guo, and V. Schmeits, Peak state transfer in continuous quantum walks (2025), arXiv:2505.11986 [quant-ph].arxiv.org/abs/2505.11986
  4. [4]G. Coutinho, Quantum walks and the size of the graph, Discrete Mathematics 342, 2765–2769 (2019).DOI
  5. [5]G. Coutinho, E. Juliano, and T. J. Spier, No perfect state transfer in trees with more than 3 vertices, Journal of Combinatorial Theory, Series B 168, 68 (2024).arxiv.org/abs/2305.10199
  6. [6]G. Coutinho and H. Liu, No Laplacian perfect state transfer in trees, SIAM Journal on Discrete Mathematics 29, 2179–2188 (2015).
  7. [7]W. N. Anderson, Jr. and T. D. Morley, Eigenvalues of the Laplacian of a graph, Linear and Multilinear Algebra 18, 141 (1985).
  8. [8]A. Kay, The perfect state transfer graph limbo (2018), arXiv:1808.00696 [quant-ph].arxiv.org/abs/1808.00696
  9. [9]H. Zhan, An infinite family of circulant graphs with perfect state transfer in discrete quantum walks, Quantum Information Processing 18, 369 (2019).arxiv.org/abs/1707.06703
  10. [10]Y. Ge, B. Greenberg, O. Perez, and C. Tamon, Perfect state transfer, graph products, and equitable partitions, International Journal of Quantum Information 09, 823 (2011).arxiv.org/abs/1009.1340

Paper details

vlnc:W_nyzrp4b9
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

AI tools

View statement
Looking for related papers…
Contents