PaperlayerView exact revision on arXiv

Source-linked AI summary

Fidelity-Guarantee Entanglement Routing in Quantum Networks

Jian Li, Mingjun Wang, Qidong Jia, Kaiping Xue, Nenghai Yu, Qibin Sun, Jun Lu

arXiv:2111.07764v4quant-phcs.NI

TL;DR

Existing entanglement-routing mechanisms rarely account for fidelity, despite its importance for remote quantum connections. The paper introduces purification-enabled routing for single and multiple S-D pairs, combining optimal and low-complexity algorithms with greedy resource allocation. Simulations report fidelity-guaranteed solutions and improved throughput, end-to-end fidelity, and resource utilization over an existing purification-enabled scheme.

  • Problem

    Existing entanglement-routing designs mainly address robustness and throughput but rarely incorporate entanglement fidelity, a key quality metric for remote connections.

  • Method

    The paper develops purification-enabled routing with Q-PATH and Q-LEAP for single S-D pairs, then applies greedy resource allocation to multiple S-D pairs.

  • Results

    The proposed algorithms provide fidelity-guaranteed routing and outperform an existing purification-enabled scheme in throughput, average end-to-end fidelity, and resource utilization.

  • Takeaways & Limitations

    Q-PATH provides optimal performance with higher computational complexity, whereas Q-LEAP provides near-optimal performance with high efficiency for large-scale networks.

Abstract

from arXiv · show

Entanglement routing establishes remote entanglement connection between two arbitrary nodes, which is one of the most important functions in quantum networks. The existing routing mechanisms mainly improve the robustness and throughput facing the failure of entanglement generations, which, however, rarely include the considerations on the most important metric to evaluate the quality of connection, entanglement fidelity. To solve this problem, we propose purification-enabled entanglement routing designs to provide fidelity guarantee for multiple Source-Destination (SD) pairs in quantum networks. In our proposal, we first consider the single S-D pair scenario and design an iterative routing algorithm, Q-PATH, to find the optimal purification decisions along the routing path with minimum entangled pair cost. Further, a low-complexity routing algorithm using an extended Dijkstra algorithm, Q-LEAP, is designed to reduce the computational complexity by using a simple but effective purification decision method. Then we consider the common scenario with multiple S-D pairs and design a greedy-based algorithm considering resource allocation and rerouting process for multiple routing requests. To verify the effectiveness and superiority of the proposed algorithms, extensive simulations are conducted, and the simulation results show that the proposed algorithms not only can provide fidelity-guarantee routing solutions, but also has superior performance in terms of throughput, fidelity of end-to-end entanglement connection, and resource utilization ratio, compared with the existing routing scheme.

I. INTRODUCTION

The paper addresses fidelity degradation in entanglement routing by proposing purification-enabled designs that guarantee end-to-end fidelity for single and multiple Source-Destination pairs.

  • Motivation: Existing routing designs mainly target robustness and throughput, while rarely considering entanglement fidelity as the connection-quality metric.Noise can produce low-fidelity pairs, affecting quantum applications such as secure key distribution.
  • Contribution: The paper proposes fidelity-guaranteed entanglement routing and purification for S-D pairs in advance-generation quantum networks.The design combines routing decisions with purification under an end-to-end fidelity constraint.
  • Contribution: For single S-D pairs, Q-PATH finds optimal routing and purification decisions with minimum entangled-pair cost, while Q-LEAP offers lower-complexity routing with minimum fidelity degradation.Q-PATH can obtain multiple candidate paths; Q-LEAP is designed as an efficient alternative.
  • Contribution: For multiple S-D pairs, a greedy resource-allocation design uses resource consumption and degree of freedom to allocate entanglement resources across routing solutions.The goal is to improve network resource-utilization efficiency across requests.
  • Evaluation: Extensive simulations report fidelity-guaranteed solutions and superiority over an existing purification-aware routing scheme in throughput, average end-to-end fidelity, and resource utilization.The reported evaluation covers multiple performance dimensions rather than fidelity alone.

T EXT

