New Routing Algorithms Tackle Bursty Traffic in Quantum Networks

Quantum networks promise a future in which distant quantum processors share entangled states as easily as today’s computers exchange data packets. But the traffic patterns of such networks may look nothing like the steady streams of classical communication. Many anticipated applications—from distributed quantum computing to secure multi-party protocols—will demand bundles of entangled pairs delivered in sudden, concentrated bursts, all within narrow windows of time before fragile quantum memories decay. A new study from researchers at the Indian Institute of Technology Hyderabad addresses precisely this challenge, offering a suite of routing algorithms designed for what the authors call bursty demands in quantum networks.

The work, published in the journal Quantum Information Processing by Anoop Kumar Pandey, Anubhav Srivastava, Pranav K. Nayak, Bheemarjuna Reddy Tamma, and M. V. Panduranga Rao, all of the Department of Computer Science and Engineering at IIT Hyderabad, formalizes a version of the quantum routing problem in which each request specifies not only how many entangled qubit pairs are needed between two nodes, but also a start time and an end time within which all of those pairs must be delivered. The constraint is not an arbitrary complication. Quantum memories at network nodes can store quantum information only for limited durations, so a request for, say, ten shared EPR pairs between two nodes is meaningful only if all ten arrive before the earliest delivered pairs begin to degrade. Applications that need several shared EPR pairs at once therefore impose hard timing constraints on the network, and the routing algorithms that serve them must respect those constraints explicitly.

At its core, quantum network routing is about finding paths along which entanglement can be extended between distant nodes. Neighboring nodes that share an entangled pair can perform a procedure known as entanglement swapping, which stitches together short-range entangled links into a long-range one. Chained across a path of repeater nodes, swapping allows two far-apart quantum processors to end up sharing EPR pairs, the fundamental resource underlying quantum teleportation and many other protocols. The new paper treats the network as a graph, with nodes representing quantum devices and edges representing links capable of generating entanglement, and asks how to allocate the network’s limited entanglement-generation resources across many simultaneous, time-constrained requests.

The researchers begin with a deliberately simple variant of the problem, and even this stripped-down version turns out to be computationally intractable in the formal sense: it is NP-hard, meaning that no known algorithm can solve all instances efficiently as the network grows. This matters for practitioners because it rules out the hope of a single fast, exact method that always finds the optimal routing plan. Instead, the field must rely on a combination of exact formulations for small instances and clever heuristics for large ones. The IIT Hyderabad team does both. They formulate the simple variant as an integer linear program, a mathematical optimization model in which the routing decisions are encoded as integer variables subject to linear constraints, and they solve it with the commercial CPLEX solver to obtain optimal or near-optimal benchmarks.

Exact optimization, however, does not scale. Integer linear programs of the multicommodity-flow type, which this problem closely resembles, can take prohibitive amounts of time on realistic networks with many requests. So the authors design a fast greedy heuristic algorithm for the same problem. Greedy algorithms work by making the locally best choice at each step—in this case, deciding which request to serve next and along which path—without attempting to look ahead at the global consequences. The trade-off is familiar from classical networking: greedy methods sacrifice the guarantee of optimality in exchange for dramatic speedups. What makes this study notable is the empirical observation that the greedy heuristic’s solutions appear to mimic those of the ILP formulation closely, delivering solution quality comparable to the exact optimizer while running in a fraction of the time.

Encouraged by that result, the team generalized their greedy heuristic into a flexible framework that can be adapted to yield different heuristics for different objective functions. This is the conceptual heart of the paper. Rather than designing a bespoke algorithm for every variation of the bursty routing problem, the authors provide a single template in which the key decision—how to rank and select requests and paths—can be swapped out to optimize different goals. A crucial feature of the framework is that it splits the demand for EPR pairs in two dimensions: spatially, by dividing a request’s required pairs across multiple paths through the network, and temporally, by spreading delivery across the time window allowed by the request. This splitting ability is what allows the framework to juggle many competing requests without starving any of them entirely.

From this framework, the researchers derive several concrete heuristics targeting different variants of the problem. One variant addresses starvation avoidance, ensuring that no request is left unserved simply because greedier neighbors monopolized the network’s resources. Another aims to minimize the number of spatial splits, the situations in which a single request’s entangled pairs must be routed along several different paths. Spatial splits are not free: coordinating entanglement across multiple paths adds overhead and complexity at the requesting nodes, so a routing plan that keeps each request’s traffic on fewer paths can be preferable even if it is not optimal in raw throughput. By tuning the framework’s selection rules, the authors produce heuristics that trade these objectives against one another, and they compare the performance of the resulting algorithms empirically across different scenarios.

The motivation for worrying about burstiness draws on a long line of research into classical internet traffic. Studies of real-world networks have shown that traffic is inherently bursty at short time scales, with demand arriving in concentrated clumps rather than smooth flows. Quantum networks are expected to inherit this character, and possibly amplify it, because many quantum applications are inherently batch-oriented: a distributed computation may need a fixed number of entangled pairs delivered together before it can proceed at all. Earlier work on quantum routing has explored concurrent entanglement routing, fidelity-guaranteed routing, multicommodity flow formulations, and time-scheduled entanglement establishment, but the specific combination of hard delivery windows and multi-pair demands addressed in the new paper fills a gap in that landscape.

The practical significance of the work lies in the gap between what exact methods can prove and what operational networks will need. A quantum network controller in a real deployment will face a continuous stream of requests with deadlines and must make routing decisions in real time, on hardware where quantum memories are ticking down toward decoherence. An integer program that takes minutes or hours to solve is useless in that setting, no matter how optimal its answer. A greedy framework that runs quickly, adapts to different objectives, and empirically tracks the quality of exact solutions offers a plausible foundation for such controllers. The fact that the framework is modular means network operators could tune it as hardware improves—as memories get longer-lived, the timing constraints loosen, and different objective functions may become dominant.

The researchers have released the source code supporting their findings in a public GitHub repository, allowing other teams to reproduce their experiments and build on the framework. The authors state that all contributed equally to the conception, development, analysis, and preparation of the manuscript, and the research received no specific grant from any funding agency. As quantum network testbeds mature and distributed quantum computing demonstrations move from single links to multi-node networks, the scheduling and routing layer will increasingly determine what these systems can do. This study’s contribution—a rigorous demonstration that even simple bursty routing is NP-hard, an exact benchmark formulation, and a fast, adaptable family of heuristics that split demands across paths and time—gives the emerging quantum internet a more complete algorithmic toolkit for the lumpy, deadline-driven traffic it will actually face.

Subject of Research: Routing algorithms for time-constrained bursty entanglement distribution in quantum networks

Article Title: A suite of routing algorithms for bursty demands in quantum networks

Article References: Pandey, A. K., Srivastava, A., Nayak, P. K., Tamma, B. R., & Rao, M. V. P. (2026). A suite of routing algorithms for bursty demands in quantum networks. Quantum Information Processing, 25(10), Article 340. https://doi.org/10.1007/s11128-026-05355-2

Image Credits: AI Generated

DOI: 10.1007/s11128-026-05355-2

Keywords: quantum networks, entanglement swapping, routing algorithms, bursty demands, NP-hard, integer linear programming, greedy heuristics, quantum repeaters, EPR pairs, distributed quantum computing, optimization, quantum memory