CS Paper Radar

Shortest-path percolation and structural robustness of quantum internet networks

Victor H. F. Francheto, Thomas Peron

cs.SI physics.soc-phcond-mat.stat-mechquant-ph ·submitted 2026-11-16 20:20 UTC · v1
code/data

Abstract

We study shortest-path percolation on spatial networks that model the quantum internet based on optical fibers. In this process, the removal of paths describes the consumption of the entangled links used for communication. We compare finite and unrestricted path-length bounds for networks whose average degree either increases with system size or remains approximately constant. We show that networks become more robust as the average degree increases, whereas networks with approximately constant average degree exhibit a data collapse for the fixed finite bounds considered. Using Monte Carlo sampling of the shortest-path-length distribution, we estimate an equivalent path cost, a finite bound that approximately reproduces the degradation of the network in the unrestricted case. For networks with fixed average degree, this cost grows approximately as the square root of the number of nodes. Increasing the bound beyond this value requires additional computation time without appreciably changing the percolation dynamics. As a complementary result, for Erdős-Rényi random networks, we find an empirical relation between the initial average degree and the approximately common crossing point of the percolation curves for different path-length bounds.

Comment
20 pages, 18 figures. Code available at https://github.com/VictorFrancheto/shortest-path-percolation-implementation

Closest papers

Nearest neighbours by meaning across the whole index.

Criticality and universality in network dismantling

cs.SI physics.soc-phcond-mat.stat-mech ·2026-08-27 ·Lorenzo Cirigliano, Claudio Castellano, Minsuk Kim, Filippo Radicchi, Hanlin Sun
similarity 0.59
Abstract · 17 pages, 11 figures, 2 tables + supplemental material

Identifying the smallest set of elements whose removal dismantle a complex network, known as the network dismantling problem, is a fundamental task with many practical applications. Whereas network dismantling has been extensively studied over the past decade, most work has focused on developing efficient algorithms for large but finite networks. By contrast, the physics of the network dismantling process, namely how the network structural connectivity is affected by the removal of nodes or edges, remains largely unexplored in the thermodynamic limit. Here, we shed light on this understudied aspect of network dismantling by introducing an adaptive biased percolation process able to optimally dismantle a network. Through a systematic analysis of synthetic network models, we find that the proposed percolation process displays a universal phase transition, characterized by the abrupt and simultaneous disappearance of both the giant connected component and the largest 2-core, across networks with markedly different degree distributions. Simulations on real networks further support this universality, indicating that the physics of network dismantling is insensitive to a broad range of topological properties. Together, these results suggest that a topology-agnostic theory could be developed to explain the critical behavior of network dismantling.

0.26

Performance Evaluation of Emerging Networks of Quantum Repeaters: Analysis and Simulation

cs.NI ·2026-10-02 ·Kobi Ravid, Javad Ghaderi, Gil Zussman
similarity 0.59
Abstract

Emerging experimental quantum network deployments are based on collaborations between research institutions and rely on telecommunications fiber infrastructure. Currently, such networks consist of mostly Dual Input Repeaters (DIRs) and can be viewed as composed of (mostly) line graphs. In order to evaluate the performance of such networks (e.g., in terms of Entangled Pair Rate, EPR, and average Fidelity) we developed a custom quantum network simulation platform that takes into account both the quantum and classical network components. To support the verification of the simulation results, we develop a novel approach for performance analysis of DIRs. We compare the simulation results to the analytical results for DIRs and to prior results for repeaters with more than two inputs. We observe that although the expected memory utilization cannot be bounded, \emph{a small DIR memory size is sufficient and leads to minimal performance degradation}. For line networks with a single repeater and $3$ repeaters, we explore the dependency of incoming and outgoing memory size requirements on the number of nodes (network size), their connectivity (fiber length) and various quantum error settings (amplitude damping and phase flip channels). We evaluate the \emph{EPR} and the \emph{average Fidelity} for a sub-network of a deployed network with $3$ repeaters, using two alternative paths. We show that as the number of nodes increases or when the fiber lengths between nodes differ significantly, additional node memory is needed to maintain the same EPR (qubits are stored for longer duration to allow completion of entanglement across the network). We also show that the memory size should be above some minimum threshold to allow EP creation (EPR $>0$) as pair selection and swapping completion propagate across the network.

0.34

Utility-Based Path Selection and Configuration in Quantum Networks via Layered Shortest Paths

cs.NI quant-ph ·2026-09-14 ·Leonardo Bacciottini, Subhransu Maji, Don Towsley, Gayane Vardoyan
theory similarity 0.58
Abstract · 13 pages

A path in a quantum network is a chain of repeaters that distributes entanglement between two users. Selecting a path requires balancing the rate and quality (e.g., fidelity) of the delivered entanglement, but these quantities, unlike standard routing metrics, compose non-additively. The problem is compounded by link-level configuration choices (e.g., distillation rounds or emitter brightness tuning), each trading rate against fidelity, so that a path's performance depends jointly on its route and its per-link settings. We cast this joint path selection and configuration problem as a shortest path computation on a layered graph whose layers track discretized end-to-end fidelity. A single run returns the full rate fidelity Pareto frontier, from which the path maximizing any nondecreasing utility function of rate and fidelity can be selected. We prove that for certain utility functions (including the secret key rate of BB84), the method is a fully polynomial time approximation scheme, returning a near-optimal path within a specified tolerance. We further characterize exactly when cheaper scalarization-based routing suffices: it is optimal for utility functions with convex fidelity profiles, but can be arbitrarily suboptimal otherwise (e.g., for step-like, sigmoidal utilities), whereas the layered method remains reliable in all cases.