The paper models a quantum network as capacity-limited connected quantum nodes and incorporates entanglement generation, purification, and swapping into fidelity-constrained routing.

  • Network model: A quantum network is represented as G = (V, E, C), where nodes are quantum devices, edges are quantum channels, and capacities bound available entangled pairs.The model uses edge capacity c(u, v) to represent the maximum entangled-pair supply.
  • Network model: Quantum nodes support entanglement and teleportation operations, while channels connect adjacent nodes and carry shared entangled pairs for qubit transmission.The model assumes first-generation repeaters with finite memories and no quantum error correction.
  • Entanglement operations: Entanglement purification combines two lower-fidelity Bell pairs into one higher-fidelity pair and can be recursively applied across multiple rounds.Under pumping purification, each round consumes an additional entangled pair; purification is therefore a fidelity-resource trade-off.
  • Entanglement operations: Entanglement swapping extends one-hop entanglements across repeater paths, but imperfect repeater measurements degrade multi-hop fidelity.This degradation motivates imposing an end-to-end fidelity constraint during routing.
  • Problem formulation: The routing problem selects paths and purification decisions so each S-D connection satisfies F_i,j(s, d) > F_th_i under network capacities.For multiple S-D pairs, the problem is additionally difficult because it belongs to the NP-hard multi-commodity-flow class.

IV. ROUTING DESIGN FOR SINGLE S-D PAIR

For a single S-D pair, the paper designs Q-PATH for optimal minimum-cost fidelity-guaranteed routing and Q-LEAP as a lower-complexity near-optimal alternative.

  • Q-PATH: Q-PATH is an iterative algorithm that jointly selects a routing path and purification decisions to minimize entangled-pair cost under the fidelity constraint.Its procedure includes path selection, fidelity-based purification decisions, edge-cost updates, and throughput updates.
  • Q-LEAP: Q-LEAP is introduced as a low-complexity heuristic using a multiplicative fidelity-degradation metric to find a near-optimal, efficiently computable routing solution.It selects a best-quality path and uses a simple but effective purification decision method.
  • Design rationale: The single-S-D design targets an optimal solution with Q-PATH while reducing computational burden through Q-LEAP.The paper positions Q-PATH as the optimal reference and Q-LEAP as the efficient alternative.
  • Q-PATH: Q-PATH first removes edges unable to meet the fidelity threshold, finds shortest paths, and evaluates multiple shortest-path candidates before updating costs and throughput.The supplied algorithm fragments explicitly include edge filtering, BFS path search, candidate-path construction, and iterative updates.
  • Q-PATH: Q-PATH outputs the selected path and purification decisions after iteratively enforcing the end-to-end fidelity requirement.The algorithm output includes P_i,j(s_i, d_i) and D^pur_i,j.

B. Iterative Routing Design for Single S-D Pair

Q-PATH searches routing paths and purification decisions iteratively to satisfy an end-to-end fidelity constraint at minimum entangled-pair cost. Its purification decisions exploit fidelity-improvement monotonicity, while throughput accounts for both path establishment and purification consumption.

  • Q-PATH design: Q-PATH searches solutions from the lowest entangled-pair cost and iteratively updates purification decisions until a fidelity-guaranteed route is found.The algorithm considers routing paths together with purification allocations rather than minimizing hops alone.
  • Path search: Q-PATH removes edges unable to meet the fidelity threshold after purification, then uses BFS and k-shortest paths to search feasible routes by cost.The initialization constructs an update graph and records purification decisions during iterative path selection.
  • Cost and throughput: Purification adds entangled-pair consumption to the basic path cost, and throughput is calculated from both path establishment and extra purification operations.The algorithm outputs the selected path, purification decision, expected fidelity, and achievable throughput when the request is satisfied.
  • Purification cost modeling: The purification cost table records each edge’s resource consumption and the minimum and maximum fidelity achievable after successive purification rounds.For an edge with original fidelity 0.75, the first two rounds yield fidelities 0.9 and 0.9642.
  • Purification decisions: Purification improvement decreases with additional rounds, enabling a greedy decision that is optimal under the stated fidelity condition.Theorem 1 states that the greedy approach finds the minimum-cost purification decision when original fidelity is above x*.
  • Limitation: The greedy purification procedure requires sufficient entangled pairs on the edges; otherwise Q-PATH may find no effective solution.

T EXT

The supplied passage contains only a fragment of notation associated with the section’s displayed content.

  • T EXT: The passage identifies notation involving an edge and a purification-round quantity.
  • T EXT: The supplied notation is associated with an end-to-end routing calculation.
  • T EXT: No complete operational definition is available in the supplied passage.

C. Discussion and Complexity Analysis of Q-PATH

