Complex networks from classical to quantum

ABSTRACT Recent progress in applying complex network theory to problems in quantum information has resulted in a beneficial cross-over. Complex network methods have successfully been applied

to transport and entanglement models while information physics is setting the stage for a theory of complex systems with quantum information-inspired methods. Novel quantum induced effects

have been predicted in random graphs—where edges represent entangled links—and quantum computer algorithms have been proposed to offer enhancement for several network problems. Here we

review the results at the cutting edge, pinpointing the similarities and the differences found at the intersection of these two fields. SIMILAR CONTENT BEING VIEWED BY OTHERS SYMMETRIES IN

QUANTUM NETWORKS LEAD TO NO-GO THEOREMS FOR ENTANGLEMENT DISTRIBUTION AND TO VERIFICATION TECHNIQUES Article Open access 25 January 2022 COMPLEX QUANTUM NETWORK MODELS FROM SPIN CLUSTERS

Article Open access 26 September 2023 CONCURRENCE PERCOLATION THRESHOLD OF LARGE-SCALE QUANTUM NETWORKS Article Open access 29 July 2022 INTRODUCTION Quantum mechanics has long been

predicted to help solve computational problems in physics1, chemistry2, and machine learning3 and to offer quantum security enhancement in communications4, including a quantum secure

Internet5. Rapid experimental progress has pushed quantum computing and communication devices into truly data-intensive domains, where even the classical network describing a quantum system

can exhibit complex features, giving rise to what appears as a paradigm shift needed to face a fundamental type of complexity6,7,8,9,10,11,12,13. Methods originating in complex

networks—traditionally based on statistical mechanics—are now being generalized to the quantum domain in order to address these new quantum complexity challenges. Building on several

fundamental discoveries14,15, complex network theory has demonstrated that many (non-quantum) systems exhibit similarities in their complex features14,15,16,17,18, in the organization of

their structure and dynamics19,20,21,22,23,24, the controllability of their constituents25, and their resilience to structural and dynamical perturbations26,27,28,29,30,31. Certain quantum

systems have been shown to indeed exhibit complex features related to classical systems, as well as novel mechanisms and principles that interrelate complex features in quantum

systems6,7,8,9,10,11,12,32. Two types of quantum networks have been of primary focus in the series of pioneering results we review. The first consists of quantum systems whose connections

are represented by entangled states6,33,34. These quantum networks are used in secure quantum communication systems. The second area of focus consists of networks of quantum systems, such as

atoms or superconducting quantum electronics, whose connections are physical35,36,37,38,39,40. Such systems are used to develop quantum-enhanced algorithms or quantum information transport

systems, both modeled by quantum walks on complex networks. At a fundamental level, the two types of quantum networks are described by quantum information theory, allowing one to extend the

spectrum of network descriptors—such as ranking indicators, similarity, and correlation measures—inside the quantum domain. Interestingly, the same tools can then be appropriately modified

to apply to traditional complex networks, suggesting the existence of a framework—network information theory—suitable for application to both classical and quantum networked systems32,41,42.

This bidirectional cross-over is carving out a coherent path forward built fundamentally on the intersection of these two fields (see Box. 1). Several quantum effects are still outside of

the predictive range of applicability of complex network theory. Future work should build on recent breakthroughs and head toward a new theory of complex networks, which augments the current

statistical mechanics approach to complex networks, with a theory built fundamentally on quantum mechanics. Such a unified path forward appears to be through the language of information

theory. Here, we make an effort to review some of the crucial steps toward the creation of a network theory based fundamentally on quantum effects. Therefore, we do not cover several topics

that, nevertheless, deserve to be mentioned as part of the field. These include, in no particular order, quantum gravity theories based on complex networks43,44,45,46, synchronization in and

on quantum networks47, quantum random circuits48,49, classical spin models, and quantum statistics successfully used in complex network theory50,51,52 (see ref. 53 for a thorough review).

BOX 1: CROSS-POLLINATION BETWEEN THE FIELDS OF COMPLEX NETWORKS AND QUANTUM INFORMATION SCIENCE In recent years, seminal work has been carried out at the intersection of quantum information

and computation and complex network theory. We attempt to catalog the scope of this work in Box 1. Each of the shaded regions represent published findings that map out the field from

theoretical, experimental, and computational perspectives. The top area classifies the analytical tools inspired by quantum information for classical network analysis and vice versa—both

covered in this review—as well as the quantum algorithms developed to address-specific problems in network science. The classification in the bottom area includes quantum networks based on

entangled states and on physical connections—also covered in this review—as well as quantum network models of space-time, random quantum circuits, random tensor networks, and geometry

NETWORKS IN QUANTUM PHYSICS VS COMPLEXITY Network and graph theory fundamentally arises in nearly all aspects of quantum information and computation. As is the case with traditional network

science, not all networks exhibit what is considered as “complexity”. Here, we will recall briefly the basic definition of a network and mention several areas where network theory arises in

quantum computation and contrast this with the concept of a complex network. A network is an abstract representation of relationships (encoded by edges) between units (encoded by nodes) of a

complex system. Edges can be directed, i.e., they can represent information incoming to or outgoing from a node and, in general, they can be weighted by real numbers. The number of

incoming, outgoing, and total edges is known as incoming, outgoing, and total degree of a node, respectively. The sum of the corresponding weights defines the incoming, outgoing, and total

strength of that node, respectively. Networks are often characterized by how node degree and strength are distributed and correlated. Systems modeled by uncorrelated networks with

homogeneous degree distribution are known as Erdos–Renyi networks, whereas systems with power-law degree distribution are known as scale-free networks. We refer to refs. 16,54 for reviews of

network concepts and models. The use of various aspects of graph and network theory can be found in all aspects of quantum theory, yet not all networks are complex. The commonly considered

networks include (i) Quantum spins arranged on graphs; (ii) quantum random walks on graphs; (iii) Quantum circuits/networks; (iv) Superconducting quantum (electrical) circuits; (v) Tensor

network states; (vi) Quantum graph states, etc. Although the idea of a complex network is not defined in a strict sense, the definition is typically that of a network that exhibits an

emergent property, such as a non-trivial distribution in node degree. This is in contrast to graph theory, which applies graph theory or tensor network reasoning to deduce and determine

properties of quantum systems. Here, we will focus on topics in quantum systems that are known to be connected with the same sort of complexity considered in complex networks. QUANTUM

NETWORKS BASED ON ENTANGLED STATES To define quantum networks based on entangled states, let us start from the state of each _i_th qubit, written without loss of generality, as $$\left|

{\psi _i} \right\rangle = {\mathrm{cos}}(\alpha _i)\left| 0 \right\rangle + e^{ - i\theta _i}{\mathrm{sin}}(\alpha _I)\left| 1 \right\rangle ,$$ (1) with |0〉 and |1〉 the preferred or

“computational” basis. The qubit is in a pure, coherent superposition of the two basis states and any measurement in this same basis will cause the state to collapse onto |0〉 or |1〉, with

probability cos2(_α__i_) and sin2(_α__I_), respectively. Let us consider a quantum system with two qubits, i.e., _i_ = 1 and 2. The basis of this system is given by the so called, tensor

product, of the two basis states: |00〉, |01〉, |10〉, and |11〉. If the two qubits are not entangled, i.e., their states are independent from each other, then the state of the overall system

can be written as e.g., |_ψ_12〉 = |_ψ_1〉⊗|_ψ_2〉, whereas this is not possible if the two qubits are entangled. A generalization of this description to the case of mixed states is obtained in

