  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.
