Graph Theory Reveals Hard Limits on the Quantum Internet’s Reach

The dream of a quantum internet, in which users separated by continents share entangled states to run unconditionally secure cryptography and delegated quantum computing, runs headlong into physics. Quantum systems degrade as they travel, they cannot be copied to compensate for loss, and any measurement disturbs them. A new theoretical study published in Quantum Information Processing by Abhishek Sadhu, Meghana Ayyala Somayajula, Karol Horodecki and Siddhartha Das confronts these constraints head on, using the mathematics of graphs to ask a deceptively simple question: how large can a quantum network actually be, and how robust, before the tasks it is meant to perform become impossible? The answers, expressed in terms of network diameters, percolation thresholds and critical success probabilities, suggest that even with repeater-based improvements, the reach of quantum communication protocols such as device-independent quantum key distribution is bounded in ways that classical networks never faced.

The difficulty stems from facts that have no classical analogue. Unlike a classical signal, the loss associated with transmitting a quantum state through a lossy channel cannot be reduced with amplifiers, because measuring an unknown quantum state disturbs it and unknown states cannot be cloned. Quantum repeaters offer an alternative: entanglement swapping and, optionally, entanglement purification at intermediate nodes can extend entanglement distribution across lossy channels. The authors model the elementary links of such networks as isotropic states, in which an ideal maximally entangled state is mixed with a useless noisy state, and then track how the quality of these links degrades as they are chained together. This abstraction deliberately ignores implementation details, so that the resulting limitations apply to any technology, from fibre optics on the ground to satellite links above the atmosphere.

The first main result concerns device-independent quantum key distribution, or DI-QKD, in which two parties distil a secret key while trusting only the observed statistics of their devices. The researchers show that a network of isotropic states with visibility parameter lambda has a finite diameter for DI-QKD: any two nodes can be connected by entanglement swapping to produce a device-independent key only if they sit within a critical distance of each other. In a repeater chain of n stations, the visibility shared by the end nodes falls as q^n lambda^(n+1), where q is the success probability of the Bell measurement at each relay. Because the DI-QKD rate vanishes once this effective visibility drops below a critical threshold, gamma_crit = 0.7445 for standard CHSH-based protocols, there is a hard ceiling on how many repeater stations can separate the end nodes. Strikingly, the team also identifies states whose neighbouring links each distil a nonzero key, yet whose end-to-end repeater rate is exactly zero.

Translated into graph-theoretic language, this becomes a statement about percolation. The authors prove a theorem showing that a quantum network with a regular lattice structure will not form percolation in practice for tasks including DI-QKD, entanglement sharing, Bell-CHSH violation and teleportation. They define a network as critically large for a given task when every edge has a success probability bounded by some constant c and at least two nodes lie farther apart than a threshold distance derived from the critical probability p*. For such networks, they prove there must exist at least two vertices that cannot perform the task over any connecting path. In other words, no matter how the lattice is engineered, the connected component that supports the task remains finite, and the network’s effective diameter is bounded by the physics of its elementary links.

The second main result quantifies a trade-off in fibre-based repeater networks equipped with quantum memories. For an entanglement-swapping network in which neighbouring nodes are joined by optical fibres with loss parameter alpha and each node stores its qubits in a lossy memory with parameter beta, the critical fibre length l_cr and critical storage time t_cr satisfy alpha times l_cr plus beta times t_cr less than one over two r times the logarithm of q^r eta_s^(r+1) divided by p*, where r is the number of repeater stations, eta_s the source efficiency and p* the critical success probability. Increasing the number of repeater stations therefore permits shorter fibres and shorter storage times, but the two resources compete. Under a stated assumption that some repeater scheme improves the channel transmittance from eta to eta^(1/f), the team derives an f-fold advantage in both the critical length and the critical time, recovering known results for measurement-device-independent and twin-field quantum key distribution as the cases f = 1 and f = 2.

Turning to real-world architecture, the study analyses a two-layered satellite network for distributing entangled pairs between far-off cities. A global layer of satellites distributes entanglement between ground stations across different cities, while a local optical layer carries the states onward through fibres. Satellite-satellite links are modelled as qubit erasure channels, satellite-ground links as qubit thermal channels capturing atmospheric conditions, and imperfect quantum memories as depolarizing channels. As an illustration, the authors trace a shortest path between ground stations at Bengaluru and Gdansk and compute the average entanglement yield, which decreases both with the number of satellite-to-satellite links and with the total fibre length. The yield formula folds in weather-dependent atmospheric parameters, source efficiencies, Bell-measurement success probabilities and the time the state spends degrading in memory, offering a concrete benchmark for what currently available technology could deliver.

The paper also applies its framework to a global mesh network built from 3462 major airports connected by 25482 airline routes, with edge weights set by the distances between airports. The longest route, between Singapore Changi and New York John F. Kennedy, spans roughly 15331 kilometres, while the average airport separation is about 1952 kilometres. For this network the team reports the entanglement yield under currently available and desirable future technology, and identifies the most critical airports, those whose removal most damages the network’s function, including Istanbul, Dubai, Anchorage, Beijing Capital, Chicago O’Hare and Los Angeles. A further example considers a fibre-based star network linking the U.S. Department of Energy in Washington to laboratories involved in the National Quantum Initiative, deriving an upper bound on the channel loss parameter that still permits entanglement sharing between the hub and each leaf node.

Quantum processors themselves enter the analysis as small-scale networks. Treating the processor layouts of Google, IBM and Rigetti as graphs, the authors introduce two robustness measures, link sparsity and node connection strength, and find that the 54-qubit square topology of Google’s Sycamore processor exhibits the highest node connection strength and the lowest link sparsity among the architectures considered. Extending the square layout to a hypothetical 1024-qubit, 32-by-32 processor, they compute a link sparsity of 0.9962 and show that inner nodes, sharing edges with four neighbours, carry the highest values of a critical parameter that identifies nodes essential to network function. Corner and boundary nodes fare worse, a result that maps directly onto which qubits are most costly to lose in a large superconducting chip.

Finally, the study supplies algorithmic primitives for operating such networks: a Dijkstra-based procedure for finding the shortest network path between a pair of end nodes, a network-construction algorithm that guarantees distinct paths between the nodes of two parties, a heuristic for ranking critical nodes, and a producer-consumer scheme for allocating quantum states at a buffer node that stores incoming entanglement and serves multiple clients. Together, the authors argue, these results and tools provide a theoretical baseline for benchmarking the critical parameters, distances, storage times, success probabilities and node importances, that will decide whether the quantum Internet can scale from laboratory demonstrations to a global infrastructure. The message is sobering but constructive: the limits are finite, measurable, and now written in the language of graphs.

Subject of Research: Graph-theoretic analysis of the practical limits on the robustness and scalability of the quantum Internet

Article Title: Practical limitations on robustness and scalability of quantum Internet

Article References: Sadhu, A., Somayajula, M. A., Horodecki, K., & Das, S. (2026). Practical limitations on robustness and scalability of quantum Internet. Quantum Information Processing, 25(11), Article 351. https://doi.org/10.1007/s11128-026-05312-z

Image Credits: AI Generated

DOI: 10.1007/s11128-026-05312-z

Keywords: quantum internet, quantum networks, DI-QKD, entanglement distribution, quantum repeaters, graph theory, percolation, quantum memories, satellite quantum communication, quantum processors, network robustness, entanglement swapping