terms of the non-negative density matrix _ρ_; a unit trace Hermitian operator representing the state of the system as an ensemble of (unknown) pure states. Instead of distributing

entanglement on regular graphs, such as uniform lattices typically studied in condensed matter physics, it has been shown that it is possible to tune the amount of entanglement between two

nodes in such a way that it equals the probability to have a link in (classical) Erdos–Renyi graphs6. Such random graphs can be defined by the family of networks _G_(_N_, _p_), where _N_ is

the number of nodes and _p_ the probability to find a link between any two nodes. The probability scales with the size of the network following a power law _p_ ∝ _N_−_z_, with _z_ ≥ 0. In

classical network theory, there exists a critical value for the probability _p__c_(_N_) for which, if _p_ > _p__c_(_N_) a given subgraph of _n_ nodes and _l_ links has higher probability

to be observed. The classical result is that this critical probability scales with _N_ as _p__c_(_N_) ∝ _N_−_n_/_l_. Acin, Cirac, and Lewenstein6 formulated an elegant extension of this

picture to the quantum realm by replacing each link with an entangled pair of particles, where the probability _pi_,_j_ = _p_ that the link exists between nodes _i_ and _j_ is substituted by

a quantum state _ρ__i_,_j_: = _ρ_ of two qubits, one at each node (see Fig. 1). One can build a quantum network where each node consists of _N_ − 1 qubits, which are entangled, in pairs,

with qubits of other nodes. However, in this case, although the connections are identical and pure they encode non-maximally entangled pairs. For pure states of qubits the density matrix is

_ρ_ = |_ϕ_〉〈_ϕ|_, with $$\left| \phi \right\rangle = \frac{1}{{\sqrt 2 }}\left( {\sqrt {2 - p} \left| {00} \right\rangle + \sqrt p \left| {11} \right\rangle } \right).$$ (2) Here, 0 ≤ _p_ ≤ 

1 quantifies the entanglement of links and the state of the overall quantum random graph can be denoted by |_G_(_N_, _p_)〉. If each link, i.e., each entangled pair, attempts to convert its

state to the maximally entangled one (_p_ = 1/2) through local operations and classical communication (LOCC), the optimal probability of successful conversion is exactly _p_. It follows that

the fraction of existing entangled states converted to maximally entangled ones by LOCC corresponds to the probability of having a link between nodes in the corresponding classical random

network6. By varying the value of the parameter _z_, i.e., how the critical probability scales with system size, it is possible to control the number and type of subgraphs present in a

quantum network of _N_ nodes. This is useful to create special multipartite states, such as the Greenberger–Horne–Zeilinger state, which exhibits non-classical correlations55. The striking

result is that it is possible to obtain, with probability approaching unity, a quantum state with the topology of any finite subgraph for _N_ approaching infinity and _z_ = −2. This bridge

between complex network theory and quantum theory provides a powerful tool to investigate the critical properties of a quantum system. For instance, in the case of regular lattices, it has

been shown that the probability _p_opt to establish a perfect quantum channel between the nodes can be mapped to the probability of distributing links among each pair of nodes in the

lattice6, a scenario that can be studied using the well-established bond-percolation theory from statistical physics. This result allows one to calculate the critical probability above which

the system will exhibit an infinite connected cluster and, in the case of qubits, it has been shown that the probability of having an entangled path with infinite length—i.e., an infinite

sequence of entangled states connecting an infinite number of qubits—is unity. However, for product states this probability is zero, denoting the existence of a sharp transition between

these two scenarios. However, local measurements based on this approach, called classical entanglement percolation (CEP), are not optimal, in general, to generate maximally entangled states:

CEP is not even asymptotically optimal for two-dimensional lattices and new quantum protocols based on quantum entanglement percolation have to be used instead6. A novel critical

phenomenon, defining an entanglement phase transition, emerges from this new strategy, where the critical parameter is the degree of entanglement required to be distributed in order to

establish a quantum channel with probability that does not decay exponentially with the size of the system, at variance with CEP. This type of enhancement with respect to the classical case

has been reported for different network topologies, such as Erdos–Renyi, scale-free, and small-world networks33. Unexpected quantum effects emerging from network effects have been reported.

Cardillo et al.56 Show that nodes that store the largest amount of information are the ones with intermediate connectivity and not the hubs, breaking down the usual hierarchical picture of

classical networks. More recently, Carvacho et al.57 measured the emergence of special quantum correlations, named non-bilocal, correlating distant qubits by means of several intermediate,

typically independent, sources, and providing evidence for violation of local causality in a quantum network. The static entangled states providing the network connectivity described here,

will be replaced in the next section by dynamical processes on networked quantum systems. QUANTUM NETWORKS BASED ON PHYSICAL CONNECTIVITY Another wide area where network concepts have found

applicability consists of quantum systems physically interconnected, such as atoms or superconducting quantum electronics35,36,37,38,39,40. These types of systems provide fertile ground

where quantum algorithms are tested58,59,60,61,62 and quantum information transport systems are studied63,64,65. Typical modeling approaches are based on so called “quantum walks” on complex

networks, with recent studies showing that quantum information tasks, typically designed for simple topologies, retain performance in very disordered structures66. Stochastic (non-quantum)

walks are also a central model in complex network theory—see the review67. Any quantum process can be viewed as a single-particle walk on a graph. Single-particle quantum walks represent a

universal model of quantum computation—meaning that any algorithm for a quantum computer can be translated into a quantum walk on a graph—and, in addition, quantum walks have been widely

studied in the realm of quantum search on graphs, in both continuous and discrete time via coined walks (see e.g.,58,59,60,61 in particular, the graph optimality results66). The

computational advantages of quantum versus stochastic random walk based algorithms has attracted wide interest with typical focus being on general graphs, which consequently do not exhibit

complex features. However, many works have compared properties of stochastic68,69 and quantum random walks63,64,65 on complex networks70. Network topology has further been shown as a means

to direct transport by adding complex numbers—while maintaining Hermiticity—to the networks adjacency matrix in “chiral quantum walks”65,71,72 (note that chiral walks were realized

experimentally in ref. 12). Open system walks which mix stochastic and quantum effects in ‘open’ evolutions64 have aided in the study of quantum effects in biological exciton transport

(again, modeled as a quantum walk) and developments in a quantum version of Google’s Page-Rank8,9,10 has been seen, providing a practical solution to overcome the degeneracy issues affecting

the classical version and enhancing node ranking in large networks. Recently, Faccin et al. have analytically solved a model that shed light on some key differences between stochastic and

quantum walks on complex networks7. These differences push forward a general understanding which can lead to a theory explaining novel complex features in quantum systems. Quantum walks on

complex networks represent both a practical model of transport70 as well as an interesting stage of comparison between the quantum and stochastic cases. As a closed quantum system exhibits

fluctuations in the probabilities in time, typically a long time average is considered. Physically, this is the best approximation one can hope for, provided that there is no knowledge of

when the walk started. In this case, the probability to find a quantum walker in the _i_th node is given by $$p(i) = \mathop {{\lim}}\limits_{T \to \infty } \frac{1}{T}\mathop

{\int}\limits_0^T {dt} \left| {\left\langle {i|U_t|0} \right\rangle } \right|^2,$$ (3) where |0〉 is the initial state and _U__t_ = _e_−i_Qt_ is the unitary evolution operator defined by the

quantum generator _Q_. Interference between subspaces of different energy vanish in the long time average so we obtain an expression for the probability (_P__Q_)_i_ in terms of the energy

