  Quantum network is the key to enable distributed quantum information
processing. As the single-link communication rate decays exponentially with the
distance, to enable reliable end-to-end quantum communication, the number of
nodes needs to grow with the network scale. For highly connected networks, we
identify a threshold transition in the capacity as the density of network nodes
increases---below a critical density, the rate is almost zero, while above the
threshold the rate increases linearly with the density. Surprisingly, above the
threshold the typical communication capacity between two nodes is independent
of the distance between them, due to multi-path routing enabled by the quantum
network. In contrast, for less connected networks such as scale-free networks,
the end-to-end capacity saturates to constants as the number of nodes
increases, and always decays with the distance. Our results are based on
capacity evaluations, therefore the minimum density requirement for an
appreciable capacity applies to any general protocols of quantum networks.