0.23

Resetting-based designated information distribution

cs.DC cond-mat.stat-mechcs.SI ·2026-11-09 ·Xiaojuan Ma, Yan Wang, Indranil Gupta
published similarity 0.56
Abstract

For a network of $n$ nodes under random gossip dynamics, we show that by introducing the additional resetting mechanism (with rate $β$) to a designated subset of $r$ nodes, the expected sum of all node values is asymptotically equal to $\tfrac{n}{r}$ times the sum of the initial values of the $r$ designated nodes, in the small-$β$ and long-time limit. We also analyze the convergence speed to this asymptotic state and provide an approximate high-probability confidence interval for the expected sum at finite time $t$ and finite $β$. Operationally, we propose a protocol that distributes the initial node values over the designated subset evenly (up to a prescribed precision), by appropriately turning on and off the resetting dynamics. Our work not only offers insights into classical problems such as distributed computing and network control, but also serves as a potential foundation for designing quantum algorithms that prepare desired states in quantum networks using only local operations.

0.38

Multi-Pair Fidelity-Aware Rate Allocation in a Quantum Network: Approximation Schemes

cs.NI ·2026-08-11 ·Zunzheng Zhang, Xuanli Lin, Zhaofeng Zhang, Nageswara S. V. Rao, Guoliang Xue
theory similarity 0.56
Abstract

Entanglement distribution in quantum networks must jointly account for limited link capacities, probabilistic entanglement swapping, and heterogeneous link fidelities. In this paper, we study multi-pair fidelity-aware rate allocation in quantum networks. We formulate three rate-allocation problems: rate sum, rate sum subject to minimum-rate constraints, and max-min fairness. Prior work has studied a special case of the rate sum problem, where all links have identical fidelity. This special case admits a polynomial-time algorithm. We prove that all three problems are NP-hard. We then study optimization versions of these problems which maximize the minimum end-to-end fidelity subject to throughput or fairness requirements. We present fully polynomial-time approximation schemes (FPTAS) for solving these optimization problems. Experiments on randomly generated networks demonstrate the computational effectiveness of the proposed schemes.

0.04

Multiplicative Path Weights in Networks: From Katz Connectivity to Mean First-Passage Times

cs.SI math.PRphysics.soc-ph ·2026-10-15 ·Robbert van der Burg, Bernd Heidergott, Thao Le, Alessandro Zocca
similarity 0.56
Abstract

Signal dispersion, stress propagation in interbank systems, and transmission probabilities in epidemic and reliability models are all captured by studying paths on directed graphs where the path weight is defined as the product of its edge weights. Connectivity in such networks is naturally quantified by aggregating these multiplicative path weights across nodes. This paper provides a comprehensive treatise on connectivity and ranking measures based on multiplicative path weights. We demonstrate how standard all-path connectivity, such as the standard Katz centrality, can be extended beyond its classical spectral threshold. In addition, we derive closed-form expressions for connectivity based on first-hit paths and introduce a new version of Katz centrality. Furthermore, for random edge weights, we derive resolvent-based expressions for the first and second moments, alongside variance bounds, under a path-indexed coupling framework. Finite irreducible Markov chains are a subclass of the models studied, and we show that the scaled matrix of first-hit path probabilities is the probability-generating function for first-passage and return times, and that differentiation yields the classical first-passage times. Numerical examples illustrate the application of our results in a variety of settings.

0.23

On the Probability of Network States with Gaussian Connectivity Functions

eess.SP math.PR ·2026-08-18 ·Amy S. Inwood, Peter J. Smith, Pawel Dmochowski, Carl P. Dettmann, Justin P. Coon +1 more
published similarity 0.55
Abstract · Accepted to IEEE GLOBECOM 2026

In this paper, we consider the connectivity of a random network of N mobile devices in three dimensions (3D), where the location of each device or node has a Gaussian distribution in each dimension. For each pair of nodes, the probability of connectivity is related to the nodes' separation by a Gaussian connectivity function. The fundamental analytical tool for studying such systems is the probability of a given network state, derived and expressed in terms of its graph Laplacian. Leveraging this result, we obtain results for the connectivity of small networks, the probability of a complete network (where all nodes are connected to all other nodes), and the probability of an isolated node, which gives an approximation to the connectivity probability of larger networks. The general results are then simplified for special cases and limiting scenarios.

0.33

Resource competition and survival for random walkers on complex networks

cs.SI physics.comp-phstat.AP ·2026-10-24 ·Snehal Shekatkar
similarity 0.55
Abstract · 4 pages, 4 figures

We consider the problem of $W$ random walkers on a complex network where each walker requires an amount $θ$ of resource at each time to survive. Resource is stochastically produced at each vertex of the network with a specified distribution. The survival time of the system of walkers is defined as the time required for all $W$ walkers to die. Using numerical simulations, we show that Erd{\H o}s-Rényi networks a have higher mean survival time than Scale-free networks as expected, but also that uniform distribution production leads to higher mean survival time than exponential distribution with the same mean. We derive an exact expression for the survival-time distribution under the assumption of independent walker lifespans, and use it to show that scale-free network topology produces strong dependence in the lifespans but homogeneous topology does not. We moreover demonstrate how the survival time can be substantially increased without changing the resource production or network topology by appropriately biasing the movement of the walkers towards low degree vertices on Scale-free networks, but has no effect on Erd{\H o}s-R{é}nyi networks.

0.27