WorksMathematics
Peak state transfer in trees and the cost of distance
Abstract
There is peak state transfer between vertices and in a graph if there exists a time for which saturates the triangle inequality imposed by its spectral decomposition and is either the adjacency or Laplacian matrix. We show that peak state transfer at distance requires edges in the adjacency case, 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 and edges, showing that peak state transfer is achievable in a polynomial graph size. In contrast, Laplacian perfect state transfer costs at least edges when the distance partition of vertices around one vertex is almost equitable. Finally, we show that Laplacian peak state transfer in trees requires edges, and we characterize all trees of diameter 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 at some known time for either the adjacency or Laplacian matrix of a graph? This problem is called perfect state transfer [2].
Let be the Laplacian matrix of a connected graph , with spectral decomposition over distinct eigenvalues . Following [3], the bounding matrix is where denotes entrywise absolute values. By the triangle inequality, for all times . If there exists some time for which the inequality is saturated for some pair of vertices and , we say that there is Laplacian peak state transfer between and . We may likewise define adjacency peak state transfer.
If , we say that and 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 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 admits peak state transfer between and at distance and has edges, find a bound for in terms of .
We provide in the Laplacian peak state transfer case, and furnish a family of graphs with , 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 . Furthermore, we show that Laplacian perfect state transfer across the diameter of a graph between vertices whose distance partitions are equitable requires 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 . The latter bound is tight to leading order in 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 .
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 have 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 , we write to mean that is nontrivial. When the sorted order of eigenvalues is important, we index eigenvalues by their sorted order as , and otherwise omit the subscript. We write to mean the entries of .
We recall definitions from [3], which will be necessary throughout. For a symmetric matrix with spectral idempotents , the positive and negative mutual eigenvalue supports are
and . Likewise, we write . is eligible if consists of algebraic integers and is closed under algebraic conjugation. If is either the Laplacian or adjacency matrix of a graph and and are vertices of that graph, then is eligible.
For real time ,
by the triangle inequality. We define and say that there is peak state transfer between and with respect to if there exists a time at which or equivalently when (1) is saturated.
We recall a helpful fact about resolvent matrices.
Lemma 2.1. Let be a symmetric matrix with spectral idempotents . As rational functions,
In particular, has only simple poles, its pole set is exactly , and
If the entry is written in lowest terms as , then .
A pair of results of Coutinho, Guo, and Schmeits relate the admission of peak state transfer to the arithmetic of the spectrum of , which we will use repeatedly.
Theorem 2.2 (Coutinho-Guo-Schmeits [3] Theorem 5.3). Let be a symmetric matrix and let be vertices with eligible and nonempty. There is peak state transfer between and with respect to if and only if:
(i) every eigenvalue in is a quadratic integer: there exist a squarefree integer , an integer , and for each an integer of the same parity as , such that
(ii) fixing and setting
is even if and only if , and odd if and only if .
If these hold, peak state transfer occurs precisely at all odd multiples of , with phase factor .
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 be the Laplacian matrix of a connected graph . There is peak state transfer between distinct vertices and with respect to if and only if:
(i) every is an integer
(ii) with , for all : is even if and only if , and odd if and only if .
If these hold, peak state transfer occurs precisely at all odd multiples of with phase factor .
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 . Finally, the integrality of elements of 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 be a tree and its centre, or root.
Definition 2.4. Define the grounded Laplacian and grounded Weyl function as
respectively. For rooted trees with root , we abbreviate to mean the grounded Weyl function of the subtree of rooted at .
The matrix is the principal submatrix of the Laplacian matrix of a hypothetically extant tree with as a rooted subtree. This idea leads to the following recurrence relation:
Lemma 2.5. Let be the root of a tree , and label the neighbors of as . Then, we have
and and . If contains only , then we have .
Proof. Write
and observe that admits a partition
where , and then the Sherman-Morrison-Woodbury formula provides
and .
For singleton graphs, , , and are obvious. If , then . Finally, , so a similar recurrence gives . □
It will be useful to define the function, for integer ,
which appears repeatedly since
Moreover, we will denote the solutions of as
which are irrational whenever and positive, satisfying .
Lemma 2.6. Again, suppose are the neighbors of , which root their own subtrees . Set
If is some vertex in and the unique path from to traverses vertices , then as rational functions,
Moreover, , and off the poles. Finally, .
Proof. The first equality can be acquired in a way analogous to Lemma 2.5. To get the second, again recall , , and consider the partitioned form of
again by the Sherman–Morrison–Woodbury formula. Furthermore,
where we write to mean the subtree rooted at for some , a neighbor of along the path from to . Repeating this procedure, we find that
where now is the subtree rooted at . Continue until reaching , at which point the product terminates. To see that , observe that by Lemma 2.5, away from poles, and similarly follow from .
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 and positive integers and accompanying pairwise distinct and each positive. Construct the tree by attaching to , which we call the root, children who each have 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 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 vertices of degree , 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 with root , we have
if , and
if $b_1 = 0.
Proof. We use Lemma 2.5 together with (2).
Shallow trees are not generally pairwise nonisomorphic; for example . 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 a shallow tree, Laplacian peak state transfer between any pair of vertices is forbidden whenever .
Proof. Since , Lemma 3.2 tells us that has poles at if and in , which are pairwise distinct since the ’s are. Let be the two smallest such poles of , which must exist as . Lemma 2.6 shows that , and away from the poles of , so on and it furthermore runs monotonically from to on , and hence has exactly one zero in , say . is a root of the monic integral characteristic polynomial of and hence an algebraic integer, and the only rational algebraic integers are ordinary integers, of which there are none in , so is irrational.
For each adjacent to with children, we have that since is strictly between and . Likewise is neither a pole nor a zero of . is a simple zero of since by Lemma 2.6, and no has a pole or zero there—which was established in the preceding sentence—so is a pole of every resolvent entry in the row, and for every vertex not equal to by Lemma 2.1.
If had multiplicity one could choose an eigenvector with ; then restricts on some subtree to a null vector of , and , so is a pole or a zero of , a contradiction. Hence, is a simple eigenvalue whose eigenvector is nowhere vanishing because is nowhere vanishing. Therefore, is an element of 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 and with . 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 and instead simply write . 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 .
The fact that 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 be a shallow, balanced tree with , and root . If and are distinct from each other and from , there is an irrational number in , and hence peak state transfer between and is forbidden.
Proof. As in the proof of Proposition 3.3, we note that is a pole of for each neighbor of , and in turn a pole of , and not a pole of . Therefore, by Lemma 2.1 and hence every eigenvector vanishes on , and any eigenvector is restricted to on the subtree rooted by . Moreover,
so is one-dimensional and spanned by since . Finally, since eigenvectors vanish on , their coefficients must sum to zero, so we have that
where the matrix is understood to vanish on the row and column. Hence, is nonvanishing for every and distinct from , and contains , necessarily irrational. Corollary 2.3 then forbids Laplacian peak state transfer. □
We note that the assumption precludes and precludes , 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 be a balanced, shallow tree. There is Laplacian peak state transfer between the root and some other vertex if and only if there exist integers of opposite parity and such that and . If is odd and even, there is peak state transfer from root to child with amplitude . If instead is the odd one, there is peak state transfer from root to leaf with amplitude .
Proof. Throughout, let be the root, any child of the root, and any leaf. From Lemma 3.2, we have
while (2) gives
and trivially . Combining the three with Lemma 2.6 gives
In either case, the poles are, by Lemma 2.1,
with and
and is equivalent to the requirement that is a perfect square since and a perfect square that is even is also divisible by four. Write
and rearrange to see that , which are of the same parity, and even since is assumed to be an integer. Write
and note that , so we have further that
where we note that the choice of sign in the quadratic formula is the choice that distinguishes from , and the choice is unimportant. Clearly and impose and . In terms of and , we have
and thus we recognize that
so, in particular, and cannot both be even, and are both odd when and have the same parity. Hence, is odd, and we now need only to check the hypothesis of Corollary 2.3. Using Lemma 2.1 again, we find,
Hence, the balanced shallow trees that admit Laplacian peak state transfer are precisely those for which and have opposite parity, namely those for which and have opposite parity, by (11).
Finally, we use Lemma 2.1 once more to get the transfer amplitudes. If is odd and even, there is Laplacian peak state transfer from root to child with amplitude
When is odd and even, the peak state transfer is from root to leaf with amplitude
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 which hosts peak state transfer from root to each child at amplitude . 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 admits adjacency peak state transfer from each child of the root to the adjacent leaf for with amplitude as . 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 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 if and only if is either a star or a balanced rooted tree for some pair of integers and 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 with root and a neighbor of . Then,
so
and Lemma 2.1 then gives , and 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 and at time , and there is perfect state transfer from to at time , then . 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 are no longer straightforwardly enumerable from the degrees of the neighbors of . 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 in ) 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 and 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 , , , and with , and . Construct the tree with root such that has children that are the root of their own subtree and children that are the root of a subtree.
Proposition 3.10. The trees have Laplacian peak state transfer between the root and each of its neighbors of degree for every positive integer , with peak amplitude
Proof. Throughout, we will suppose is some neighbor of of degree , and is some neighbor of of degree . We proceed by again using the grounded Weyl functions. From Lemma 3.2, we have
with . Hence, we have
by Lemma 2.5. Now, using Lemma 2.6, we find
We note that, a priori, (4) is a ratio of polynomials of degree , but in practice, it is the ratio of a quadratic with a quartic. This simplicity comes from two sources: First, the neighbors of root balanced subtrees, meaning that the Weyl functions and are of lower degree than the generic diameter four case. Secondly, and have the common denominator . These two facts conspire together to induce a cancellation of in the entry of the resolvent that we calculate.
Specializing now to , , , and , we find
The denominator factors as , while the numerator is and has only irrational roots , so the poles of (5) are precisely the roots of and therefore .
Finally, we invoke Lemma 2.1 to find
and
Combining (6) and (7) as , we produce the matrix elements of the spectral idempotents
is even while and are odd, so must be odd, and hence has the same parity as for in , and (8) shows that in is odd exactly when . Explicitly,
Hence, Corollary 2.3 provides Laplacian peak state transfer between and .
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 achieved at . Notably, , 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 with root by affixing vertices adjacent to that each root their own subtree. When , , and , there is Laplacian peak state transfer from to every vertex of degree at every odd multiple of .
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 to some leaf. Suppose that a path from to a leaf consists of the vertices , , and with a leaf and adjacent to . Then,
and we calculate
where the first equality is Lemma 2.6. Writing
with distinct by construction, we conclude that where is equivalent to the desired result by Lemma 2.1 and Corollary 2.3. Since is cubic with three distinct real roots, we can produce a formula for in terms of trigonometric functions of , , and .
Specializing now to the case at hand, we find , , implies which have 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 , not necessarily a tree. The machinery that drives the two theorems of this section is the following elementary lemma:
Lemma 4.1. Let be a symmetric matrix such that for . Either or .
Proof. Write and suppose . Since for , the invertible Vandermonde system in distinct eigenvalues forces for all , so is empty.
By relating the number of distinct eigenvalues in to the transfer distance, we can relate the number of edges in a graph to the eigenvalues of either or via the trace of or .
Edge count bounds
Theorem 4.2. Let be a simple graph with edges admitting peak state transfer with respect to its adjacency matrix between vertices at distance . Then,
Proof. Each in is an eigenvalue of of multiplicity at least one, and , so by Lemma 4.1. By Theorem 2.2, as above. If , consists of distinct integers. If is odd, then
and otherwise we have
Hence,
On the other hand, if , is eligible and thus is closed under algebraic conjugation, so , and
where we have used , and the fixed parity of to invoke
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 exhibiting peak state transfer with respect to their adjacency matrices at distance containing edges, and hence the only possible improvements to Theorem 4.2 must come at order or lower.
Theorem 4.3. Let be a simple graph with edges admitting Laplacian peak state transfer between vertices at distance . Then,
Proof. By Corollary 2.3 and Lemma 4.1, consists of at least distinct integers (of which must be positive) and integers alone. Moreover, the sum of distinct positive integers is at least . Hence, we have
In [4], the authors prove that perfect state transfer in a graph of diameter requires at least 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 , which are weaker than bounds in terms of the graph diameter.
The ingredients of Theorem 4.3 are the fully integral 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, , is the same as its first Betti number.
Proposition 4.4. In the setting of Theorem 4.3, with maximum vertex degree , has a vertex of degree at least and cycle rank at least .
Proof. The maximum eigenvalue of is at least since contains an integer at least . On the other hand, the maximum eigenvalue is bounded above by [7].
Write to mean the characteristic polynomial of which is integral and monic, and which is likewise integral and monic by Corollary 2.3. Because exact factorization of monic integral polynomials preserves integer coefficients, is integral and monic, and hence its evaluation at is a nonzero integer. Therefore the product of nonzero eigenvalues of outside of with multiplicity is at least one. By the matrix-tree theorem, we have immediately
which produces the desired result after using the definition of the cycle rank and the fact that each spanning tree is acquired from by deleting some number of edges, so
Remark 4.5. For trees in particular, Proposition 4.4 specializes to
or . 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 is partition of its vertices such that every vertex in has the same number of neighbors in and the same number of neighbors in .
We will write to mean the class indicators of , and . We say that is the symmetric compression of by . Finally, we will use a superscript as to disambiguate the spectral decomposition of from that of 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 be a connected graph on vertices with Laplacian , and let be an almost equitable partition of the vertices of . Let be the compression of by . If and satisfy and , then:
(i) is simple, and .
(ii) If is an eigenvalue of , then
and if is not an eigenvalue of .
(iii) there is Laplacian peak state transfer between and if and only if and for all , where .
Proof. By construction, the column space of is -invariant, and so , and for every .
(i) Connectedness of implies that is a simple eigenvalue of with eigenvector , whose spectral idempotent is nonvanishing in every entry, so by Lemma 4.1. Since and , we have that the sets must be equal and can contain only simple eigenvalues.
(ii) By (i), we must only show that the displayed formula is correct for in . To this end, we again consider the resolvent
where is the degree characteristic polynomial of and is some other polynomial of finite degree. Taking the limit , we find that the right hand side becomes since and separated by distance . Since is degree , it follows that must be a constant. Connectedness and taking residues gives
To get the displayed formula, solve for and recognize that .
(iii) Apply Corollary 2.3 with the supports in (ii); the peak value is .
Lemma 4.7 constrains Laplacian peak state transfer at distance with the provision that there is some almost equitable partition consisting of classes whose compression of is a lossless descriptor of the state transfer between the vertices of interest. It says nothing about Laplacian peak state transfer at distance when there does not exist any such almost equitable partition, even when there is an otherwise suitable almost equitable partition consisting of 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 be integers with . Further suppose . Then, there exist integers and such that
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 be a connected graph on vertices with edges. If is a vertex of , the distance partition about is almost equitable, and there is Laplacian perfect state transfer between and some vertex at distance from then,
Proof. Let be the distance partition about where is the eccentricity of and let be the symmetric compression of by . As is a tridiagonal Jacobi matrix with endpoint corresponding to , no eigenvector of may vanish on or the zero initial condition propagates through the recurrence, forcing the entire eigenvector to vanish. It follows that the eigenvalues of are simple. Likewise, we have assumed perfect state transfer so
Every summand is nonnegative and bounded above by for . In order for every term to vanish, we must then have
In particular, we have , and .
In order to apply Lemma 4.7, we must first show that . To that end, suppose , and define
Since is a compression of , which is assumed to be connected and has a simple null vector, also has a simple null vector given by
for all . Because , the vector with entries is orthogonal to the simple null vector of . Moreover, is nonzero only when , is tridiagonal, and , so
but , and all vertices in are adjacent to , so , and hence
where the inequality follows from whenever and since we have assumed . Now, the vector with entries must have overlap with some eigenvector whose eigenvalue is strictly between 0 and 1, since the null vector is simple and orthogonal to , and the inequality above is strict. Eigenvalues of are eigenvalues of , and there are no integers in , so contains an irrational number, contradicting peak and thus perfect state transfer. In particular, we have that .
Now that we have confirmed , and that , Lemma 4.7 applies to give
and with . Write , integers of alternating parity, and rewrite
since factors of cancel. Then, Lemma 4.8 provides that there exist integers and so that
Now, perfect state transfer is peak state transfer together with , so
The right hand side has at least factors of two since , and is odd, so must be divisible by and the bound is established after recognizing that for connected graphs on 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 , construct the chain consisting of pairwise disjoint vertex sets of size with such that vertices and are adjacent whenever .
The chain has vertices and edges. If and , then when , and when . For chains, we will use the equitable partition , and its compression of . Explicitly, we write
with rows and columns corresponding to the classes of the chain.
If and are distinct vertices in , then , so the only vector with support purely on that can walk down the chain is orthogonal to every such difference. In other words, the only eigenvectors of with support on vertices from distinct classes are in the cyclic subspace of the class indicator vectors and whenever and are in different classes. This observation will allow us to use Lemma 4.7 repeatedly.
Theorem 4.11. For every and , define
and . Then,
admits Laplacian peak state transfer between any vertex in and any in at every odd multiple of with amplitude
The number of edges is
Proof. Clearly, the hypotheses of Lemma 4.7 apply, so it suffices to compute . That is,
where, for convenience, we set . Pursuant to this goal, we write , and find
Define , for so that for , and . We now extend (12) into a restriction of a finite difference operator with polynomial coefficients by defining , and . Namely,
Since , and is reflection symmetric about , the even eigenfunctions of exactly determine the eigenvectors of . The palindromic extension is necessary on the grounds that itself is a difference operator that fails to have polynomial coefficients. All that remains to find the spectrum of is to note that is triangular with respect to polynomials; if is a polynomial of degree , then is also. In particular,
so the eigenvalues of are exactly the coefficients of in , which are . For , the eigenfunction is constant and therefore even, and eigenfunctions alternate in their parity because the centered monomials are even under the reflection symmetry of exactly when is even. Finally, . 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
and
by Lemma 4.7 (ii). Since , the beta integral and binomial theorem yield
The integrand can be rewritten as
so integration by parts yields
as desired. Finally, (iii) is trivial counting.
For , has , and transfer times equal to odd multiples of . For , has , so we have not included this fact about in the statement of Theorem 4.11.
For chains, the optimal lower bound for as a function of is somewhere between and , while Theorem 4.3 provides only . 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 , all have . See e.g. [9, 10].
The graphs 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 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, in the adjacency case, and introduced in Theorem 4.11 in the Laplacian case are both chains.
Remark 4.13. If a chain is palindromic in the sense that for each , and further there is some , then the vertex in the singleton and its mirror copy in are strongly cospectral, and is persymmetric (likewise in the case of the adjacency matrix). Additionally, 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 and at distance is only polynomially expensive, even assuming that is strongly cospectral to some other vertex . Hence, unconditional improvements to the 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 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, , has a transfer amplitude that tends to as 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 is required for Laplacian peak state transfer at distance but could only construct couples with . A natural next question is to attempt to either improve the lower bound for 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 .
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]S. Bose, Quantum communication through an unmodulated spin chain, Physical Review Letters 91, 207901 (2003).pubmed.ncbi.nlm.nih.gov/14683398
- [2]C. Godsil, When can perfect state transfer occur? (2011), arXiv:1011.0231 [math.CO].arxiv.org/abs/1011.0231
- [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]G. Coutinho, Quantum walks and the size of the graph, Discrete Mathematics 342, 2765–2769 (2019).DOI
- [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]G. Coutinho and H. Liu, No Laplacian perfect state transfer in trees, SIAM Journal on Discrete Mathematics 29, 2179–2188 (2015).
- [7]W. N. Anderson, Jr. and T. D. Morley, Eigenvalues of the Laplacian of a graph, Linear and Multilinear Algebra 18, 141 (1985).
- [8]A. Kay, The perfect state transfer graph limbo (2018), arXiv:1808.00696 [quant-ph].arxiv.org/abs/1808.00696
- [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]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