Q-PATH is theoretically presented as an optimal fidelity-guaranteed routing algorithm, but its complexity can grow rapidly with network size and edge capacity. This motivates a lower-complexity alternative based on extended Dijkstra search.

  • Iterative example: In a routing example, Q-PATH iteratively raises route cost when a candidate path requires purification to satisfy the fidelity constraint.A two-hop candidate with min cost 2 is enqueued with cost 3 after purification is required on one edge.
  • Optimality: Theorem 2 states that Q-PATH finds a fidelity-guaranteed routing path with minimum entangled-pair cost for any S-D pair.
  • Complexity analysis: Q-PATH’s complexity includes purification-table construction, k-shortest-path search, purification decisions, and throughput updates across candidate paths.The stated terms include O(|E|Cmax), O(K|V|(|E|+|V| log2 |V|)), O(K|E|Cmax), and a throughput-update term proportional to Ri|E|.
  • Motivation for Q-LEAP: Because complexity rises quickly with the number of edges and edge capacity, the paper introduces Q-LEAP as a low-complexity alternative.

D. Low-complexity routing design for single S-D pair

Q-LEAP reduces the search burden by selecting a best-quality path with an extended Dijkstra algorithm and using average fidelity for purification decisions. The purification step has worst-case complexity O(|E|).

  • Best-quality path search: Q-LEAP searches for the path with minimum fidelity degradation using an extended Dijkstra algorithm and a monotonic non-additive routing metric.Unlike classical additive shortest-path routing, the metric reflects multiplicative fidelity degradation.
  • Purification decision: Q-LEAP uses average fidelity to make lower-complexity purification decisions while enforcing the end-to-end fidelity threshold.For a path of length l, each hop is required to satisfy the corresponding average-fidelity condition.
  • Complexity: The worst-case complexity of Q-LEAP’s purification-decision step is reduced to O(|E|).

E. Discussion and Complexity Analysis of Q-LEAP

The multiple-S-D-pair problem is formulated as fidelity-constrained resource allocation, using single-pair routing solutions and rerouting when residual resources invalidate paths. The greedy design allocates routing solutions iteratively while considering resource availability and allocation order.

  • Problem Definition: Multiple-S-D-pair routing seeks paths and purification decisions satisfying each pair’s end-to-end fidelity constraint under network-capacity limits.The problem is defined over topology G = (V, E, C), with routing paths and purification decisions for each request.
  • Design Overview: The greedy algorithm builds single-pair solutions with Q-PATH or Q-LEAP, then allocates their resources sequentially through a priority queue.Algorithm 3 includes path predetermination, resource allocation, and rerouting stages.
  • Re-routing Process: When a selected path exhausts residual edge resources, the algorithm reroutes that S-D pair on the residual graph and re-enqueues the new solution.Invalidated paths trigger a rerouting process before the allocation loop continues.
  • Resource Allocation: Allocation order materially affects throughput: allocating P1,1 first can exhaust shared edge (r1, r2), forcing the second request to be denied.The example uses two paths sharing an edge and shows the consequence of an unfavorable allocation order.

C. Resource Allocation

The resource-allocation utility ranks routing solutions using resource consumption and degree of freedom. These factors favor solutions that conserve scarce entangled pairs and preserve rerouting options for other requests.

  • Utility Metric: The utility metric combines resource consumption and degree of freedom to evaluate how difficult each routing solution is to allocate.α and β weight the total resource consumption S(·) and degree of freedom G(·).
  • Degree of Freedom: Degree of freedom counts routing options across hops and represents the possibility of successful rerouting.The paper’s example assigns G(P1,1) = 10 and G(P2,1) = 9, illustrating how allocation order can preserve alternatives.
  • Resource Consumption: Lower resource consumption should be allocated earlier because high-consumption paths can exhaust edge capacity and deny other S-D requests.The example states that ordering by S(·) can achieve maximum throughput.

D. Computational Complexity Analysis

The paper analyzes computational complexity for multi-request routing and evaluates the proposed algorithms through numerical simulations on generated quantum-network topologies. The experiments compare routing performance across fidelity and channel-capacity settings.

  • Complexity Analysis: Algorithm 3 has complexity driven by S-D-pair path selection, at most K candidate paths, and rerouting performed up to Ri times.The allocation stage contributes O(K|E|), while rerouting can execute up to Pi Ri times.
  • Evaluation Setup: The evaluation uses numerical simulations on a platform with an AMD Ryzen 7 3700X CPU, 32GB RAM, and Windows 10 64-bit.The simulation code is reported as available in reference.
  • Evaluation Setup: Random network topologies are generated using the Waxman model, with edge probability based on node distance and the network’s maximum pairwise distance.The generated topologies are used in Table III.
  • Evaluation Setup: Figures 6 and 7 compare single-S-D-pair throughput, average fidelity, and network resource utilization under channel-capacity and fidelity-threshold settings.Figure 6 fixes channel capacity at 50, while Figure 7 fixes the fidelity threshold at 0.7.

