Source-linked AI summary
Effective routing design for remote entanglement generation on quantum networks
Changhao Li, Tianyi Li, Yi-Xiang Liu, Paola Cappellaro
TL;DR
The paper addresses efficient entanglement generation for simultaneous requests on quantum networks with limited capacity. It proposes a routing scheme combining multiple paths, purification, and three edge-capacity scheduling algorithms. Propagatory update has the highest throughput and capacity utilization across network conditions, while fairness and robustness differ among the schemes.
Problem
Limited quantum capacity makes efficient routing for simultaneous entanglement-generation requests between remote stations an open network-design problem.
Method
The paper develops a multi-request, multi-path, multi-channel routing scheme with entanglement purification and three algorithms for allocating finite edge capacity.
Results
Propagatory update stands out in system throughput and capacity utilization, while progressive filling is fairest and proportional share is least efficient but more robust against network failures.
Takeaways & Limitations
The routing scheme provides a solution for allocating limited resources in complex quantum networks that generate entangled pairs between remote station pairs.
Takeaways & Limitations
The approach assumes centralized global routing information, while large networks may face classical communication times exceeding quantum-memory lifetimes.
Abstract
from arXiv · showhide
Quantum network is a promising platform for many ground-breaking applications that lie beyond the capability of its classical counterparts. Efficient entanglement generation on quantum networks with relatively limited resources such as quantum memories is essential to fully realize the network's capabilities, the solution to which calls for delicate network design and is currently at the primitive stage. In this study we propose an effective routing scheme to enable automatic responses for multiple requests of entanglement generation between source-terminal stations on a quantum lattice network with finite edge capacities. Multiple connection paths are exploited for each connection request while entanglement fidelity is ensured for each path by performing entanglement purification. The routing scheme is highly modularized with a flexible nature, embedding quantum operations within the algorithmic workflow, whose performance is evaluated from multiple perspectives. In particular, three algorithms are proposed and compared for the scheduling of capacity allocation on the edges of quantum network. Embodying the ideas of proportional share and progressive filling that have been well-studied in classical routing problems, we design a new scheduling algorithm, the propagatory update method, which in certain aspects overrides the two algorithms based on classical heuristics in scheduling performances. The general solution scheme paves the road for effective design of efficient routing and flow control protocols on applicational quantum networks.
Introduction
Quantum networks support applications beyond classical data networks, but remote entanglement generation requires repeaters, purification, and routing under limited quantum capacity. This study develops a multi-request, multi-path, multi-channel routing scheme with centralized scheduling and virtual circuits.
- Quantum networks can support quantum communication, clock synchronization, and distributed quantum computing beyond classical data-network capabilities.
- Remote entanglement generation becomes harder with distance, while quantum repeaters use entanglement swapping to connect distant stations through intermediate nodes.Repeater operations involve local Bell-state measurements aided by classical communication.
- Entanglement purification increases pair fidelity but reduces the number of shared pairs available along network links.This tradeoff matters for applications requiring fidelity above a security-related threshold.
- Limited quantum memories make simultaneous entanglement-generation requests a critical routing-design problem.The network must respond to requests between desired stations despite constrained quantum capacity.
- The proposed scheme uses a central scheduler to select virtual-circuit paths and allocate edge capacity at each processing-window start.Routing results are broadcast to quantum stations, without requiring local processors on nodes or edges.
- The scheme supports multi-request, multi-path, and multi-channel entanglement generation while maintaining fidelity thresholds and allocating limited quantum resources.Multiple paths also spread flow, helping address potential network failures.
Network parameters and capabilities.
The routing problem is defined on lattice quantum networks whose purified, finite-capacity links support imperfect entanglement swapping and optical transmission. Requests seek minimum numbers of remote entangled pairs within each time window.
- Entanglement purification initializes each edge above a fidelity threshold but reduces its available edge capacity.The model allows identical pair fidelities along an edge and varying fidelities across edges.
- Each simultaneous request requires at least f̄_r entangled pairs between remote source and terminal nodes along a selected path.Remote pairs are generated through entanglement swapping during a processing time window.
- Imperfect local swapping and optical links make successful remote entanglement increasingly time-consuming as path length grows.The model represents local swapping and optical-link success with probabilities p_in and p_out.
- The routing problem concerns small-capacity regular lattice networks with topology that can vary during operation.
Routing Problem.
The routing problem is to allocate limited, imperfectly generated quantum capacity among multiple requests and paths while maintaining fidelity and feasible per-window operation. The proposed scheme combines physical entanglement operations with algorithmic path selection, capacity scheduling, and flow determination, evaluated through throughput, delay, and fairness measures.
- Problem formulation: The protocol addresses arbitrary entangled-pair requests under limited quantum memory, supporting multiple requests while maintaining above-threshold entanglement fidelity.Network capacity is reinitialized and realized through probabilistic entanglement generation and purification before routing.
- Problem formulation: For each request, multiple connection paths are identified and their allocated flows are aggregated to meet the request demand as closely as possible.This extends single-shortest-path routing by using path sets Lr and aggregate flow f^r = Σ_l∈Lr f^r,l.
- Routing construction: The stepwise scheme combines physical quantum operations with algorithmic planning, including network reinitialization, purification, path identification, capacity scheduling, and flow determination.A central scheduler computes and broadcasts routing decisions within each processing window, and requests are handled in batches.
- Routing construction: Edges with residual capacity below lmax are deactivated, while k shortest paths are selected on the revised graph to provide routing redundancy.The path count must be sufficient in principle to satisfy demand through k fmin ≥ f̄r.
- Capacity scheduling: Capacity scheduling compares proportional share, progressive filling, and propagatory update, with the last combining ideas from the first two methods.Proportional share uses local edge information, progressive filling targets max-min fairness, and PS and PU truncate edge path lists by length before allocation.
- Evaluation: Performance is assessed using weighted throughput, path-stretching delay, and request fairness alongside traffic-utilization measures.Progressive filling achieves Jreq ≈1 and guarantees max-min fairness among the three scheduling methods.
Baseline case.
In the baseline case, PU achieves the strongest throughput and edge-capacity use, while PS distributes routed traffic most evenly. As request distance increases, throughput and minimum flow decay exponentially, with PU remaining superior.
- PU obtains the largest throughput and best exploits edge capacities in the baseline comparison.Its scheduled path flows and edge capacity utilizations are generally highest among the three schemes.
- Throughput and the minimum flow of the two requests decay exponentially as request distance grows.
- PU produces obviously larger throughputs than PS and PF as request distance varies.The latter two algorithms remain comparable to each other.
Dependence on request distance and choice of k.
Request distance and the number of candidate shortest paths jointly shape throughput, utilization, path length, and fairness. Increasing k initially helps flow generation but eventually introduces congestion and less favorable path properties.
- Request distance: At large request distances, fixed-k traffic spreads across many paths, decreasing capacity utilization and yielding γ = 1 for shortest-path routing.
- Visualization: The figure compares traffic utilization across edges, with green, yellow, and red indicating utilization below 30%, from 30% to 70%, and above 70%.Larger edge width represents larger utilization; simulations use C0 = 100 and edge fidelities with mean Fmean = 0.8 and standard deviation Fstd = 0.1.
- Algorithm behavior: PU uses edge channels more effectively through information propagation during its iterative process, while PF balances requests and paths effectively.
- Choice of k: Increasing k lowers average capacity utilization, increases normalized path length, and reduces path fairness for PS and PU.
Effect of fidelity threshold.
Raising the fidelity threshold requires more purification, which reduces realized edge capacity and throughput while altering routing efficiency and fairness. Multi-path routing is intended to improve robustness to failures.
- Threshold effects: Higher fidelity thresholds require more purification steps, monotonously decreasing edge capacity and throughput.
- Threshold effects: At high fidelity thresholds, repeated purification removes edges, forcing broader exploration and reducing average capacity utilization.
- Threshold effects: High fidelity thresholds produce longer normalized paths and lower path fairness for PS and PU, while request fairness remains high across algorithms.
- Robustness: The multi-path design is intended to make routing more robust to potential network failures.
Potential network failures.
The routing scheme continues operating under increasing edge or node failures, though throughput declines. PS is the most robust of the three schemes, while PU's throughput advantage diminishes as failures become more severe.
- Evaluation dimensions: The performance study varies shortest-path count k and request distance while plotting throughput F, utilization Uave, path metric γ, and fairness measures.
- Failure robustness: Throughput decreases as edge or node failures become more serious, but the system continues producing output.After shutdown of 4 out of 16 utilized stations, some output remains.
- Failure robustness: PS shows the greatest robustness, slightly exceeding PF, whereas PU's throughput superiority gradually vanishes under network failures.
Number of requests per window.
As the number of requests per window increases, throughput rises while normalized throughput declines more slowly than inverse-proportionally, and propagatory update retains a throughput advantage. Fairness and traffic metrics worsen for propagatory update and progressive filling, while routing delay shows no consistent change.
- Number of requests per window: Throughput F increases with more requests, while normalized throughput F/|R| decreases less steeply than the inverse-proportional reference.The propagatory update method remains superior in throughput across the tested request counts.
- Number of requests per window: Traffic becomes more diluted and routing fairness decreases for propagatory update and progressive filling as requests increase.Uave, Uvar, Jreq, and Jpath fall quasi-linearly in the reported experiments.
- Number of requests per window: Average routing delay γ shows no consistent change with request count, and any apparent lower delay for propagatory update is not significant.
- Scheduling trade-offs: Progressive filling is the fairest scheduling method, while proportional methods have fairness that depends on α and β.
- Scheduling trade-offs: Propagatory update provides the strongest system throughput and capacity utilization, with its superiority largely maintained under network failures.The higher throughput is traded against less equitable allocation across requests and larger variance in edge utilization.
- Scope and limitations: The protocol is demonstrated on an 8 × 8 square lattice with edge capacity C0 = 102 and fewer than 10 requests per time window.The authors note that current laboratory quantum networks are much smaller and have edge capacities of only a few qubits.
Supplemental material for “Effective routing design for remote entanglement generation on quantum networks”
The supplemental material identifies the authors and their Massachusetts Institute of Technology affiliations, with equal contribution noted for the first two authors.
- Changhao Li, Tianyi Li, Yi-Xiang Liu, and Paola Cappellaro are listed as the paper’s authors.
- The authors are affiliated with MIT’s Research Laboratory of Electronics, Department of Nuclear Science and Engineering, and Sloan School of Management.
- Changhao Li and Tianyi Li contributed equally to the work.
1 Entanglement swapping and purification
This section reviews entanglement swapping and purification as mechanisms for generating long-distance entanglement and increasing fidelity, while trading away generation rate and pairs.
- Entanglement swapping: Quantum repeaters use local Bell-state measurements to connect entanglement across distant memories.The review describes memory-assisted repeaters and shows that measuring intermediate memories projects the outer memories into Bell states.
- Entanglement swapping: With quantum repeaters, remote-entanglement generation time scales polynomially with distance rather than exponentially.
- Entanglement purification: Purification combines two shared qubit pairs through local C-NOT gates and measurements to improve the fidelity of a retained pair.
- Entanglement purification: Initial fidelity above 0.5 enables purification toward highly entangled states.The purification curve has this threshold, as illustrated in Figure S2.
- Entanglement purification: Purification increases fidelity at the cost of entanglement generation rate and multiple entangled pairs.The protocol’s success probability is below one, so fresh pairs are consumed during distillation.
2 Capacity allocation scheduling
The routing protocol compares proportional share, progressive filling, and propagatory update for allocating finite edge capacity across requests and paths. The methods differ in whether they allocate capacity forward, fill paths uniformly, or propagate deductions backward to enforce path constraints.
- Scheduling methods: Three scheduling methods are compared: proportional share, progressive filling, and the newly introduced propagatory update.
- Proportional share: Proportional share allocates edge capacity first among requests and then among their paths using request weights, path counts, and path lengths.The exponents β and α control dependence on the number of paths and path length, respectively.
- Proportional share: Path allocations are lower-capped by fmin, and any resulting capacity overflow is iteratively subtracted from paths receiving the largest shares.
- Progressive filling: Progressive filling increases flow uniformly across unsaturated paths until capacity constraints saturate edges and remove affected paths from further increases.For integer capacities, each attempt increases every unsaturated path by one unit.
- Comparison: Unlike proportional share, which can leave capacity unused when bottleneck edges constrain a path, propagatory update addresses this mismatch during allocation.
- Propagatory update: Propagatory update integrates the short-board constraint during allocation by deducting excess desired flow from requests and then paths.It stores each path’s maximum flow, computes the edge excess over capacity, and updates path maxima throughout the process.
3 Discussion on scheme parameters
The discussion examines how lmax, α, and β affect routing performance. Increasing lmax initially improves flow and utilization before saturation, while α and β expose trade-offs between path and request fairness and throughput.
- lmax dependence: For fixed k, total flow F and average capacity utilization Uavg initially increase with lmax, then saturate at larger values such as lmax = 10.The saturation is attributed to edge removal balancing the gain from allowing more paths.
- α dependence: When paths spread across the network, larger α favors longer paths and increases Uavg, while path fairness Jpath is optimal at α = 0.When utilized paths have identical shortest lengths, performance does not depend on α.
- β dependence: For proportional share, β = 0 gives the best throughput and traffic metrics but degrades request fairness Jreq.Here β controls allocation’s dependence on the number of paths belonging to different requests.
4 Performance under network failures
This section presents performance measures before and after network failures, covering throughput, capacity utilization, variance, fairness, and γ. After failures, some paths become inaccessible, so some γ values are missing.
- The failure analysis compares performance measures before and after network failures, with white and red bars marking the two conditions.
- Parameter-sensitivity figures examine routing performance with respect to α and β under specified request distances and parameter settings.The α plots report total flow, average capacity utilization, and path fairness; the β plots report total flow, average capacity utilization, and request fairness.
- The reported measures include minimum flow over requests, average capacity utilization, and variance of capacity utilization.
- Request fairness and path fairness are evaluated separately under network failures.
- The robustness figures also report γ under network failures.