Degree Distribution in Quantum Walks on Complex Networks

In this theoretical study, we analyze quantum walks on complex networks, which model network-based processes ranging from quantum computing to biology and even sociology. Specifically, we analytically relate the average long-time probability distribution for the location of a unitary quantum walker to that of a corresponding classical walker. The distribution of the classical walker is proportional to the distribution of degrees, which measures the connectivity of the network nodes and underlies many methods for analyzing classical networks, including website ranking. The quantum distribution becomes exactly equal to the classical distribution when the walk has zero energy, and at higher energies, the difference, the so-called quantumness, is bounded by the energy of the initial state. We give an example for which the quantumness equals a Rényi entropy of the normalized weighted degrees, guiding us to regimes for which the classical degree-dependent result is recovered and others for which quantum effects dominate.

Popular Summary

Imagine a web surfer mindlessly wandering from one page to another by clicking randomly on one of the many hyperlinks on each page they encounter. Where would they end up? This question and the answer to it actually are essential to how Google’s web-search engine decides the relative importance of the world’s webpages. Algorithmically, the world’s webpages are represented by a huge network of nodes (pages) and links (hyperlinks) and the mindless internet surfer by a “random walker.” Now, what happens if the random walker is quantum mechanical instead? This may sound like a question for science fiction, but it is actually part of a recent fundamental drive toward merging the science of complex networks—relevant to many scientific disciplines, including statistical physics, biology, computer science, and social science—with quantum mechanics. In this paper, we make one of the first steps in that drive: to uncover and delineate some of the fundamental connections and differences between classical and quantum networks, by developing and investigating a revealing toy model of quantum random walks on complex networks.

It is well known that for a classical random walker on a complex network, the probability of finding the walker on a node after a long time is proportional to the probability of that node’s degree (or the number of links to other nodes), reflecting only the network’s connective topology. A quantum walker, however, brings conceptually nontrivial subtleties to the problem, including hallmark quantum effects such as quantum interference and the ability of a walker to be in a coherent superposition of states. In addition, the long-time state of a quantum walker depends on its initial state and most often does not converge to a steady state.

Here, we have constructed a model of a quantum walker on a network. The walker’s state is a multicomponent one, with the squared amplitude of the $i$th component representing the probability of finding the walker at node $i$ of the network. This multicomponent state evolves in time according to a Schrödinger equation that has a correspondence with the classical walker. By investigating this model, we have succeeded in uncovering the following properties: (1) When the walker starts from its zero-energy ground state, the long-time average of probability of finding it at a node follows the classical result; (2) at higher energies, the walker’s long-time behavior deviates from the classical case, reflecting its quantumness, and this quantumness is quantitatively bounded by the initial energy of the walker and equal to Rényi entropy—a property associated with the network’s degree distribution.

Our paper thus provides the first analytical connection between classical and quantum walks on complex networks, as well as highlighting their differences. We see this work as the beginning of an exciting development that will involve quantum physics, graph and network theory, and the physics of stochastic processes.

Figure 1

Relating stochastic and quantum walks. An undirected weighted network (graph) $G$ is represented by a symmetric, off-diagonal and non-negative adjacency matrix $A$. There is a mapping from $A$ (by summing columns) to the diagonal matrix $D$, with entries given by the weighted degree of the corresponding node. The node degrees are proportional to the steady-state probability distribution of the continuous-time stochastic walk (with uniform escape rate from each node) generated by $H_C=L{D}^{-1}$, where $L=D-A$ is the Laplacian. The steady-state probabilities, represented by the vector $|{\pi }_0⟩$, are proportional to the node degrees. We generate a corresponding continuous-time unitary quantum walk by the Hermitian operator $H_Q=D^{-1/2}L{D}^{-1/2}$, which is similar to $H_C$. The probability of being in a node in the stochastic stationary state $|{\pi }_0⟩$ and the probability arising from the quantum ground state are equal and proportional to the node degree.

Figure 2

Long-time average probability and degree for nodes in a complex network. Eight networks are considered: BA, ER, WS, RG, KC, EM, CE, and CA. We plot the classical $(P_C{)}_i$ (red dashed line) and quantum $(P_Q{)}_i$ (black +) probabilities against the degree $d_i$ for every node $i$. We overlay this with a plot of the average degree distribution $P(d)$ against $d$ for each network type (grey solid line), when known, along with the distribution for the specific realization used (grey +). Alongside the BA network, we also plot $(P_Q{)}_i$ for the optimized BA (BA-opt) network, in which the internode weights of the BA network are randomly varied in a Monte Carlo algorithm to reach $\epsilon =0.6$ (orange x). We do not include a plot of the degree distribution for this network.

Figure 3

Quantumness and degree entropy. The value of $\epsilon$ against $H_1$ [Eq. (10)] for the nine different networks considered in Fig. 2, as well as the random regular (RR) network (a network with the same degree for each node—in this case, we consider a regular graph with each node of degree six) and star (ST) networks (black +). We also plot $\epsilon$ and $H_1$ for the network obtained in several iteration steps, each randomly varying an internode weight of the BA network, for an increasing number of iteration steps (bottom to top, grey to orange x). The quantumness $\epsilon$ increases and the entropy $H_1$ decreases with step number. The red dashed line represents the upper bound of Eq. (11).

Figure 4

Quantum effects. The ratio of the quantum $({\tilde{P}}_Q{)}_i$ and classical $(P_C{)}_i$ probabilities plotted against degree $d_i$ (black +) for every $i$, for the networks considered in Fig. 2. We also plot the best-fitting curve (red dashed line) to these data of the form $({\tilde{P}}_Q{)}_i/(P_C{)}_i\propto (d_i{)}^{{\kappa }_3}$, whose exponent ${\kappa }_3$ is given in the plot.