eigen-space projectors Π_j_ of the Hamiltonian _H__Q_, $$(P_Q)_i = \mathop {\sum}\limits_j {\left\langle i \right|{\Pi}_j\rho (0){\Pi}_j\left| i \right\rangle } .$$ (4) Here \({\Pi}_j =

\mathop {\sum}\nolimits_k {| {\phi _j^k} \rangle \langle {\phi _j^k} |}\) projects onto the subspace spanned by the eigenvalues \(| {\phi _j^k} \rangle\) of _H__Q_ corresponding to the same

eigenvalue _λ__j_. QUANTUM-ENHANCED PAGE-RANKING The non-symmetric adjacency matrix representing the directed connectivity of the World Wide Web, a.k.a. the Google matrix _G_, satisfies the

Perron–Frobenius theorem73 and hence there is a maximal eigenvalue corresponding to an eigenvector of positive entries _Gp_ = _p_. The eigenvector _p_ corresponds to the limiting

distribution of occupation probabilities of a random web surfer—it represents a unique attractor for the dynamics independently of the initial state. The vector _p_ is known as the

Page-Rank. A dumping or teleportation factor is often included in the computation in order to assure the Perron–Frobenius theorem satisfactibility. Several recent studies embed _G_ into a

quantum system and consider quantum versions of Google’s Page-Rank8,9,10. Garnerone et al.74 relied on an adiabatic quantum algorithm to compute the Page-Rank of a given directed network,

whereas Burillo et al.11 rely on a mixture of unitary and dissipative evolution to define a ranking that converges faster than classical Page-Rank. The page-ranking vector \(\vec p\) is an

eigenvector of \({\Bbb I} - G\) corresponding to the zero eigenvalue (the lowest). This fact leads to a definition of a Hermitian operator which can play the role of a Hamiltonian, defined

as: $$h^p = ({\Bbb I} - G)^\dagger ({\Bbb I} - G),$$ (5) though highly non-local, its ground state represents the target Page-Rank, which could be found by adiabatic quantum annealing into

the ground state. Using a quantum computer to accelerate the calculation of various network properties has been considered widely58,59,60,61. As Page-Rank relies on finding the vector

corresponding to the lowest eigenvalue of the Google matrix, the adiabatic algorithm opens the door up to accelerate network calculations using quantum computers. DIRECTING TRANSPORT BY

SYMMETRY BREAKING IN CHIRAL WALKS Chiral quantum walks, introduced by Zimborás et al. in ref. 65 and realized experimentally in ref. 12, append complex numbers to the adjacency matrix

(playing the role of the system Hamiltonian) while still maintaining the Hermitian property12,65,71,72. These complex phases in many cases do not affect transfer probabilities: the theory

explaining this finding was developed in refs. 12,65, without relying on approximations or averaging. The case of open systems has been investigated as well in ref. 65. In the scenarios

where the addition of complex phases affects transfer probabilities, the underlying system breaks time-reversal symmetry and, consequently, the probability flow into the quantum system is

biased. This fact enables directed state transfer without requiring a biased (or non-local) distribution in the initial states, or coupling to an environment. When the underlying graph is

bipartite (e.g., a graph whose vertices can be divided into two disjoint sets such as a square lattice), time-reversal symmetry in the transport probabilities cannot be broken. Transport

suppression is indeed possible however65. Bipartite graphs include trees, linear chains and generally, graphs with only even cycles. These results point to a subtle interplay between the

topology of the underlying graph, giving rise to a new challenge for dynamical control of probability transfer when considering walks on complex networks12,65,71,72. OPEN QUANTUM WALKS The

area of open quantum systems75 studies noise and its effects in quantum systems. The adiabatic version of Page-Rank9 uses a quantum stochastic quantum walk as proposed by64 (see also refs.

76,77 for studies on open walks). Quantum stochastic walks are defined by a quantum walk undergoing dissipative dynamics. The latter follows the quantum master equation in the Lindbladian

form: $$\dot \rho = {\Bbb L}[\rho ]$$ (6) $$= - {\mathrm{i}}[H,\rho ] + \mathop {\sum}\limits_k {L_k} \rho L_k^\dagger - \frac{1}{2}\left\{ {L_k^\dagger L_k,\rho } \right\}$$ (7) where

_L__k_ represents a jump operator, whereas [⋅,⋅] and {⋅,⋅} are commutator and anti-commutator, respectively. The network topology is embedded by choosing _H_ equal to the adjacency matrix of

the symmetrized network and \(L_k = L_{ij} = \sqrt {G_{ij}} ij\). In this picture, node ranking is defined by an activity vector _α_ computed at the steady state _ρ_ss. Paparo et al.8,10

introduced a Szegedy type of Markov chain quantization78 of the random walk. In order to quantize the Markov chain defined by the Google matrix _G_ of _N_ nodes, one introduces a Hilbert

space \({\cal{H}} = {\mathrm{span}}\left\{ {\left| i \right\rangle _1\left| j \right\rangle _2,\left| i \right\rangle ,\left| j \right\rangle \in [0,N]} \right\}\) and the superposition of

outgoing edges from node _i_: $$\left| \psi \right\rangle _i = \left| i \right\rangle _1 \otimes \mathop {\sum}\limits_k {\sqrt {G_{ki}} } \left| k \right\rangle _2$$ (8) and $${\Pi} =

\mathop {\sum}\limits_k {\left| {\psi _k} \right\rangle } \left\langle {\psi _k} \right|.$$ (9) Each step of the quantum walk _U_ is defined by a coin flip \(2{\Pi} - 1\) and a swap

operation _S,_ which ensures unitarity8 $$U = S(2{\Pi} - 1)$$ (10) the swap operator is \(S = \mathop {\sum}\nolimits_{ij} {\left| {ij} \right\rangle \left\langle {ji} \right|}\). In the

case of quantum Page-Rank, this is set to the instantaneous probability _P_(_i_, _t_) of finding the walker at node _i_ at the time-step _t_. To obtain a fixed value for the quantum

Page-Rank a time average is calculated as long as with its variance as a measure for quantum fluctuations. Another approach11 involves defining a Markov quantum evolution similar to Eq. (7),

with a tuning parameter _α_: $$\dot \rho = - (1 - \alpha )[H,\rho ] + \alpha \left[ {\mathop {\sum}\limits_k {L_k} \rho L_k^\dagger - \frac{1}{2}\{ L_k^\dagger L_k,\rho \} } \right]$$ (11)

where the Hamiltonian _H_ is the symmeterized adjacency matrix and \(L_k = L_{ij} = \sqrt {G_{ij}} \left| i \right\rangle \left\langle i \right|\) represent the jump operators, which

consider the directness of the network. With this definition, for values of _α_ ∈ (0, 1), a stationary state is guaranteed. In this case, for _α_ = 0, we revert to the unitary evolution,

whereas for _α_ =  1, we revert to the stochastic case. The authors8,10,11 show how this definition of quantum Page-Rank resolves problems of degeneracy in the classical Page-Rank

definition, enhances the importance of secondary hubs and, for certain values of _α_, the algorithm exhibits faster convergence. TOWARDS UNIFIED ANALYSIS OF NETWORK COMPLEXITY The

interaction between network science and quantum information science has led to the development of theoretical and computational tools that benefitted from both fields. On the one hand,

quantum-inspired tools, such as information entropies and quantum distance measures, have been successfully applied to practical problems concerning classical complex networks32. On the

other hand, classical network descriptors have been ported to the quantum realm to gain better insights about the structure and the dynamics of networked quantum systems13. The

cross-pollination between the two fields—including, among others, quantum statistics for modeling the dynamics of classical networks and their geometry79,80 (see also ref. 81 and references

therein)—is still ongoing with vibrant future research opportunities. Here, we briefly review the advances concerning quantum-inspired entropic measures for networks and network-inspired

