We introduce a mapping between graphs and pure quantum bipartite states and show that the associated entanglement entropy conveys non-trivial information about the structure of the graph. Our primary goal is to investigate the family of random graphs known as complex networks. In the case of classical random graphs, we derive an analytic expression for the averaged entanglement entropy while for general complex networks we rely on numerics. For a large number of nodes n we find a scaling where both the prefactor c and the sub-leading O (1) term g e are characteristic of the different classes of complex networks. In particular, g e encodes topological features of the graphs and is named network topological entropy. Our results suggest that quantum entanglement may provide a powerful tool for the analysis of large complex networks with non-trivial topological properties.
Recent work has exposed the idea that interesting quantum-like (QL) probability laws, including interference effects, can be manifest in classical systems. Here, we propose a model for QL states and QL bits. We suggest a way that huge, complex systems can host robust states that can process information in a QL fashion. Axioms that such states should satisfy are proposed. Specifically, it is shown that building blocks suited for QL states are networks, possibly very complex, that we defined based on k -regular random graphs. These networks can dynamically encode a lot of information that is distilled into the emergent states we can use for QL processing. Although the emergent states are classical, they have properties analogous to quantum states. Concrete examples of how QL functions are possible are given. The possibility of a ‘QL advantage’ for computing-type operations and the potential relevance for new kinds of function in the brain are discussed and left as open questions.
Abstract We establish a framework for constructing robust quantum-like states based on k -regular bipartite graphs, aiming to realize quantum-inspired information processing through classical oscillatory networks. We first introduce the k -regular bipartite graph and its mathematical representation, and analyze its intrinsic spectral properties. In contrast to ordinary k -regular non-bipartite graphs, the intrinsic bipartite symmetry, enhanced spectral gap, and global delocalization mechanism confer superior robustness to the emergent states. We verify that the emergent states of these bipartite graphs satisfy the axiomatic requirements of quantum-like states, and show that the global delocalization property ensures stable operation under structural noise. Based on the axiomatic requirements of quantum-like states, we further realize basic quantum-inspired gate operations in the classical network framework. Our numerical simulations reveal that the k -regular bipartite graph system exhibits enhanced coherence and stability under noise interference compared with non-bipartite graph systems. This research not only broadens the application boundaries of quantum-inspired computing but also provides a new feasible path for the practical implementation of classical simulation of quantum information processing.
Networks constitute efficient tools for assessing universal features of complex systems. In physical contexts, classical as well as quantum networks are used to describe a wide range of phenomena, such as phase transitions, intricate aspects of many-body quantum systems, or even characteristic features of a future quantum internet. Random quantum networks and their associated directed graphs are employed for capturing statistically dominant features of complex quantum systems. Here, we develop an efficient iterative method capable of evaluating the probability of a graph being strongly connected. It is proven that random directed graphs with constant edge-establishing probability are typically strongly connected, i.e., any ordered pair of vertices is connected by a directed path. This typical topological property of directed random graphs is exploited to demonstrate universal features of the asymptotic evolution of large random qubit networks. These results are independent of our knowledge of the details of the network topology. These findings suggest that other highly complex networks, such as a future quantum internet, may also exhibit similar universal properties.
Graph states are entangled states that are essential for quantum information processing. As experimental advances enable the realization of large-scale graph states, efficient fidelity estimation methods are crucial for assessing their robustness against noise. However, calculations of exact fidelity become intractable for large systems due to the exponential growth in the number of stabilizers. In this work, we show that the fidelity between any ideal graph state and its noisy counterpart under IID Pauli noise can be mapped to the partition function of a classical spin system, enabling efficient computation via statistical mechanical techniques. Using this approach, we analyze the fidelity for regular graph states under depolarizing noise and uncover the emergence of phase transitions in fidelity between the pure-state regime and the noise-dominated regime. Specifically, in 2D, phase transitions occur only when the degree satisfies d ≥ 6 , while in 3D they already appear at d ≥ 5 . However, for graph states with excessively high degree, such as fully connected graphs, the phase transition disappears. Robustness of graph states against noise is thus determined by their connectivity and spatial dimensionality. Graph states with lower degree and/or dimensionality, which exhibit a smooth crossover, demonstrate greater robustness, while highly connected or higher-dimensional graph states are more fragile. Extreme connectivity, as the fully connected graph state possesses, restores robustness. Furthermore, we show that the fidelity can be rewritten in the form of the partition function of a constraint-percolation problem. Within this picture, we discuss the qualitative difference between 2D regular graph states with d = 6 and d = 5 regarding the presence or absence of a phase transition, as well as the suppressed critical behavior of fully connected graph states.
Higher-order networks take group interactions as given. I ask what happens when a group interaction is made by pairwise dynamics on a graph, and follow it through the transition that decides whether it matters at large scale, Anderson localisation. An emergent hyperedge is a
k-body bound state of a Hamiltonian whose terms live on the vertices and edges of the graph, Borromean when none of its
(k−1)-body faces is bound, detected on a finite graph by a
k-fold coincidence that survives the thermodynamic limit while the
(k−1)-fold ones vanish. Sparse random graphs produce one from the simplest pairwise dynamics: three distinguishable particles with on-site attraction
U and hopping
t bind into a trimer before any pair binds. The thresholds are obtained on the Bethe lattice, in closed form for the pair, in both sectors that an expander graph has and a lattice lacks, the one a condensate sees and the one a Fermi liquid sees. On a disordered graph the emergent hyperedges nucleate on rare deep sites and localise before their parts: the compact trimer, with a narrow band and a threefold sensitivity to site energies, undergoes the Anderson transition at a disorder of
1.6t, against
17t for a single particle and
4t for a pair, and the Fermi liquid of trimers is a glass above a line between
1.5t and
1.7t, where a liquid of single particles at the same density needs
15t to
16t. The transition is the single-particle cavity transition with the composite's hopping and effective disorder. A group interaction made by pairwise dynamics is an order of magnitude more fragile to heterogeneity than the network that makes it.