Source-linked AI summary
Complex Networks from Classical to Quantum
Jacob Biamonte, Mauro Faccin, Manlio De Domenico
TL;DR
The paper reviews how complex-network theory and quantum information can inform one another, addressing their intersection across quantum networks, transport, and network analysis. It synthesizes quantum-inspired measures and network-inspired models, highlighting entangled random graphs, percolation, and quantum-network effects. The review concludes that a unified information-theoretic framework remains incomplete, especially for structure–dynamics relations in quantum networks.
Problem
The paper addresses how complex-network methods and quantum-information concepts can be combined to analyze classical and quantum networked systems.
Method
The paper reviews advances using quantum-inspired entropic measures for networks and network-inspired measures for quantum systems.
Results
The review identifies cross-field tools and findings spanning quantum random graphs, entanglement percolation, quantum-walk network comparisons, and entropy-based network analysis.
Takeaways & Limitations
The intersection supports a developing network information theory applicable to both classical and quantum networked systems.
Takeaways & Limitations
The interplay between structure and dynamics remains almost entirely unclear for quantum networks, and current scale-free models require experimental verification.
Abstract
from arXiv · showhide
Recent progress in applying complex network theory to problems in quantum information has resulted in a beneficial crossover. 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.
NETWORKS IN QUANTUM PHYSICS VS COMPLEXITY
This section maps how network and graph theory arise across quantum information and computation, distinguishing general networks from complex networks. It catalogs cross-pollination between quantum-information tools, network analysis, and quantum algorithms.
- NETWORKS IN QUANTUM PHYSICS VS COMPLEXITY: The review catalogs published work at the intersection of quantum information and computation with complex network theory.Its scope spans theoretical, experimental, and computational perspectives.
- NETWORKS IN QUANTUM PHYSICS VS COMPLEXITY: Network theory represents relationships between units using nodes and edges, which may be directed and weighted.Node degree counts edges, while node strength sums corresponding edge weights.
- NETWORKS IN QUANTUM PHYSICS VS COMPLEXITY: Network and graph theory appears throughout quantum theory, including quantum spins, quantum random walks, quantum circuits, tensor network states, and quantum graph states.The section contrasts these broad uses with the narrower notion of complex networks.
- NETWORKS IN QUANTUM PHYSICS VS COMPLEXITY: Complex networks are typically identified by emergent properties such as a non-trivial distribution in node degree.This distinguishes complex networks from graph-theoretic descriptions used to deduce properties of quantum systems.
QUANTUM NETWORKS BASED ON ENTANGLED STATES
Entangled-state quantum networks replace classical links with entangled pairs whose tunable entanglement can reproduce random-graph connectivity. This framework controls subgraph structure and exposes quantum-network effects in connectivity and information distribution.
- QUANTUM NETWORKS BASED ON ENTANGLED STATES: Quantum networks can encode connections as entangled states between qubits located at different nodes.The reviewed construction replaces each classical link with an entangled pair shared by the corresponding nodes.
- QUANTUM NETWORKS BASED ON ENTANGLED STATES: Entanglement between two nodes can be tuned to equal the link probability p in an Erdős–Rényi graph G(N, p).Here, N is the number of nodes and p is the probability of a link between any two nodes.
- QUANTUM NETWORKS BASED ON ENTANGLED STATES: LOCC conversion of each link to a maximally entangled state succeeds with probability p, matching the corresponding classical link probability.The entanglement parameter satisfies 0 ≤ p ≤ 1.
- QUANTUM NETWORKS BASED ON ENTANGLED STATES: As N approaches infinity with z = −2, the quantum network can realize the topology of any finite subgraph with probability approaching unity.Changing system size controls the number and type of subgraphs, including multipartite states such as Greenberger-Horne-Zeilinger states.
- QUANTUM NETWORKS BASED ON ENTANGLED STATES: Entanglement percolation maps perfect quantum-channel formation onto link distribution and reveals a sharp contrast between entangled and product states.For qubits, the probability of an infinitely long entangled path is unity, whereas it is zero for product states; classical entanglement percolation is not generally optimal.
- QUANTUM NETWORKS BASED ON ENTANGLED STATES: Quantum-network effects can place the largest information stores at intermediate-connectivity nodes rather than hubs and generate non-bilocal correlations between distant qubits.The latter provides evidence for violation of local causality in a quantum network.
QUANTUM NETWORKS BASED ON PHYSICAL CONNECTIVITY
Quantum networks based on physical connectivity use quantum walks to model transport, computation, and ranking on networks. Reviewed approaches include unitary, dissipative, and mixed quantum evolutions, revealing topology-dependent transport effects and improvements to quantum PageRank.
- Quantum walks and physical networks: Quantum walks on physically interconnected systems model quantum information transport and provide a universal representation of quantum computation on graphs.These systems include atoms and superconducting quantum electronics, and quantum walks are also used for quantum search.
- Topology and transport: Chiral quantum walks use complex phases in a Hermitian adjacency matrix to direct transport, while bipartite topology prevents breaking time-reversal symmetry in transport probabilities.Transport suppression remains possible on bipartite graphs, including trees, linear chains, and graphs containing only even cycles.
- Topology and transport: Analytical comparisons between stochastic and quantum walks expose differences that contribute to understanding novel complex features in quantum systems.The reviewed crossover treats quantum walks as both practical transport models and a setting for comparing quantum and stochastic dynamics.
- Quantum walks and physical networks: Long-time averaging converts fluctuating closed-system walk probabilities into node-occupation probabilities determined by energy eigenspaces.The evolution uses Ut = e^-iQt, with the initial state and quantum generator defining the walk.
- Quantum PageRank: Quantum PageRank has been implemented through adiabatic, unitary-dissipative, and Szegedy-type quantum-walk constructions based on the Google matrix.The approaches use Hamiltonians, jump operators, Hilbert-space superpositions, coin operations, swaps, or time-averaged node probabilities.
- Quantum PageRank: Quantum PageRank resolves classical degeneracy, enhances secondary-hub importance, and can converge faster for certain values of α.The mixed quantum evolution interpolates between unitary and stochastic behavior, with a stationary state guaranteed for α ∈ (0, 1].
TOWARDS UNIFIED ANALYSIS OF NETWORK COMPLEXITY
The paper develops a unified view of network complexity by translating information-theoretic and quantum tools between classical and quantum systems. Applications include entropy, network comparison, multilayer analysis, quantum walks, and quantum community detection, while some measures and dynamical comparisons retain important limitations.
- Information-theoretic framework: Von Neumann entropy of a rescaled Laplacian equals the Shannon entropy of its eigenvalue spectrum and extends to multilayer networks.This construction treats the normalized Laplacian as analogous to a quantum density matrix.
- Information-theoretic framework: Because rescaled-Laplacian von Neumann entropy can violate sub-additivity, diffusion-based entropy uses information propagation and time as a resolution parameter.The diffusion solution is ψ(t) = exp(−Lt)ψ(0), and its normalized propagator defines the density matrix.
- Information-theoretic framework: Quantum-inspired information measures provide a basis for developing an information theory of complex networks with applications to system comparison.Quantum information tools are applied to classical networks, while network descriptors are transferred to quantum systems.
- Network comparison: Network likelihood enables statistical inference and model selection using Fisher information, Akaike and Bayesian information criteria, and minimum description length.It follows from minimizing Kullback-Leibler divergence between a reference distribution and a parametric model.
- Network comparison: Quantum Jensen-Shannon divergence between continuous-time quantum walks is maximal when the compared original networks are isomorphic.The networks are merged before the walks evolve on the composite system.
- Applications: The framework has been applied to biological multilayer systems, identifying redundancy in genetic networks, complementary structures in C. elegans networks, and community associations in the human microbiome.These applications connect information-theoretic network measures to molecular, neuronal, and microbial organization.
- Quantum dynamics: Quantum network applications reveal both classical correspondences and distinct dynamical constraints: generators can share eigenvalues, yet the quantum walk may lack a stationary state.In the ground state, average node occupation depends on node degree as in the classical case; outside it, a quantumness measure can be defined.
- Quantum dynamics: Quantum community-detection methods use closeness measures based on transport and fidelity, augmenting ad hoc partitioning approaches for quantum transport systems.The measures are related to Hamiltonian couplings and eigenstate localization.
OUTLOOK IN QUANTUM NETWORK SCIENCE
The outlook calls for expanding complex-network methods into quantum physics while porting quantum-domain methods into network science. It identifies information-theoretic foundations, structure–dynamics relations, and experimental validation as central directions for future progress.
- Quantum complex-network research must expand its application domain while also importing quantum methods into network science.
- Information-processing capacity offers a promising but still early framework for quantifying networked classical systems.
- The interplay between structure and dynamics remains almost entirely unclear for quantum networks.
- Scale-free quantum networks remain a toy model whose theoretical predictions require experimental verification.
- A theoretical foundation for quantum complex networks could have substantial impact on information and communication technology.