measures for quantum systems. INFORMATION ENTROPY OF CLASSICAL NETWORKS Historically, the concept of entropy has been successfully used to quantify the complexity of many systems82,83.

Recently, the possibility of using quantum entropy and other quantum information theoretical measures has been explored by the community of network scientists. For classical complex

networks, von Neumann’s entropy has been applied over one decade ago84. The combinatorial Laplacian matrix _L_, obtained from the adjacency matrix representing the network, is rescaled by

the number of edges in the network. The normalization of the matrix _L_ guarantees that the corresponding eigenvalues are non-negative and sum up to 1—in order to be interpreted as

probabilities85—and some other properties, which makes the resulting object similar to a quantum density matrix _ρ_. Network entropy is defined according to von Neumann quantum entropy as

$$S(\rho ) = - {\mathrm{Tr}}(\rho \log_2\rho ).$$ (12) By exploiting the eigen-decomposition of the Laplacian matrix, it can be shown that this entropy corresponds to the Shannon entropy of

the eigenvalue spectrum of _ρ_. This entropy has been generalized to the case of multilayer systems86, composite networks where units exhibit different types of relationships that are

generally modeled as different layers (see ref. 17,18,87 for a thorough review). It has been recently shown that the von Neumann entropy calculated from the rescaled Laplacian does not

satisfy the sub-additivity property in some circumstances32,41. This undesirable feature can be addressed by means of a more grounded definition32, whose rationale is to measure the entropy

of a network by exploiting how information diffuses through its topology. Information diffusion in this context is governed by the equation $$\dot \psi _i(t) = - \mathop {\sum}\limits_{j =

1}^N {L_{ji}} \psi _j(t),$$ (13) with _ψ__i_(_t_) the amount of information in node _i_ at time _t_. The solution of this diffusion equation is given, in vector notation, by _ψ_(_t_) = 

exp(−_Lt_)_ψ_(0), whose normalized propagator is used to define the density matrix as $$\rho = \frac{{e^{ - \tau L}}}{{{\mathrm{Tr}}(e^{ - \tau L})}},$$ (14) where time plays the role of a

resolution parameter allowing one to probe entropy at different scales32. A similar approach, involving a modified Laplacian matrix, has been recently used for revealing the mesoscale

structure of complex directed networks88,89. This quantum-inspired framework provides a powerful basis to develop an information theory of complex networks, with direct applications in

classical network science, such as system comparison. COMPARING CLASSICAL NETWORKS A known problem in network science is to compare two networks, without relying on a specific subset of

indicators. Network information entropy allows one to introduce relative entropies such as the Kullback–Leibler divergence, to compare two networks with density matrices _ρ_ and _σ_

respectively: $${\cal{D}}(\rho ||\sigma ) = {\mathrm{Tr}}[\rho (\log _2\rho - \log _2\sigma )].$$ (15) By exploiting the well-known classical result that the minimization of Kullback–Leibler

divergence between a reference distribution and its parametric model corresponds to the maximization of the likelihood, it has been shown that in a network context this allows one to define

the network log-likelihood by $$\log _2{\cal{L}}(\Theta ) = {\mathrm{Tr}}[\rho \log _2\sigma (\Theta )].$$ (16) The introduction of network likelihood opens the door to a variety of

applications in statistical inference and model selection, based on concepts such as the Fisher information matrix, Akaike and Bayesian information criteria, and minimum description length,

to cite some of them32. This new framework has been used to compare networks for several purposes. For instance, in the case of pairs of networks, the graphs are first merged by connecting

each node from one network to any other node in the other network. Successively, continuous-time quantum walks are used to explore the composite system and the quantum Jensen–Shannon

divergence between the evolution of two walks is calculated. This divergence, that is a measure of (dis)similarity, is shown to be maximum when the two original networks are isomorphic60.

The square root of quantum Jensen–Shannon divergence has the nice property of defining a metric, allowing one to define a distance between networks. If _ρ_ and _σ_ are two density matrices

corresponding to two networks with _N_ nodes, their Jensen–Shannon divergence is defined by $${\cal{D}}_{JS}(\rho ||\sigma ) = \frac{1}{2}{\cal{D}}_{KL}(\rho ||\mu ) +

\frac{1}{2}{\cal{D}}_{KL}(\sigma ||\mu )$$ (17) $$= S(\mu ) - \frac{1}{2}[S(\rho ) + S(\sigma )],$$ (18) that is the difference between the entropy of the mixture \(\mu = \frac{1}{2}(\rho +

\sigma )\) and the semi-sum of the entropies of the original systems. In the context of multilayer systems, this measure has been used to quantify the distance between layers of a multiplex

network, cluster, and aggregate them appropriately in order to reduce its structural complexity41. These ideas have quickly found direct applications in biology. In genetic molecular

systems, such as the ones described by gene–protein interactions, layers might encode different relationships among molecules—functional, e.g., additive, suppressive and other types of

association, or physical, e.g., colocalization or direct interaction. The information-theoretic framework described here allowed to show that such systems exhibit a certain level of

redundancy, larger than the one observed in man-made systems41, suggesting the existence of biological mechanisms devoted to maximize diversity of interactions. In computational neuroscience

studies, the connectome of the nematode _Caenorhabditis elegans_—one of the most studied in the field because of its small size, with ~300 neuronal cells—has been mapped to a multiplex

network where layers encode synaptic, gap junction, and neuromodulator interactions. Here, the analysis of reducibility revealed that the monoamine networks have a unique structure, with

information complementary to that provided by neuropeptide networks90. The same analysis, applied to a multilayer functional representation of the human brain revealed, quantitatively, the

importance of not disregarding or aggregating connectivity information for clinical classification of healthy and schizophrenic subjects91. In another application the Jensen–Shannon distance

between layers of a multiplex system has been used to identify community-based associations in the human microbiome32, where the microbial network corresponding to each body site is

represented by a layer in a multiplex network, in perfect agreement with biological expectation92. The (dis)similarity between networks has also been quantified by using a combination of the

classical Jensen–Shannon distance and the concept of network node dispersion, measuring the heterogeneity of a graph in terms of connectivity distance among its nodes42. DEGREE DISTRIBUTION

OF QUANTUM NETWORKS Nodes in a complex network have different roles and their influence on system dynamics can vary widely depending on their topological characteristics. One of the simpler

(and widely applied) characteristics is the degree centrality, defined as the number of edges incident on that node. Many real world networks have been found to follow a widely

heterogeneous distribution of degree values93. Several models, based on mechanisms like preferential attachment15, fitness94, or constrained random wiring54, to mention some of them, were

developed to reproduce degree distributions commonly observed in empirical systems. Despite the complexity of the linking pattern, the degree distribution of a network affects in a simple

way the ongoing dynamics. In fact, it can be shown that the probability of finding a memoryless random walker at a given node of a symmetric network at the stationary state, is just

proportional to the degree of such node68. In ref. 7, theauthors consider the relationship between the stochastic and the quantum version of such processes, with the ultimate goal of

shedding light on the meaning of degree centrality in the case of quantum networks. They consider a stochastic evolution governed by the Laplacian matrix \(L_S = {\cal{L}}D^{ - 1}\), the

stochastic generator that characterizes classical random walk dynamics and leads to an occupation probability proportional to node degree. In the quantum version, an hermitian generator is

required and the authors proposed the symmetric Laplacian matrix \(L_Q = D^{ - \frac{1}{2}}{\cal{L}}D^{ - \frac{1}{2}}\), generating a valid quantum walk that, however, does not lead to a

