Quantum complex networks

In recent years, new algorithms and cryptographic protocols based on the laws of quantum physics have been designed to outperform classical communication and computation. We show that the quantum world also opens up new perspectives in the field of complex networks. Already the simplest model of a classical random network changes dramatically when extended to the quantum case, as we obtain a completely distinct behavior of the critical probabilities at which different subgraphs appear. In particular, in a network of N nodes, any quantum subgraph can be generated by local operations and classical communication if the entanglement between pairs of nodes scales as 1/N^2.