{'fraction_non_alphanumeric': 0.05565054326843528, 'fraction_numerical': 0.013733384810545474, 'mean_word_length': 4.298655756867329, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Inefficient quantum walks on networks: the role of the density of states

We show by general arguments that networks whose density of states contains few highly degenerate eigenvalues result in inefficient performances of continuous-time quantum walks (CTQW) over these networks, while systems whose eigenvalues all have the same degeneracy lead to very efficient transport. We exemplify our results by considering CTQW and, for comparison, its classical counterpart, continuous-time random walks, over simple structures, whose eigenvalues and eigenstates can be calculated analytically. Extensions to more complicated, hyper-branched networks are discussed.


I. INTRODUCTION
The transfer of information in quantum systems has attracted a lot of attention in recent years, especially in the context of quantum computing [1]. In analogy to classical random walks, which are used as algorithmic tool in "classical" computing, two version of quantum walks have been introduced: discrete-time quantum (random) walks, with an additional internal "coin" degree of freedom [2], and continuous-time quantum walks (CTQW), where the analogy to continuoustime random walks (CTRW) lies in identifying the classical transfer matrix with the quantum mechanical Hamiltonian [3]. Recently, it has been shown how these two version are related [4].
CTQW are formally equivalent to the tight-binding model in solid-state physics [5] or the Hückel/LCMO model in physical chemistry [6] and therefore can be applied to study transport processes in various types of different systems, like spin chains [7] or ultra-cold Rydberg gases [8]. What matters is that the constituting elements (spins, atoms, molecules, etc.) are of the same type, in the simplest cases they resemble twolevel systems.
In general, the quantum dynamics is very different from the corresponding classical dynamics. The unitary time evolution of a quantum system leads to characteristic dynamical phenomena, e.g., quantum revivals and quantum carpets for the particle in a box [9] or for CTQW on a ring [10], or, for disordered systems, to localization [11].
For linear (ordered) systems, the quantum transport efficiency of CTQW has been proven to overcome the classical efficiency, a result which translates also to more complicated systems like decision or Cayley trees [12]. However, the efficiency of the transport strongly depends on the initial condition [13], i.e., different initial conditions lead to vastly different dynamics of the CTQW.
One way of quantifying the global efficiency of quantum walks is by the average probability of a walker to return to or stay at the origin [14]. In the classical case this quantity depends only on the eigenvalues, or more generally on the density of states (DOS), of the underlying system and not on its eigenvectors. Quantum mechanically, there exists a lower bound to the quantum mechanical return probability. This lower bound also depends only on the DOS [14,15], and, in most cases considered here, is a good measure of the transport efficiency, since the global temporal behaviour of the lower bound is similar to the one of the full expression for the return probability which also requires the eigenstates.
Depending (mainly) on the topology of the system, the DOS shows very distinct features. There is a large variety of complex classical systems, ranging from glasses to proteins, showing anomalous transport [16], which can be related to the structure of the DOS. For instance, CTRW over small-world networks have been shown to be super-diffusive [17]. As we proceed to show, for quantum walks especially the degeneracies of the eigenvalues and the number of degenerate eigenvalues determine the transport efficiency.

II. QUANTUM WALKS ON NETWORKS
We start by considering quantum mechanical transport processes on discrete networks, which are a collection of N connected nodes. A connectivity matrix A = (A ij ) can be assigned to every network. The non-diagonal elements A ij equal −1 if nodes i and j are connected by a bond and 0 otherwise. The diagonal elements A ii equal the number of bonds, f i , which exit from node i.

A. Transition probabilities
Classically, a CTRW is governed by a master equation for the conditional probability, p k,j (t), to find the walker at time t at node k when starting at node j. [18] The transfer matrix of the walk, T = (T kj ), is, in the simplest case where the transmission rates γ of all bonds are take to be equal, related to the connectivity matrix by T = −γA (we assume γ ≡ 1 in the following).
CTQWs are obtained by identifying the Hamiltonian of the system with the classical transfer matrix, H = −T [3,12,13]. The states |j associated with the nodes j of the network form a complete, ortho-normalised basis set of the whole accessible Hilbert space, i.e., k|j = δ kj . A state |j evolves in time as |j(t) = U(t)|j , where U(t) = exp(−iHt) is the quantum mechanical time evolution operator (we have set m ≡ 1 and ≡ 1). The transition amplitude α k,j (t) from state |j at time 0 to state |k at time t reads then α k,j (t) = k|U(t)|j and obeys Schrödinger's equation. Denoting the eigenvalues of the Hamiltonian H = −T by E n (n = 1, . . . , N ) and the orthonormalised eigenstates by |ψ n , such that n |ψ n ψ n | = 1, the quantum mechanical transition probability is π k,j (t) ≡ |α k,j (t)| 2 = n k|e −iEnt |ψ n ψ n |j 2 . (1)

B. Long time limit
Quantum mechanically the unitary time evolution prevents π k,j (t) from having a definite limit for t → ∞. In order to compare the classical long time probability with the quantum mechanical one, one usually uses the long time average (LTA) [19] = n,m δ En,Em k|ψ n ψ n |j j|ψ m ψ m |k , where δ En,Em = 1 if E n = E m and δ En,Em = 0 otherwise. Some eigenvalues of H might be degenerate, so that the sum in eq. (3) can contain terms belonging to different eigenstates |ψ n and |ψ m . We can use the Cauchy-Schwarz inequality to obtain a lower bound for the LTA [15], such that the time integral in eq. (2) fulfills This results in The only term in the sum over n in eq. (5) which survives after integration and taking the limit T → ∞ is the one with E 1 = 0. The corresponding eigenvector can be written as

C. Averaged transition probabilities
Quantum mechanically as well as classically, we can calculated properties from the probability distributions, which solely depend on the eigenvalues of H or T, respectively, but not on the eigenstates. Classically, there exists a simple expression for the average return probability to the initially excited node (see, e.g., ref. [20]): Quantum mechanically, the average is given by By using the Cauchy-Schwarz inequality we obtain a lower bound for π(t) [14,15], (9) With eq. (1) we therefore get In analogy to the classical case, the lower bound |α(t)| 2 depends only on the eigenvalues and not on the eigenstates of H.

III. QUANTUM WALK EFFICIENCIES
Equations (7) and (10) can be used to quantify the efficiency of the two transport processes [14]: In the classical case a quick decrease of p(t) must result -on average -in a quick increase of the probability for the walker to be at any other but the initial node. Thus, the transport away from the initial node j is the more efficient the quicker the decrease of p(t). For instance, it has been shown for small-world networks that p(t) follows a stretched exponential rather than a power law as for regular networks, which gives rise to a quicker decrease of p(t) and thus to a super-diffusive behaviour [17]. Quantum mechanically, π(t), as well as the lower bound |α(t)| 2 , will show strong oscillations due to the unitary time evolution. However, one can use the envelope of this oscillations as a measure for the efficiency, for which the same arguments as in the classical case apply. For regular d-dimensional networks it is straightforward to show that the envelope of |α(t)| 2 decays as t −d , whereas p(t) decays as t −d/2 [14]. Since the decay of |α(t)| 2 is much quicker than the one of p(t), the quantum walk is more efficient than the classical random walk.
For finite systems, p(t), π(t), and |α(t)| 2 do not decay ad infinitum. Classically, the averaged probability will drop in the course of time to the equipartition value of 1/N , since we always have the eigenvalues E 1 = 0 which is non-degenerate, i.e., Quantum mechanically, both, π(t) and |α(t)| 2 , will be oscillating about a value given by the LTA of π(t) or its lower bound |α(t)| 2 , respectively. The long time average of π(t) follows as which still depends on the eigenstates |ψ n . Using again the Cauchy-Schwarz inequality to obtain a lower bound for χ we get with eq. (10) These long time averages give indications on the overall performance of quantum walks: If the LTA are larger than the equipartition value of 1/N , on average most of the probability will remain at the initial node. The argument of using the lower bound |α(t)| 2 instead of π(t) goes only one way: Only if the envelope of |α(t)| 2 exceeds the one of the classical probability p(t) at any(most) times is the quantum walk less efficient than the classical random walk. However, if the envelope of |α(t)| 2 lies below p(t), in general, little can be said about π(t). It might also happen that the envelope π(t) lies above the classical curve, although in the examples considered below this is not the case.

IV. DEGENERACIES OF EIGENVALUES
The eigenvalues of a large variety of networks will be degenerate. By denoting the degeneracy of E n by D n ≡ D(E n ), we can recast eqs. (7) and (10) into respectively. As we will show, there is a profound difference between the temporal behaviour of the two quantities depending on the eigenvalues and their degeneracy. For classical transport processes, the long time behaviour is dominated by the smallest eigenvalues, no matter what their degeneracy is -large eigenvalues with high degeneracies will eventually be suppressed by the exponential. In the quantum case, however, the degeneracies become important due to the unitary time evolution.

A. Uniform degeneracy of eigenvalues
We start with networks, whose eigenvalues have degeneracies of the order O(1). Then we rewrite the lower bound as Now, the product D n D m will be of order O(1), therefore, all terms in the sums contribute to |α(t)| 2 . The shape of the decay depends on the functional form of the degeneracy. If we assume D n ∼ E −ν n , we obtain p(t) ∼ t −ν , whereas |α(t)| 2 ∼ t −2ν [14]. At large times t the only terms which contribute to the sum are those for which E n = E m . Then, the sum will be of order O(N ) and therefore |α(t)| 2 will be of order O(1/N ).
As an example, fig. 1 shows p(t) (solid black line) and |α(t)| 2 (short dashed red line) for a regular network of N = 1000 nodes. For regular networks, almost all eigenvalues are two-fold degenerate, for odd(even) N there is one(two) nondegenerate eigenvalue. Note that the lower bound is exact in this case, i.e., |α(t)| 2 = π(t) [21].
While propagating without interference, the envelope of |α(t)| 2 decays as t −1 (dotted blue line), which is faster than in the classical case, where p(t) ∼ t −1/2 (long dashed green line) [14]. Therefore, the quantum walk can be considered to be more efficient than the corresponding classical random walk. After the interference sets in at about t ≈ 500 = N/2, |α(t)| 2 fluctuates about the LTA χ = (2N − 1)/N 2 [χ = (2N − 2)/N 2 ] for odd(even) N , which is indeed of the same order as the classical long time equipartition value 1/N . However, the classical plateau value is reached at a much later time at about t ≈ 10 5 .

B. One highly degenerate eigenvalue
In contrast to the uniform degeneracy, we consider now one eigenvalue, E l , whose degeneracy, D l , is of order O(N ) whereas the others are of order O(1) or less. By writing we obtain, up to order O(1/N 2 ), The first term on the right-hand side of eq. (18) is of order O(1) and the second term [with the same argument as for eq. (16)] is of order O(1/N ). Therefore, for few highly degenerate eigenvalues, the lower bound |α(t)| 2 will not show a decay to values which fluctuate about 1/N but rather will fluctuate for all times about 1 − 1/N . Also π(t) will not decay but fluctuate roughly about the same value since |α(t)| 2 is a lower bound. Take as a simple example a star-shaped network, having one core node and N − 1 nodes directly connected to the core but not to each other. The eigenvalue spectrum has a very simple structure, there are 3 distinct eigenvalues, namely E 1 = 0, E 2 = 1, and E 3 = N , having the degeneracies D 1 = 1, D 2 = N − 2, and D 3 = 1, respectively. Therefore we get  shows p(t), π(t), and |α(t)| 2 for a star-shaped network with N = 51 nodes. Here, not only |α(t)| 2 (short dashed red line) but also π(t) (long dashed green line) fluctuate about a value close to one, see also the inset of fig. 2. Classically, p(t) (solid black line) decays to the equipartition value 1/N , although the exact form of the decay is different than for regular networks. Thus, the quantum walk has -on average -a large probability to return (or stay) at the initial site, and in this sense is less efficient than its classical counterpart.

C. Two highly degenerate eigenvalues
The next step is having two highly degenerate eigenvalues, E l and E m , with degeneracies D l and D m of order O(N/2).
This changes the properties of |α(t)| 2 . From we get, up to order O(1/N ), Here, the terms D 2 l , D 2 m , and D l D m are of order O(N 2 /4); the cosine fluctuates in the interval [0, 1]. Therefore, in contrast to eq. (18) whose fluctuations are of the order O(1/N ), eq. (22) will also fluctuate in the full interval [0, 1]. As before, there is no envelope of |α(t)| 2 which decays with time. An example of such a system is a star with 2 nodes on each arm. There is one zero eigenvalue E 1 = 0, two nondegenerate eigenvalues E 2,3 = (N +5± √ N 2 − 6N + 25)/4, and two eigenvalues E 4,5 = (3 ± √ 5)/2, whose degeneracy  Figure 3 shows the temporal behaviour of p(t), π(t), |α(t)| 2 , and of eq. (23) for a star with 50 arms of length 2, i.e., N = 101 nodes. While the behaviour of p(t) (black solid line) is similar to the one for the simple star ( fig. 2), there are obvious differences for π(t) (long dashed green line) and |α(t)| 2 (short dashed red line). Although, as for the star-shaped network, neither π(t) nor |α(t)| 2 show a decay to some value comparable to the classical equipartition value 1/N , the oscillations become larger for both quantities. While π(t) fluctuates roughly in the interval [0.2, 1], |α(t)| 2 fluctuates in the full interval [0, 1]. Moreover, considering only the two highly degenerate eigenvalues results in an excelent agreement of eq. (23) (dotted blue line) with the full expression for |α(t)| 2 . Thus also here the quantum walks have a large probability to return or stay at the origin, which results in a low transport efficiency compare to the classical random walk.

D. Complex structures with highly degenerate eigenvalues
So far we have considered simple systems. As we now turn to more complex structure, it will become evident that a lot can be related to those simple models. In particular, there are also large complex systems of eminent interest which have only few degenerate eigenvalues.
One group of systems of interest are star-like hyperbranched structures. An example is the dendrimer, which has been experimentally realised as one macromolecule and which has interesting applications, such as drug delivery and as a light-harvesting antenna [23]. The nodes of the dendrimer can be grouped into generations g, which are concentric about the core node. In our case the core (g = 0) has 3 emanating bonds connecting three additional nodes to it (g = 1); every node in generation g ≥ 1 is connected by one bond to two other node in generation g + 1. Therefore, total number of nodes grows exponentially with the total number of generations G, i.e., N = 3 · 2 G − 2, whereas the number in one generation g is given by N g = 3 · 2 g−1 .
When restricting ourselves to only the three most highly degenerate eigenvalues, the dendrimer resembles a star-like structures. From the eigenvalues we obtain (for G > 3) (24) where N is an appropriate normalization constant. Figure 4 also shows the temporal behaviour of eq. (24), see longdashed blue line, which is very similar to the full expression for |α(t)| 2 . Hence, the general behaviour is indeed dominated by the most degenerate eigenvalues, there are only slight deviations due to the remaining ones. From |α(t)| 2 as well as from eq. (24), we find also here that quantum walks over dendrimers are much less efficient than their classical counterpart. There is certainly a large variety of networks, on which the quantum mechanical transport behaviour remains to be investigated. Prime examples are fractals. Classically it has been shown that the return probability depends on the spectral (fracton) dimension of the fractal, see, e.g., [25]. The eigenvalues of certain fractals can also be calculated recursively [26]. In some cases this gives rise to highly degenerate eigenvalues.

V. CONCLUSIONS
We have analyzed the efficiencies of quantum walks over different discrete networks by relating the density of states to the average return probability of the walk. Depending on the connectivity of the networks, the spectra of the Hamiltonians are vastly differerent. The difference between classical random and quantum walks over networks can be summarised as follows: In the classical case the eigenvalues of the transfer matrix itself are governing the average return probabilities p(t). Quantum mechanically, the degeneracies of the eigenvalues of the Hamiltonian dominate the temporal behaviour and the long time averages of the average return probability π(t) and its lower bound |α(t)| 2 . After giving general arguments corroborating this statements, we illustrated this by simple examples, like regular and star-like networks and extended those to more complex structures, like Cayley trees or dendrimers, which also have few highly degenerate eigenvalues.