stationary state, making difficult a direct comparison between classical and quantum versions of the dynamics. A common and useful workaround to this issue is to average the occupation

probability over time, as in Eq. (4). The generators of the two dynamics are spectrally similar (see Fig. 2) and share the same eigenvalues, whereas the eigenvectors are related by the

transformation \(\phi _i^C = D^{ - \frac{1}{2}}\phi _i^Q\). As a consequence, if the system is in the ground state the average probability to find the walker on a node will be the same as in

the classic case, which will depend solely on the degree of each node. For the cases in which the system is not in the ground state, it is possible to define a _quantumness_ measure

\(\varepsilon = 1 - \left\langle {\phi _0^Q} \right|\rho _0\left| {\phi _0^Q} \right\rangle ,\)describing how far from the classical case the probability distribution of the quantum walker

will be. In the case of uniformly distributed initial state _ρ_0, this provides a measure for the heterogeneity of the degree distribution of a quantum network. MESOSCALE ORGANIZATION OF

QUANTUM SYSTEMS Community detection, and in general mesoscopic structure detection, has been widely studied in the literature of classical complex networks95,96. Although the definition of

community “a subset of nodes tightly connected compared to what is expected” is in general ill defined and part of an ongoing debate, the number of proposed algorithms is incredibly high and

still growing. The cross-pollination of community detection with quantum mechanics is in two levels. On the one hand, chronologically, the first attempt was to borrow tools from quantum

mechanics for applications to classical systems88,97,98,99,100. On the other hand, an algorithm to find communities in complex quantum systems was proposed in ref. 13. In ref. 97,98, the

authors propose a method for data clustering similar to kernel density estimators, in a quantum framework. The given data points are mapped to a Gaussian wave function and, supposing that

the latter is an eigenstate for some time-independent Schrödingher equation: $$H\psi = [T + V(x)]\psi = E_0\psi ,$$ the minimization of the potential _V_(_x_) leads to the desired

clustering. An extension to dynamical quantum systems has been introduced in ref. 99. In this case the expectation values of the position operator evolves in time toward the closer minimum

of the potential. This formulation can leverage the acceleration of graphics hardware. A method based on continuous-time quantum walks was proposed in ref. 100. Here, a node-affinity measure

based on the response of node population density to link failure was given. If the population on two nodes changes in a similar manner after link removal, they are more likely to belong to

the same community. A magnetic Laplacian, where a magnetic field is expected to traverse all cycles in the network, was used in ref. 88. With an approach similar to chiral walks, previously

described, the symmetric Laplacian is amended with the original link directionality by a phase term _e_±i_θ_, with _θ_ being a parameter for the method, and used for community detection in

directed networks, a longstanding problem in network science. In the case of quantum systems, partitioning in modular units has been often carried out on the basis of ad hoc considerations.

In an effort to extend community detection to the quantum mechanics realm, Faccin et al.13 introduced several closeness matrices inspired by different quantum quantities. Given the

Hamiltonian \(H = \mathop {\sum}\nolimits_{ij} {H_{ij}} \left| i \right\rangle \left\langle j \right|\) of the quantum system of interest, the authors consider a continuous-time random walk

on the system topology. The first quantity is energy transport, porting to the quantum realm the concept applied in several classical algorithms where communities are interpreted as traps

for the dynamical process. In this framework, two nodes are considered to be close if, on average, their in-between transport is high. If this average is computed over a short time period

(compared with evolution time scales), then the closeness values are proportional to the Hamiltonian terms |_H__ij_|, providing a classical approach to community detection (see Fig. 3). A

second quantity, also proposed as a closeness measure, is related to the average fidelity of the evolving process compared with the initial state. In this case, the localization of

eigenstates is the characteristic determining the closeness of two nodes. These methods augment current ad hoc approaches to partitioning nodes in quantum transport systems with enhanced

methods based on community detection algorithms. OUTLOOK IN QUANTUM NETWORK SCIENCE Generalization of complex network methods to the quantum setting represents a foundational advancement

required to understand complexity in physical systems. These methods represent a change of paradigm, which bring several road blocks that must be faced. Centrally, the application domain of

complex network methods to quantum physics must be expanded, whereas studies in the other direction, i.e., where methods from the quantum domain have now been ported to network science. From

a foundational perspective, as networks necessarily represent physical systems, such systems are inherently governed by the laws of information physics. In fact, a research line is emerging

now that seeks to quantify, in terms of implicit information processing capacity, networked systems, with several applications to social, technological, and biological

systems32,41,42,90,91. Although this interesting direction seems promising, yet it is comparably in its infancy, whereas it is still not known how to generalize classical concepts of

complexity science to the quantum domain. Another relevant research direction, crucial for applications in classical network science, concerns the interplay between structure and dynamics,

which is almost entirely unclear in the case of quantum networks. Although scale-free networks have been considered in the quantum setting33, the result is an—albeit interesting—toy model

with theoretical predictions to be verified experimentally. Therefore, further advancement along this track is of central interest, because it might play a fundamental role in

quantum-enhanced technology and could lead to experiments devoted to test cross-disciplinary ideas in quantum and complexity science34. The quest for a theoretical foundation for quantum

complex networks might have a deep impact in information and communication technology. Although information processing in classical systems is well controlled, it is also rather limited and

quantum computing might overcome such limitations101,102. However, given that such systems are more sensitive to interactions with the environment, they are also more exposed to errors than

their classical counterparts. Quantum error-correcting codes allow us to store and manipulate quantum information in the presence of certain types of noise that, in this context, might

perturb the quantum system causing effects similar to random failures in classical complex networks. The development of quantum error correction techniques that make quantum computing and

quantum communication possible cannot prescind from the study of “system resilience”, a topic that found uncountable applications in classical network science26,28,31,103,104. Other types of

perturbations that are natural for classical systems, such as targeted attacks of network hubs26 or cascade-based attacks105, still have no clear quantum counterpart and their study, from

both theoretical and experimental perspectives, will play a key role in the development of a quantum Internet5. In fact, it is tantalizing to think about how quantum hubs should be protected

by the quantum counterpart of typical denial of service attacks. Continued advances in the theory of complexity in networked quantum systems will help address the challenges faced as

quantum technologies scale up to commercially feasible products. Work toward a quantum theory of complex networked systems is already opening up novel avenues when facing contemporary

complexity challenges. DATA AVAILABILITY No data set were generated or analyzed during the current study. REFERENCES * Johnson, T. H., Clark, S. R. & Jaksch, D. What is a quantum

simulator? _EPJ Quantum Technol._ 1, 1–12 (2014). Article  Google Scholar  * Lanyon, B. P. et al. Towards quantum chemistry on a quantum computer. _Nat. Chem._ 2, 106–111 (2010). Article 

Google Scholar  * Biamonte, J. et al. Quantum machine learning. _Nature_ 549, 195–202 (2017). Article  ADS  Google Scholar  * Komar, P. et al. A quantum network of clocks. _Nat. Phys._ 10,

582–587 (2014). Article  Google Scholar  * Kimble, H. J. The quantum internet. _Nature_ 453, 1023–1030 (2008). Article  ADS  Google Scholar  * Acín, A., Cirac, J. I. & Lewenstein, M.

Entanglement percolation in quantum networks. _Nat. Phys._ 3, 256–259 (2007). THIS PAPER DISCOVERS SEVERAL PROPERTIES OF ENTANGLEMENT-BASED COMPLEX QUANTUM NETWORKS. Article  Google Scholar

  * Faccin, M., Johnson, T., Biamonte, J., Kais, S. & Migdał, P. Degree distribution in quantum walks on complex networks. _Phys. Rev. X_ 3, 041007 (2013). Google Scholar  * Paparo, G.