B. Results under Single S-D Pair Scenarios

In single-pair settings, Q-PATH provides the strongest routing performance and minimum-cost fidelity guarantees, while Q-LEAP trades some performance for much lower complexity. Across multi-pair extensions, the proposed methods improve throughput and resource use over the baseline while maintaining fidelity constraints.

  • Single S-D Pair Results: Q-PATH achieves the highest throughput, while Q-LEAP runs 50x lower than the baseline complexity as network scale increases.Q-PATH’s running time is 5x–10x higher than the baseline, whereas Q-LEAP is 50x lower.
  • Single S-D Pair Results: Q-PATH produces end-to-end fidelity just above the threshold with minimum entangled-pair cost, while Q-LEAP generally uses similar resources with near-optimal performance.Q-PATH has lower resource utilization than Q-LEAP in the fidelity-threshold comparison, despite higher throughput.
  • Multiple S-D Pair Results: As fidelity thresholds increase, Algorithm 3-PATH maintains the highest throughput and minimum above-threshold fidelity, whereas Algorithm 3-LEAP obtains the highest fidelity.The baseline’s resource utilization drops substantially when the fidelity threshold exceeds 0.8.
  • Multiple S-D Pair Results: As channel capacity increases, Algorithm 3-PATH remains highest-throughput and its advantage over Algorithm 3-LEAP ranges from 11.4% to 6.5%.Algorithm 3-PATH also attains the lowest above-threshold fidelity and resource consumption, indicating minimum entangled-pair cost.
  • Multiple S-D Pair Results: For multiple S-D pairs, Algorithm 3-PATH improves throughput over Algorithm 3-LEAP by 12.3%–10.2% and over the baseline by 510.7%–353.2%.Throughput rises with the number of S-D pairs, while fidelity remains relatively stable under the fixed threshold setting.
  • Overall Results: The proposed designs provide fidelity-guaranteed routing, with Q-PATH optimal but computationally expensive and Q-LEAP near-optimal and efficient for larger networks.The greedy multi-pair design allocates resources using degree of freedom and resource consumption metrics.

APPENDIX A PROOF OF THEOREM 1

The proof shows that purifying the lowest-fidelity entangled pair is optimal when its fidelity lies above the threshold x∗≈0.743. Repeated-round reasoning extends this greedy choice to minimum-cost purification decisions.

  • Theorem 1 Proof: For one-round purification, the largest fidelity improvement occurs when the original fidelity is x∗≈0.743.The derivative analysis establishes increasing concavity over the relevant fidelity interval and identifies the maximizing point.
  • Theorem 1 Proof: When edge fidelities exceed x∗, purifying the entangled pair with the lowest fidelity yields the highest improvement.The proof assumes x∗ < F_i,j(s_i,d_i) < F_th and compares purification gains across edges.
  • Theorem 1 Proof: The greedy purification decision is optimal for one purification operation because it minimizes the required entangled-pair cost.The argument identifies the minimum-fidelity edge as the edge receiving purification when N∗=1.
  • Theorem 1 Proof: For N∗=2 and higher, the proof recursively reduces later rounds to the one-operation case, extending optimality to multiple purification rounds.After the first operation, the remaining situation is treated in the same manner as N∗=1.

APPENDIX B PROOF OF THEOREM 2

Theorem 2 proves that Q-PATH finds a fidelity-feasible routing path with minimum entangled-pair cost by searching candidate paths in increasing cost order. The induction rules out any cheaper feasible path being missed earlier.

  • Theorem 2 Proof: Q-PATH begins with the minimum-hop path found by BFS, establishing that any feasible optimal cost is at least Hmin.The first iteration searches shortest paths with Hmin hops and checks the fidelity constraint.
  • Theorem 2 Proof: If a feasible path of cost Hmin exists, the algorithm must find it in the first iteration; otherwise, a shorter-than-minimum-hop path would be required.This contradiction establishes the base case for the induction.
  • Theorem 2 Proof: At iteration k, Q-PATH searches paths with minimum cost Hmin+k and cannot miss a cheaper feasible path stored outside the priority queue.The proof compares the assumed optimal path with the path selected by the algorithm and derives a contradiction.
  • Theorem 2 Proof: Applying the same contradiction through successive iterations proves that Q-PATH returns a fidelity-feasible path with globally minimum entangled-pair cost.The induction concludes after excluding any feasible path with cost below the selected path’s cost.
Loading 2111.07764v4…