D. & Martin-Delgado, M. A. Google in a quantum network. _Sci. Rep._ 2, 444 (2012). Article  ADS  Google Scholar  * Garnerone, S. Thermodynamic formalism for dissipative quantum walks.

_Phys. Rev. A_ 86, 032342 (2012). Article  ADS  Google Scholar  * Paparo, G., Müller, M., Comellas, F. & Martin-Delgado, M. Quantum google algorithm. _EPJ Plus_ 129, 150 (2014). *

Sánchez-Burillo, E., Duch, J., Gómez-Gardeñes, J. & Zueco, D. Quantum navigation and ranking in complex networks. _Sci. Rep._ 2, 650 (2012). * Lu, D. et al. Chiral Quantum Walks. _Phys.

Rev. A_ 93, 0423902 (2016). THIS PAPER EXPERIMENTALLY REALIZES CHIRAL QUANTUM WALKS (WALKS THAT DIRECT TRANSPORT MODULATED TIME-SYMMETRY BREAKING AS PROPOSED IN [65]. * Faccin, M., Migdał,

P., Johnson, T. H., Bergholm, V. & Biamonte, J. D. Community detection in quantum complex. _Netw. Phys. Rev. X_ 4, 041012 (2014). Google Scholar  * Watts, D. J. & Strogatz, S. H.

Collective dynamics of small-world networks. _Nature_ 393, 440–442 (1998). Article  ADS  MATH  Google Scholar  * Barabási, A.-L. & Albert, R. Emergence of scaling in random networks.

_Science_ 286, 509–512 (1999). Article  ADS  MathSciNet  MATH  Google Scholar  * Boccaletti, S., Latora, V., Moreno, Y., Chavez, M. & Hwang, D.-U. Complex networks: structure and

dynamics. _Phys. Rep._ 424, 175–308 (2006). Article  ADS  MathSciNet  MATH  Google Scholar  * Kivelä, M. et al. Multilayer networks. _J. complex Netw._ 2, 203–271 (2014). Article  Google

Scholar  * De Domenico, M., Granell, C., Porter, M. A. & Arenas, A. The physics of spreading processes in multilayer networks. _Nat. Phys._ 12, 901–906 (2016). Article  Google Scholar  *

Guimera, R. & Amaral, L. A. N. Functional cartography of complex metabolic networks. _Nature_ 433, 895–900 (2005). Article  ADS  Google Scholar  * Palla, G., Derényi, I., Farkas, I.

& Vicsek, T. Uncovering the overlapping community structure of complex networks in nature and society. _Nature_ 435, 814–818 (2005). Article  ADS  Google Scholar  * Song, C., Havlin, S.

& Makse, H. A. Self-similarity of complex networks. _Nature_ 433, 392–395 (2005). Article  ADS  Google Scholar  * Colizza, V., Flammini, A., Serrano, M. A. & Vespignani, A. Detecting

rich-club ordering in complex networks. _Nat. Phys._ 2, 110–115 (2006). Article  Google Scholar  * Boguna, M., Krioukov, D. & Claffy, K. C. Navigability of complex networks. _Nat.

Phys._ 5, 74–80 (2009). Article  Google Scholar  * Vespignani, A. Modelling dynamical processes in complex socio-technical systems. _Nat. Phys._ 8, 32–39 (2012). Article  MathSciNet  Google

Scholar  * Liu, Y.-Y., Slotine, J.-J. & Barabási, A.-L. Controllability of complex networks. _Nature_ 473, 167–173 (2011). Article  ADS  Google Scholar  * Albert, R., Jeong, H. &

Barabási, A.-L. Error and attack tolerance of complex networks. _Nature_ 406, 378–382 (2000). Article  ADS  Google Scholar  * Callaway, D. S., Newman, M. E., Strogatz, S. H. & Watts, D.

J. Network robustness and fragility: percolation on random graphs. _Phys. Rev. Lett._ 85, 5468 (2000). Article  ADS  Google Scholar  * Buldyrev, S. V., Parshani, R., Paul, G., Stanley, H. E.

& Havlin, S. Catastrophic cascade of failures in interdependent networks. _Nature_ 464, 1025–1028 (2010). Article  ADS  Google Scholar  * Gao, J., Buldyrev, S. V., Stanley, H. E. &

Havlin, S. Networks formed from interdependent networks. _Nat. Phys._ 8, 40–48 (2012). Article  Google Scholar  * Radicchi, F. & Arenas, A. Abrupt transition in the structural formation

of interconnected networks. _Nat. Phys._ 9, 717–720 (2013). Article  Google Scholar  * De Domenico, M., Solé-Ribalta, A., Gómez, S. & Arenas, A. Navigability of interconnected networks

under random failures. _Proc. Natl Acad. Sci._ 111, 8351–8356 (2014). Article  ADS  MathSciNet  MATH  Google Scholar  * De Domenico, M. & Biamonte, J. Spectral entropies as

information-theoretic tools for complex network comparison. _Phys. Rev. X_ 6, 041062 (2016). THIS PAPER DEVELOPS AN INFORMATION THEORY APPROACH TO STUDY COMPLEX NETWORKS AND BUILDS ON

SPECTRAL METHODS FOUND IN QUANTUM STATISTICAL MECHANICS. Google Scholar  * Cuquet, M. & Calsamiglia, J. Entanglement percolation in quantum complex networks. _Phys. Rev. Lett._ 103,

240503 (2009). Article  ADS  MathSciNet  Google Scholar  * Perseguers, S., Lewenstein, M., Acín, A. & Cirac, J. Quantum random networks. _Nat. Phys._ 6, 539–543 (2010). Article  Google

Scholar  * Cirac, J. I., Zoller, P., Kimble, H. J. & Mabuchi, H. Quantum state transfer and entanglement distribution among distant nodes in a quantum network. _Phys. Rev. Lett._ 78,

3221 (1997). Article  ADS  Google Scholar  * Chaneliere, T. et al. Storage and retrieval of single photons transmitted between remote quantum memories. _Nature_ 438, 833–836 (2005). Article

  ADS  Google Scholar  * Wilk, T., Webster, S. C., Kuhn, A. & Rempe, G. Single-atom single-photon quantum interface. _Science_ 317, 488–490 (2007). Article  ADS  Google Scholar  *

Politi, A., Cryan, M. J., Rarity, J. G., Yu, S. & O’Brien, J. L. Silica-on-silicon waveguide quantum circuits. _Science_ 320, 646–649 (2008). Article  ADS  Google Scholar  * Ritter, S.

et al. An elementary quantum network of single atoms in optical cavities. _Nature_ 484, 195–200 (2012). Article  ADS  Google Scholar  * Aspuru-Guzik, A. & Walther, P. Photonic quantum

simulators. _Nat. Phys._ 8, 285–291 (2012). Article  Google Scholar  * De Domenico, M., Nicosia, V., Arenas, A. & Latora, V. Structural reducibility of multilayer networks. _Nat.

Commun._ 6, 6864 (2015). Article  Google Scholar  * Schieber, T. A. et al. Quantification of network structural dissimilarities. _Nat. Commun._ 8, 13928 (2017). Article  ADS  Google Scholar

  * Ambjørn, J., Jurkiewicz, J. & Loll, R. Emergence of a 4d world from causal quantum gravity. _Phys. Rev. Lett._ 93, 131301 (2004). Article  ADS  MathSciNet  Google Scholar  * Levin,

M. A. & Wen, X.-G. String-net condensation: A physical mechanism for topological phases. _Phys. Rev. B_ 71, 045110 (2005). Article  ADS  Google Scholar  * Konopka, T., Markopoulou, F.

& Severini, S. Quantum graphity: a model of emergent locality. _Phys. Rev. D._ 77, 104029 (2008). Article  ADS  MathSciNet  Google Scholar  * Rovelli, C. & Speziale, S. Geometry of

loop quantum gravity on a graph. _Phys. Rev. D._ 82, 044018 (2010). Article  ADS  Google Scholar  * Vinokur, V. M. et al. Superinsulator and quantum synchronization. _Nature_ 452, 613–615

(2008). Article  ADS  Google Scholar  * Emerson, J., Weinstein, Y. S., Saraceno, M., Lloyd, S. & Cory, D. G. Pseudo-random unitary operators for quantum information processing. _Science_

302, 2098–2100 (2003). Article  ADS  MathSciNet  MATH  Google Scholar  * Brown, W. G. & Viola, L. Convergence rates for arbitrary statistical moments of random quantum circuits. _Phys.

Rev. Lett._ 104, 250501 (2010). Article  ADS  Google Scholar  * Bianconi, G. & Barabási, A.-L. Bose-einstein condensation in complex networks. _Phys. Rev. Lett._ 86, 5632 (2001). THIS

PAPER DISCOVERS THAT CERTAIN COMPLEX NETWORKS MODELS ARE RELATED TO QUANTUM STATISTICS. Article  ADS  Google Scholar  * Reichardt, J. & Bornholdt, S. Detecting fuzzy community structures

in complex networks with a potts model. _Phys. Rev. Lett._ 93, 218701 (2004). Article  ADS  Google Scholar  * Garlaschelli, D. & Loffredo, M. I. Generalized bose-fermi statistics and

structural correlations in weighted networks. _Phys. Rev. Lett._ 102, 038701 (2009). Article  ADS  Google Scholar  * Dorogovtsev, S. N., Goltsev, A. V. & Mendes, J. F. Critical phenomena

in complex networks. _Rev. Mod. Phys._ 80, 1275 (2008). Article  ADS  Google Scholar  * Newman, M. E. J. The structure and function of complex networks. _SIAM Rev._ 45, 167–256 (2003).

Article  ADS  MathSciNet  MATH  Google Scholar  * Greenberger, D. M., Horne, M. A. & Zeilinger, A. Going beyond bell's theorem. In _Bell''s Theorem, Quantum Theory and

Conceptions of the Universe_, 69–72 (Springer, 1989). * Cardillo, A., Galve, F., Zueco, D. & Gómez-Gardeñes, J. Information sharing in quantum complex networks. _Phys. Rev. A_ 87, 052312

(2013). Article  ADS  Google Scholar  * Carvacho, G. et al. Experimental violation of local causality in a quantum network. _Nat. Commun._ 8, 14775 (2017). Article  ADS  Google Scholar  *

Ambainis, A. Quantum walks and their algorithmic applications. _Int. J. Quantum Inf._ 1, 507–518 (2003). Article  MATH  Google Scholar  * Shenvi, N., Kempe, J. & Whaley, K. B. Quantum

random-walk search algorithm. _Phys. Rev. A_ 67, 052307 (2003). Article  ADS  Google Scholar  * Rossi, L., Torsello, A. & Hancock, E. R. Measuring graph similarity through

continuous-time quantum walks and the quantum jensen-shannon divergence. _Phys. Rev. E_ 91, 022815 (2015). Article  ADS  MathSciNet  Google Scholar  * Wong, T. G. & Meyer, D. A.

Irreconcilable Difference Between Quantum Walks and Adiabatic Quantum Computing. Phys. Rev. A 93, 062313 (2016). * Chakraborty, S., Novo, L., Di Giorgio, S. & Omar, Y. Optimal quantum

spatial search on random temporal networks. Phys. Rev. Lett. 119, 220503 (2017). * Childs, A., Farhi, E. & Gutmann, S. An example of the difference between quantum and classical random

walks. _Quantum Inf. Process_ 1, 35–43 (2002). Article  MathSciNet  MATH  Google Scholar  * Whitfield, J. D., Rodríguez-Rosario, C. A. & Aspuru-Guzik, A. Quantum stochastic walks: a

generalization of classical random walks and quantum walks. _Phys. Rev. A_ 81, 022323 (2010). Article  ADS  Google Scholar  * Zimboras, Z. et al. Quantum transport enhancement by

time-reversal symmetry breaking. _Sci. Rep._ 3, 2361 (2013). Article  Google Scholar  * Chakraborty, S., Novo, L., Ambainis, A. & Omar, Y. Spatial search by quantum walk is optimal for

almost all graphs. _Phys. Rev. Lett._ 116, 100501 (2016). Article  ADS  Google Scholar  * Masuda, N., Porter, M. A. & Lambiotte, R. Random walks and diffusion on networks. _ArXiv

e-prints_ 1612.03281 (2016). * Noh, J. D. & Rieger, H. Random walks on complex networks. _Phys. Rev. Lett._ 92, 118701 (2004). Article  ADS  Google Scholar  * Burda, Z., Duda, J., Luck,

J. & Waclaw, B. Localization of the maximal entropy random walk. _Phys. Rev. Lett._ 102, 160602 (2009). Article  ADS  Google Scholar  * Mülken, O., Dolgushev, M. & Galiceanu, M.

Complex quantum networks: from universal breakdown to optimal transport. _Phys. Rev. E_ 93, 022304 (2016). Article  ADS  MathSciNet  Google Scholar  * Cameron, S. et al. Universal state

transfer on graphs. _Linear Algebra its. Appl._ 455, 115–142 (2014). Article  MathSciNet  MATH  Google Scholar  * Tödtli, B. et al. Continuous-time quantum walks on directed bipartite

graphs. _ArXiv e-prints_ 1606.00992 (2016). * Baez, J. C. & Biamonte, J. Quantum techniques for stochastic mechanics. _ArXiv e-prints_ 1209.3632 (2012). * Garnerone, S., Zanardi, P.

& Lidar, D. A. Adiabatic quantum algorithm for search engine ranking. _Phys. Rev. Lett._ 108, 230506 (2012). Article  ADS  Google Scholar  * Breuer, H. & Petruccione, F. _The Theory

of Open Quantum Systems_, https://books.google.com.mt/books?id=DkcJPwAACAAJ (OUP Oxford, 2007). * Sinkovicz, P., Kurucz, Z., Kiss, T. & Asbóth, J. K. Quantized recurrence time in unital

iterated open quantum dynamics. _Phys. Rev. A_ 91, 042108 (2015). Article  ADS  Google Scholar  * Manzano, D. & Hurtado, P. I. Symmetry and the thermodynamics of currents in open quantum

systems. _Phys. Rev. B_ 90, 125138 (2014). Article  ADS  Google Scholar  * Szegedy, M. Quantum speed-up of markov chain based algorithms. In _Foundations of Computer Science, 2004.

Proceedings. 45th Annual IEEE Symposium on_, 32–41 (IEEE, 2004). * Javarone, M. A. & Armano, G. Quantum–classical transitions in complex networks. _J. Stat. Mech._ 2013, P04019 (2013).

Article  Google Scholar  * Bianconi, G. & Rahmede, C. Network geometry with flavor: from complexity to quantum geometry. _Phys. Rev. E_ 93, 032315 (2016). Article  ADS  MathSciNet 

Google Scholar  * Bianconi, G. Interdisciplinary and physics challenges of network theory. _EPL_ 111, 56001 (2015). Article  ADS  Google Scholar  * Pincus, S. M. Approximate entropy as a

measure of system complexity. _Proc. Natl Acad. Sci._ 88, 2297–2301 (1991). Article  ADS  MathSciNet  MATH  Google Scholar  * Costa, M., Goldberger, A. L. & Peng, C.-K. Multiscale

entropy analysis of complex physiologic time series. _Phys. Rev. Lett._ 89, 068102 (2002). Article  ADS  Google Scholar  * Braunstein, S. L., Ghosh, S. & Severini, S. The laplacian of a

graph as a density matrix: a basic combinatorial approach to separability of mixed states. _Ann. Comb._ 10, 291–317 (2006). Article  MathSciNet  MATH  Google Scholar  * Anand, K., Bianconi,

G. & Severini, S. Shannon and von neumann entropy of random networks with heterogeneous expected degree. _Phys. Rev. E_ 83, 036109 (2011). Article  ADS  MathSciNet  Google Scholar  * De

Domenico, M. et al. Mathematical formulation of multilayer networks. _Phys. Rev. X_ 3, 041022 (2013). Google Scholar  * Boccaletti, S. et al. The structure and dynamics of multilayer

networks. _Phys. Rep._ 544, 1–122 (2014). Article  ADS  MathSciNet  Google Scholar  * Fanuel, M., Alaiz, C. & Suykens, J. Magnetic eigenmaps for community detection in directed networks.

_Phys. Rev. E_ 95, 022302 (2016). Article  ADS  MathSciNet  Google Scholar  * Fanuel, M., Alaz, C. M., ngela Fernndez & Suykens, J. A. Magnetic eigenmaps for the visualization of

directed networks. _Appl. Comput. Harmon. Anal._ 44 _,_ 189–199 (2017). * Bentley, B. et al. The multilayer connectome of caenorhabditis elegans. _PLOS Comput. Biol._ 12, e1005283 (2016).

Article  Google Scholar  * De Domenico, M., Sasai, S. & Arenas, A. Mapping multiplex hubs in human functional brain networks. _Front. Neurosci._ 10, 326 (2016). Article  Google Scholar 

* Ding, T. & Schloss, P. D. Dynamics and associations of microbial community types across the human body. _Nature_ 509, 357 (2014). Article  ADS  Google Scholar  * Albert, R. &

Barabási, A.-L. Statistical mechanics of complex networks. _Rev. Mod. Phys._ 74, 47–97 (2002). Article  ADS  MathSciNet  MATH  Google Scholar  * Caldarelli, G., Capocci, A., De Los Rios, P.

& Muñoz, M. A. Scale-free networks from varying vertex intrinsic fitness. _Phys. Rev. Lett._ 89, 258702 (2002). Article  ADS  Google Scholar  * Newman, M. E. Communities, modules and

large-scale structure in networks. _Nat. Phys._ 8, 25–31 (2012). Article  Google Scholar  * Fortunato, S. Community detection in graphs. _Phys. Rep._ 486, 75–174 (2010). Article  ADS 

MathSciNet  Google Scholar  * Horn, D. Clustering via hilbert space. _Phys. A: Stat. Mech. Appl._ 302, 70–79 (2001). PROC. INT. WORKSHOP ON FRONTIERS IN THE PHYSICS OF COMPLEX SYSTEMS.

Article  MathSciNet  MATH  Google Scholar  * Weinstein, M. & Horn, D. Dynamic quantum clustering: a method for visual exploration of structures in data. _Phys. Rev. E_ 80, 066117 (2009).

Article  ADS  Google Scholar  * Wittek, P. High-performance dynamic quantum clustering on graphics processors. _J. Comput. Phys._ 233, 262–271 (2013). Article  ADS  Google Scholar  *

Tsomokos, D. I. Quantum walks on complex networks with connection instabilities and community structure. _Phys. Rev. A_ 83, 052315 (2011). Article  ADS  Google Scholar  * Bennett, C. H.

& DiVincenzo, D. P. Quantum information and computation. _Nature_ 404, 247–255 (2000). Article  ADS  MATH  Google Scholar  * Markov, I. L. Limits on fundamental limits to computation.

_Nature_ 512, 147–154 (2014). Article  ADS  Google Scholar  * Scheffer, M. et al. Anticipating critical transitions. _Science_ 338, 344–348 (2012). Article  ADS  Google Scholar  * Gao, J.,

Barzel, B. & Barabási, A.-L. Universal resilience patterns in complex networks. _Nature_ 530, 307–312 (2016). Article  ADS  Google Scholar  * Motter, A. E. Cascade control and defense in

complex networks. _Phys. Rev. Lett._ 93, 098701 (2004). Article  ADS  Google Scholar  Download references ACKNOWLEDGEMENTS J.D.B. acknowledges the Foundational Questions Institute (FQXi,

under grant FQXi-RFP3-1322) for financial support. M.F. acknowledges the MOVE-IN fellowship program for financial support. We thank Alex Arenas and Leonie Mueck for useful feedback, and the

Institute for Quantum Computing at the University of Waterloo and the Perimeter Institute for Theoretical Physics for funding and allowing us to organize the first workshop on the

intersection of these topics. Diagrams are courtesy of Lusa Zheglova (illustrator). AUTHOR INFORMATION AUTHORS AND AFFILIATIONS * Deep Quantum Labs, Skolkovo Institute of Science and

Technology, 3 Nobel Street, Moscow, 143026, Russia Jacob Biamonte * ICTEAM, Université Catholique de Louvain, Euler Building 4, Avenue Lemaitre, B-1348, Louvain-la-Neuve, Belgium Mauro

Faccin * CoMuNe Lab, Fondazione Bruno Kessler, Via Sommarive 18, 38123, Povo, TN, Italy Manlio De Domenico Authors * Jacob Biamonte View author publications You can also search for this

author inPubMed Google Scholar * Mauro Faccin View author publications You can also search for this author inPubMed Google Scholar * Manlio De Domenico View author publications You can also

search for this author inPubMed Google Scholar CONTRIBUTIONS J.D.B., M.F. and M.D.D. designed and wrote this review. CORRESPONDING AUTHORS Correspondence to Jacob Biamonte, Mauro Faccin or

Manlio De Domenico. ETHICS DECLARATIONS COMPETING INTERESTS The authors declare no competing Interests. ADDITIONAL INFORMATION PUBLISHER’S NOTE: Springer Nature remains neutral with regard

to jurisdictional claims in published maps and institutional affiliations. RIGHTS AND PERMISSIONS OPEN ACCESS This article is licensed under a Creative Commons Attribution 4.0 International

License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source,

provide a link to the Creative Commons license, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons

license, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons license and your intended use is not permitted by

statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this license, visit

http://creativecommons.org/licenses/by/4.0/. Reprints and permissions ABOUT THIS ARTICLE CITE THIS ARTICLE Biamonte, J., Faccin, M. & De Domenico, M. Complex networks from classical to

quantum. _Commun Phys_ 2, 53 (2019). https://doi.org/10.1038/s42005-019-0152-6 Download citation * Received: 13 May 2018 * Accepted: 19 April 2019 * Published: 21 May 2019 * DOI:

https://doi.org/10.1038/s42005-019-0152-6 SHARE THIS ARTICLE Anyone you share the following link with will be able to read this content: Get shareable link Sorry, a shareable link is not

currently available for this article. Copy to clipboard Provided by the Springer Nature SharedIt content-sharing initiative