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

Multi-Pair Fidelity-Aware Rate Allocation in a Quantum Network: Approximation Schemes Zunzheng Zhang, Xuanli Lin, Zhaofeng Zhang, Nageswara S. V. Rao, Guoliang Xue Abstract

arXiv:2608.11501v1 [cs.NI] 11 Aug 2026

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. Index Terms Quantum networks, throughput, fairness, rate allocation, approximation schemes

1. I NTRODUCTION Quantum networks enable the distribution of entanglement between remote quantum nodes, which is a fundamental resource for quantum communication, distributed quantum computation, clock synchronization, and other quantum information processing tasks [14], [24], [25]. In such networks, intermediate quantum repeaters extend entanglement over long distances by generating elementary EPR pairs over physical links and performing entanglement swapping operations [2]. A central objective in quantum network routing is to allocate limited entanglement generation resources among multiple source-destination pairs. Unlike classical multicommodity flow routing, both throughput and fidelity depend on the selected paths: probabilistic entanglement swapping reduces the achievable end-to-end rate as the number of swaps increases [3], while the Werner-state model imposes end-to-end fidelity constraints that restrict the set of feasible routes. Together with limited link capacities and multiple simultaneous requests, these features make fidelity-constrained quantum network routing a challenging optimization problem. Different applications may favor different rate-allocation objectives for multiple source-destination pairs. Considering total throughput promotes network utilization but may leave some pairs with little or no service. Adding per-pair minimum-rate constraints provides baseline service guarantees, whereas max-min fairness gives stronger protection to the least-served pairs. 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 [5] has studied a special case of the rate sum problem. This special case admits a polynomial-time algorithm. However, the polynomial-time algorithm in [5] heavily depends on the assumption that all links in the network Zunzheng Zhang, Xuanli Lin, and Guoliang Xue are affiliated with Arizona State University, Tempe, Arizona, USA. Emails: {zzhan621, xlin54, xue}@asu.edu. Zhaofeng Zhang is affiliated with Delaware State University, Dover, Delaware, USA. Email: zzhang@desu.edu. Nageswara S. V. Rao is affiliated with Oak Ridge National Laboratory, Oak Ridge, Tennessee, USA. Email: raons@ornl.gov. This research is sponsored in part by PiQSci project of Advanced Scientific Computing Research program, U.S. Department of Energy, and is performed at Oak Ridge National Laboratory managed by UT-Battelle, LLC for U.S. Department of Energy under Contract No. DE-AC05-00OR22725. This manuscript has been co-authored by UT-Battelle, LLC, under contract DE-AC05-00OR22725 with the US Department of Energy (DOE). The US government retains and the publisher, by accepting the article for publication, acknowledges that the US government retains a nonexclusive, paid-up, irrevocable, worldwide license to publish or reproduce the published form of this manuscript, or allow others to do so, for US government purposes. DOE will provide public access to these results of federally sponsored research in accordance with the DOE Public Access Plan (http://energy.gov/downloads/doe-public-access-plan).

1

have identical fidelity. 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. By transforming the multiplicative Werner parameter into an additive loss metric and building on scaling techniques for multi-constrained routing [18], [19], we develop fully polynomial-time approximation schemes (FPTAS) for solving these optimization problems. Our main contributions are summarized as follows: • We formulate multi-pair fidelity-aware rate allocation in quantum networks and define three problems: rate sum, rate sum subject to minimum-rate constraints, and max-min fairness. • We prove that all three problems are NP-hard, even for the single-pair case. • We then study optimization versions of these problems, and design FPTAS for all these optimization problems. • We provide evaluation results to validate the effectiveness of our schemes. The rest of this paper is organized as follows. §2 reviews related work. §3 presents the network model and formally defines the decision problems. §4 defines the optimization versions of these decision problems. §5 develops an exact formulation for the integer version of the rate sum problem. §6 proposes the scaling-based FPTAS for the rate sum problem. §7 proposes the scaling-based FPTAS for the rate sum problem subject to minimum-rate constraints. §8 proposes the scaling-based FPTAS for the max-min fairness problem. §9 presents the performance evaluation. Finally, §10 concludes the paper. 2. R ELATED W ORK Entanglement routing has been studied extensively [1]. Existing studies can be broadly classified into throughputoriented routing, fidelity-aware routing and purification, flow-based resource allocation, and fairness-aware allocation. Some studies focus on routing and resource allocation for a single source-destination pair, including entanglementrate analysis, fidelity-rate optimization, and generalized-flow maximization [4], [10], [26]. Other studies consider multiple concurrent connection requests. Pant et al. [21] show that multipath routing can improve entanglementdistribution rates. Shi and Qian [23] propose Q-CAST for concurrent entanglement routing over probabilistic links with path recovery, while Zeng et al. [33] consider both the number of users and the resulting throughput. Gu et al. [11] study entanglement scheduling for multiple source-destination pairs. Fidelity-aware routing and resource allocation have also been studied through flow-based models and purificationenabled routing schemes. Zhao et al. [36] jointly optimize routing and purification to maximize the number of connections that meet a prescribed fidelity threshold. Zhang et al. [34] study link configuration for fidelityconstrained entanglement routing. Li et al. [17] develop purification-enabled, fidelity-guaranteed routing algorithms together with a greedy multi-pair allocation scheme. Gu et al. [9] develop an approximation scheme for cost-aware entanglement distribution with purification. Flow-based formulations are also considered in [5], [6], [35]. Among these studies, the work of Chakraborty et al. [5] is the most closely related to our rate sum formulation. They formulate entanglement distribution as a multicommodity-flow optimization problem and provide a polynomial-time solution under the assumption that all physical links have identical fidelity. In contrast, we allow heterogeneous link fidelities and show that the resulting problem is NP-hard even for a single source-destination pair. Fairness in entanglement routing has also received attention. Li et al. [16] study fidelity-constrained routing together with fair link-level capacity allocation. They also state that a related multicommodity-flow routing problem is NP-hard, but do not provide a formal proof. Wang et al. [27] address max-min fairness through offline predictive allocation and online resource adjustment, but do not impose fidelity constraints. Our approximation schemes build on classical constrained-routing techniques [22], [28]. Lorenz and Raz [18] develop an approximation scheme for the restricted shortest-path problem, while Xue et al. [30] and Misra et al. [19] study polynomial-time approximation algorithms for multi-constrained and multi-path routing. Max-min

2

fairness has been studied extensively in classical networks [12], [15], [20], and we adapt these ideas to quantum networks. 3. S YSTEM M ODEL AND P ROBLEM D EFINITIONS In this section, we present the quantum network model and define the multi-pair fidelity-aware rate allocation problems. A. Quantum Network Model We model a quantum network as a directed graph G = (V, E, c, w, q), where V is the set of n quantum nodes, including end nodes and quantum repeaters, and E is the set of m directed edges. Each edge represents a physical quantum communication link (or a direction of a physical link). We assume that the underlying undirected graph of G is connected. For an edge e = (u, v) ∈ E , c(e) denotes the maximum elementary EPR-pair generation rate over the corresponding link [5], and the Werner parameter of e is denoted by w(e) = w(u, v) ∈ (0, 1]. We also assume that swapping operations are independent and each succeeds with the same probability q ∈ (0, 1]. A path from a source node s to a destination node t is denoted by s→u1 →u2 →· · · →u|π|−1 →t, where |π| is the number of edges on the path. In Fig. 1, we illustrate four paths π1 : a → c, π2 : a → u → v → c, π3 : b → u → v → d, and π4 : b → d.

(3, 0.7)

(16

,0

(16

.95 )

,0

) ,1

(16, 1)

.9)

(16

(16 , 1)

(3, 0.7)

Fig. 1: Graph G = (V, E, c, w, q). The 2-tuple label next to directed edge (u, v) denotes (c(u, v), w(u, v)). We assume q = 0.5 for every swapping operation. Under the Werner-state model [3], [29], the end-to-end Werner parameter of a path π is the product of the Werner parameters of the edges on the path: Y W (π) = w(e). (3.1) e∈π

Therefore, the end-to-end fidelity of an EPR pair distributed along path π is 1 3Y F (π) = + w(e). 4 4 e∈π

(3.2)

For each edge e ∈ E , we define its fidelity-loss value as ℓ(e) = − ln w(e).

(3.3)

The fidelity-loss representation is introduced mainly for algorithmic purposes: it transforms the multiplicative Werner-parameter constraint into an equivalent additive path constraint. For a path π , define X ℓ(π) = ℓ(e). (3.4) e∈π

3

Using Fig. 1 as an example again, we have W (π1 ) = 0.7, W (π2 ) = 0.95 × 1 × 1 = 0.95. Therefore F (π1 ) = (3 × 0.7 + 1)/4 = 0.775, F (π2 ) = (3 × 0.95 + 1)/4 = 0.9625; ℓ(π1 ) = − ln 0.7, ℓ(π2 ) = − ln 0.95. B. Connection Demands and Rate Allocation We consider a set of K source-destination demands, also referred to as connection requests or commodities, denoted by D = {(s1 , t1 ), (s2 , t2 ), . . . , (sK , tK )}, where sk , tk ∈ V are the source and destination nodes for commodity k . We assume that sk ̸= tk . In this paper, we will use the notation [K] ≜ {1, 2, . . . , K}. For each demand k ∈ [K], we need to find a rate allocation Pk = {(πk,1 , rk,1 ), (πk,2 , rk,2 ), . . . , (πk,|Pk | , rk,|Pk | )}, where πk,i is a simple sk -tk path and rk,i ≥ 0 is the delivered rate along πk,i , i = 1, 2, . . . , |Pk |. We denote P = (P1 , P2 , . . . , PK ). Note that it suffices to consider only simple paths. If an sk -tk walk contains a cycle, removing the cycle cannot increase its fidelity loss. Moreover, since q ≤ 1, removing the cycle reduces the number of swapping operations and therefore cannot increase the elementary-pair generation rate required to support the same delivered rate. Hence, any feasible allocation can be transformed into one using only simple paths. By allowing Pk = ∅, we can restrict every path to have a positive rate, rather than a non-negative rate. However, for ease of formulation of the optimization problems, we allow paths with zero rate. We say P satisfies the link-capacity constraints if K X

X

k=1 1≤i≤|Pk | e∈πk,i

rk,i ≤ c(e), |π q k,i |−1

∀e ∈ E.

(3.5)

The quantity rk,i /q |πk,i |−1 in (3.5) represents the elementary-pair generation rate required on each edge of path πk,i to achieve a delivered end-to-end rate rk,i . The quantity q |πk,i |−1 in (3.5) arises from the probabilistic nature of entanglement swapping. Since each swapping operation succeeds with probability q , delivering rate rπ along a path with |πk,i | − 1 swapping operations requires rπ /q |πk,i |−1 elementary-pair generation rate on each edge of the path. Constraint (3.5) guarantees that for each edge, the aggregated elementary-pair generation rate does not exceed its capacity. We will simplify (πk,i , rk,i ) ∈ Pk as (π, rπ ) ∈ Pk if the exact meaning is clear from the context. In Fig. 1, we consider a demand set D = {(s1 , t1 ), (s2 , t2 )} where s1 = a, t1 = c, s2 = b, t2 = d. For illustration, consider a possible rate allocation P = (P1 , P2 ), where P1 = {(π1 , rπ1 ), (π2 , rπ2 )} and P2 = {(π3 , rπ3 ), (π4 , rπ4 )}. By (3.5), the link-capacity constraints become: rπ1 ≤ 3, rπ2 ≤ 16, 0.52 rπ3 ≤ 16, 0.52 rπ2 rπ + 32 ≤ 16, 2 0.5 0.5 rπ2 ≤ 16, 0.52 rπ3 ≤ 16, 0.52 rπ4 ≤ 3,

capacity constraint on edge (a, c),

(3.6a)

capacity constraint on edge (a, u),

(3.6b)

capacity constraint on edge (b, u),

(3.6c)

capacity constraint on edge (u, v),

(3.6d)

capacity constraint on edge (v, c),

(3.6e)

capacity constraint on edge (v, d),

(3.6f)

capacity constraint on edge (b, d).

(3.6g)

If we choose P1 = {(π1 , 3), (π2 , 2)} and P2 = {(π3 , 1), (π4 , 3)}, then P satisfies all link-capacity constraints in (3.5). If we choose P1 = {(π1 , 3), (π2 , 4)} and P2 = {(π3 , 2), (π4 , 3)}, then P does not satisfy the link-capacity constraints in (3.5), because the capacity constraint on edge (u, v) is violated. For any k ∈ [K], we define the throughput of commodity k as X Rk (P) = rπ . (3.7) (π,rπ )∈Pk

4

We call R(P) = (R1 (P), R2 (P), . . . , RK (P)) the throughput vector of a rate allocation P . For ease of reading, we will use Rk (R, respectively) to denote Rk (P) (R(P), respectively) when the exact meaning can be obtained from the context without ambiguity. In Fig. 1, if we choose P1 = {(π1 , 3), (π2 , 2)} and P2 = {(π3 , 1), (π4 , 3)}, then R1 = 5, R2 = 4. In the rest of this paper, we only concentrate on P that satisfies the link-capacity constraints (3.5). C. Problem Definitions Let F ∈ ( 41 , 1] be a given fidelity threshold. A path π is fidelity-feasible if and only if F (π) ≥ F. We can translate the fidelity threshold F into a corresponding Werner-parameter threshold W = 4F3−1 . Then a path π is fidelity-feasible if and only if W (π) ≥ W. Let ∆ = − ln W. Then the Werner-parameter constraint W (π) ≥ W is equivalent to the additive loss constraint ℓ(π) ≤ ∆. Since F (π) ≥ F ⇐⇒ W (π) ≥ W ⇐⇒ ℓ(π) ≤ ∆

(3.8)

We can equivalently consider the fidelity constraint F (π) ≥ F or the Werner-parameter constraint W (π) ≥ W or the fidelity-loss constraint ℓ(π) ≤ ∆. We study the following decision problems. Definition 1 (RS). Given a quantum network G = (V, E, c, w, q) , a commodity set D where |D| = K , a fidelity requirement F and a rate sum requirement T, the fidelity-aware Rate-Sum rate allocation problem, denoted by RS, asks whether there exists a rate allocation P P = (P1 , P2 , . . . , PK ) such that all positive-rate paths satisfy the fidelity requirement W (π) ≥ W = 4F3−1 , K k=1 Rk ≥ T, and the link-capacity constraints (3.5) are satisfied. □ We use RS(G, D, F, T) to denote an instance of RS, where G = (V, E, c, w, q) is the quantum network, D is the demand set, F is the fidelity requirement, and T is the total-throughput requirement. For the example in Fig. 1, we consider a demand set D = {(s1 , t1 ), (s2 , t2 )}, where s1 = a, t1 = c, s2 = b, and t2 = d. Consider the instance RS(G, D, 0.775, 10). Set P1 = {(π1 , 3), (π2 , 4)} and P2 = {(π4 , 3)}. Then P = (P1 , P2 ) forms a feasible solution for RS(G, D, 0.775, 10). To see this, we first note that P satisfies all link-capacity constraints. Moreover, all positive-rate paths satisfy W (π) ≥ 0.7, which is equivalent to the fidelity requirement F (π) ≥ 0.775. Since R1 = 7, R2 = 3, we have R1 + R2 = 10, and hence the total-throughput requirement is also satisfied. In contrast, set P1′ = {(π1 , 3), (π2 , 2)} and P2′ = {(π3 , 1), (π4 , 3)}. Although P ′ = (P1′ , P2′ ) satisfies the fidelity and link-capacity constraints, it has total throughput R1 + R2 = 9 < 10. Therefore, P ′ is not a feasible solution for RS(G, D, 0.775, 10). The RS problem imposes a requirement only on total throughput and provides no per-commodity service guarantee. We therefore introduce a second problem that adds a per-commodity minimum-rate constraint. Definition 2 (RS-mRC). Given a quantum network G = (V, E, c, w, q), a commodity set D where |D| = K , a fidelity requirement F and a rate sum requirement T, together with a minimum rate requirement Tmin , the fidelityaware Rate-Sum subject to minimum-Rate-Constraint rate allocation problem, denoted by RS-mRC, asks whether there exists a rate allocation P = (P1 , P2 , . . . , PK ) such that all positive-rate paths satisfy W (π) ≥ W = 4F3−1 , PK □ k=1 Rk ≥ T, min Rk ≥ Tmin , and the link-capacity constraints (3.5) are satisfied. 1≤k≤K

We use RS-mRC(G, D, F, T, Tmin ) to denote an instance of RS-mRC, where G = (V, E, c, w, q) is the quantum network, D is the demand set, F is the fidelity requirement, T is the total-throughput requirement, and Tmin is the minimum-rate requirement. For the example in Fig. 1, we consider the same demand set as above. Consider the instance RS-mRC(G, D, 0.775, 10, 4). Set P1 = {(π1 , 3), (π2 , 3)} and P2 = {(π3 , 1), (π4 , 3)}. Then P = (P1 , P2 ) forms a feasible solution for RS-mRC(G, D, 0.775, 10, 4). To see this, we first note that P satisfies all link-capacity constraints. Moreover, all positive-rate paths satisfy W (π) ≥ 0.7, which is equivalent to the fidelity requirement F (π) ≥ 0.775. Since

5

R1 = 6, R2 = 4, we have R1 + R2 = 10 and min{R1 , R2 } = 4. Hence, both the total-throughput and minimumrate requirements are satisfied. In contrast, set P1′ = {(π1 , 3), (π2 , 4)} and P2′ = {(π4 , 3)}. Although P ′ = (P1′ , P2′ ) satisfies the fidelity and link-capacity constraints and has total throughput R1 + R2 = 10, it has min{R1 , R2 } = 3 < 4. Therefore, P ′ is not a feasible solution for RS-mRC(G, D, 0.775, 10, 4). Although RS-mRC provides a baseline service guarantee by imposing a minimum-rate constraint, many resource-allocation systems adopt the stronger criterion of max-min fairness [12], [31]. A system is max-min fair if no user’s resource allocation can be increased without decreasing the resource allocation of another user whose allocation is no larger. We formalize max-min fairness using lexicographic ordering as follows. Let X = (x1 , x2 , . . . , xK ) and Y = (y1 , y2 , . . . , yK ). We write X ≻lex Y if there exists an index i ≤ K such that xi > yi and xk = yk for all k < i. We write X ⪰lex Y if X = Y or X ≻lex Y. We write X ≺lex Y if Y ≻lex X. We write X ⪯lex Y if Y ⪰lex X. For any vector X, let X↑ denote the vector obtained by sorting its entries in nondecreasing order. For example, let x = (2, 4, 1) and y = (2, 3, 10). Then x↑ = (1, 2, 4) and y ↑ = (2, 3, 10). Note that x ≻lex y , whereas x↑ ≺lex y ↑ .

Definition 3 (MmFair). Given a quantum network G = (V, E, c, w, q), a commodity set D where |D| = K , a fidelity requirement F and a nondecreasing threshold vector η = (η1 , η2 , . . . , ηK ), the Max-Min-Fair rate allocation problem, denoted by MmFair, asks whether there exists a rate allocation P = (P1 , P2 , . . . , PK ) such that all positive-rate paths satisfy W (π) ≥ W = 4F3−1 , the link-capacity constraints (3.5) are satisfied, and the sorted throughput vector satisfies R↑ ⪰lex η , where R = (R1 , R2 , . . . , RK ). □ Let R⋆↑ denote the lexicographically maximum sorted throughput vector among all rate allocations satisfying the fidelity and link-capacity constraints. Then an MmFair instance is feasible if and only if R⋆↑ ⪰lex η. Thus, MmFair asks whether the achievable max-min-fair throughput vector meets the prescribed threshold η . We use MmFair(G, D, F, η) to denote an instance of MmFair, where G = (V, E, c, w, q) is the quantum network, D is the demand set, F is the fidelity requirement, and η is the fairness-threshold vector. For the example in Fig. 1, we consider the same demand set as above. Consider the instance MmFair(G, D, 0.775, (5, 5)). Set P1 = {(π1 , 3), (π2 , 2)} and P2 = {(π3 , 2), (π4 , 3)}. Then P = (P1 , P2 ) forms a feasible solution for MmFair(G, D, 0.775, (5, 5)). To see this, we first note that P satisfies all link-capacity constraints. Moreover, all positive-rate paths satisfy W (π) ≥ 0.7, which is equivalent to the fidelity requirement F (π) ≥ 0.775. Since R1 = 5, R2 = 5, we have R↑ (P) = (5, 5) ⪰lex (5, 5). Hence, the fairness-threshold requirement is also satisfied. In contrast, set P1′ = {(π1 , 3), (π2 , 3)} and P2′ = {(π3 , 1), (π4 , 3)}. Although P ′ = (P1′ , P2′ ) satisfies the fidelity and link-capacity constraints, its commodity-throughput vector is R(P ′ ) = (6, 4), and hence R↑ (P ′ ) = (4, 6) ≺lex (5, 5). Therefore, P ′ is not a feasible solution for MmFair(G, D, 0.775, (5, 5)). D. Computational Complexity The authors of [5] presented a polynomial-time algorithm for a special case of RS where all edges have identical Werner parameters. The general versions of RS, RS-mRC, and MmFair are all NP-hard, even for the case K = 1. Theorem 1. The problems RS, RS-mRC, and MmFair are all NP-hard, even for the case K = 1.

□

Proof. RS-mRC is equivalent to RS when K = 1, with Tmin = T. Similarly, MmFair is equivalent to RS when K = 1, with η = (T). To prove Theorem 1, it suffices to prove that RS is NP-hard when K = 1. We prove Theorem 1 by a reduction from Partition [8]. An instance of Partition is given by a finite set A, where each a ∈ A is associated P with a positive P integer s(a), known as the size of a. It asks for the existence of ′ a subset A of A such that a∈A′ s(a) = a∈A\A′ s(a). This problem is known to be NP-hard [8]. We outline a reduction from Partition to RS in the following, with the help of Fig. 2. Let an instance I1 of Partition be given by A = {a1 , a2 , . . . , aL } and size function s. We construct an instance I2 of RS as follows. The set of vertices of graph G(V, E) is given by V = {u0 , v1 , u1 , v2 , u2 , . . . , uL−1 , vL , uL }. For each element al ∈ A, E contains (ul−1 , ul ), (ul−1 , vl ) and (vl , ul ). We call (ul−1 , ul ) a primary edge (solid red in Fig. 2). It

6

has capacity 1 and Werner parameter exp(−s(al )) = e−s(al ) , where e is the base of the natural logarithm. We call (ul−1 , vl ) and (vl , ul ) a two-edge detour (dashed blue in Fig. 2). Each has capacity 1 and Werner parameter P 1 W 1. Set q = 1, K = 1, T = 2, W = e− 2 1≤i≤L s(ai ) , F = 1+3 4 , s1 = u0 , t1 = uL . This completes the construction of I2 .

Fig. 2: Reduction from Partition to RS. P P Suppose I1 has a feasible solution, i.e., there exists A′ ⊆ A such that a∈A′ s(a) = a∈A\A′ s(a). Define two u0 -uL paths π1 and π2 as follows. For each l ∈ {1, 2, . . . , L}, π1 uses the primary edge (ul−1 , ul ) when al ∈ A′ , and uses the detour edges (ul−1 , vl ), (vl , ul ) when al ̸∈ A′ ; π2 uses the detour edges (ul−1 , vl ), (vl , ul ) when al ∈ A′ , and uses the primary edge (ul−1 , ul ) when al ̸∈ A′ . Since π1 and P π2 do not share any edge, we can have a flow of 1 P on each path. Since the Werner parameter of π1 is e− a∈A′ s(a) = W, and the Werner parameter of π2 is e− a∈A\A′ s(a) = W, {(π1 , 1), (π2 , 1)} is a feasible solution for I2 . Conversely, suppose I2 has a feasible solution. Let {π1 , π2 ,P . . . , πM } be its positive-rate paths, with corresponding rates r1 , r2 , . . . , rM > 0, whose total throughput is M i=1 ri = 2 (the sum cannot be larger than 2, because the max flow from u0 to uL is 2). For each path πi , let Bi ⊆QA denote the set of elements al such
that P πi uses the primary edge (ul−1 , ul ). The Werner parameter of πi is e∈πi w(e) = exp − a∈Bi s(a) . Since πi is fidelity-feasible, we have ! ! X 1X s(a) ≥ W = exp − exp − s(a) . (3.9) 2 a∈A

a∈Bi

Therefore, for every i ∈ {1, 2, . . . , M }, we have X

s(a) ≤

a∈Bi

1X s(a). 2

(3.10)

a∈A

Now consider any stage l ∈ {1, 2, . . . , L}. Every u0 -uL path must go from ul−1 to ul either through the primary edge (ul−1 , ul ) or through the two-edge detour (ul−1 , vl ), (vl , ul ). The total capacity of these two alternatives is 2, and the total feasible throughput is 2. Hence, in every stage l, both alternatives must be saturated. P In particular, the total flow using the primary edge (ul−1 , ul ) is exactly 1. Thus, for every l ∈ {1, 2, . . . , L}, i:al ∈Bi ri = 1. It follows that M L L X X X X X ri s(al ) = s(al ) ri = s(al ). (3.11) i=1

Since

al ∈Bi

i:al ∈Bi

l=1

PM

i=1 ri = 2, the rate-weighted average of the quantities

PM

l=1

P

a∈Bi s(a) is

L 1X 1X al ∈Bi s(al ) = s(al ) = s(a). PM 2 2 i=1 ri a∈A l=1

i=1 ri

P

Equality (3.12) and inequality (3.10) imply that X 1X s(a) = s(a), i = 1, 2, . . . , M. 2 a∈Bi

(3.12)

(3.13)

a∈A

Therefore A′ = B1 is a feasible solution to I1 . This proves that RS is NP-hard even for K = 1.

7

□

4. O PTIMIZATION PROBLEMS In this section, we define the optimization versions of the three decision problems. Unlike the decision problems, where a fidelity threshold is given as part of the input, the optimization problems seek to maximize the minimum end-to-end fidelity among all positive-rate paths while meeting a prescribed throughput or fairness requirement. Equivalently, under the fidelity-loss representation, they minimize the maximum path fidelity loss. We develop fully polynomial-time approximation schemes for these optimization problems in the subsequent sections. Let Pk be a rate allocation for demand (sk , tk ) where k ∈ [K]. The Werner parameter, the fidelity, and the fidelity loss of Pk are respectively: W (Pk ) =

W (π),

(4.1)

1 + 3W (Pk ) . 4

(4.2)

ℓ(π).

(4.3)

min (π,rπ )∈Pk : rπ >0

F (Pk ) =

∆(Pk ) =

max (π,rπ )∈Pk : rπ >0

Note that W (Pk ) is the minimum over the Werner parameter of sk -tk path π such that (π, rπ ) ∈ Pk where rπ > 0; F (Pk ) is the minimum over the fidelity of sk -tk path π such that (π, rπ ) ∈ Pk where rπ > 0; ∆(Pk ) is the maximum over the fidelity loss of sk -tk path π such that (π, rπ ) ∈ Pk where rπ > 0. In the extreme case where rπ = 0 for every (π, rπ ) ∈ Pk , we define W (Pk ) = 1, F (Pk ) = 1, and ∆(Pk ) = 0. This convention is slightly different from the mathematical convention that the maximum over an empty set is −∞ and the minimum over an empty set is ∞. We adopt these values as a bookkeeping convention for an inactive commodity. They lie within the physical ranges of the corresponding quantities and make an inactive commodity neutral in the aggregate definitions below. For a rate allocation P = (P1 , P2 , . . . , PK ), the minimum Werner parameter, the minimum fidelity, and the maximum fidelity loss of P are respectively: W (P) = min W (Pk ),

(4.4)

1 + 3W (P) . 4

(4.5)

∆(P) = max ∆(Pk ).

(4.6)

k∈[K]

F (P) =

k∈[K]

In the extreme case where rπ = 0 for every (π, rπ ) ∈ Pk and every k ∈ [K], we define W (P) = 1, F (P) = 1, and ∆(P) = 0, as a convention. Note that only positive-rate paths are included in the above definitions, since a zero-rate path can be removed from the allocation without affecting its throughput or capacity consumption. Note that maximizing F (P) is equivalent to maximizing W (P) = e−∆(P) , which is equivalent to minimizing ∆(P).

8

A. Optimization Versions We define the optimization versions of RS, RS-mRC and MmFair as follows. Definition 4 (oRS). Given a quantum network G = (V, E, c, w, q), a commodity set D where |D| = K , and a total-throughput requirement T, the optimization P version of RS, denoted by oRS, asks for a rate allocation P = (P1 , . . . , PK ) that minimizes ∆(P) subject to K □ k=1 Rk ≥ T and link-capacity constraints. We use oRS(G, D, T) to denote an instance of oRS, where G = (V, E, c, w, q) is the quantum network, D is the demand set, and T is the total-throughput requirement. We use ∆oRS opt (G, D, T) to denote the optimal value of oRS(G, D, T). For ease of reading, we may simply use ∆oRS to denote ∆oRS opt opt (G, D, T), if the exact meaning can be obtained from the context without ambiguity. For the example in Fig. 1, we consider a demand set D = {(s1 , t1 ), (s2 , t2 )} where s1 = a, t1 = c, s2 = b, t2 = d. Consider the instance oRS(G, D, 4). Set P1 = {(π2 , 4)} and P2 = ∅. Then P = (P1 , P2 ) forms an optimal solution for oRS(G, D, 4), with optimal fidelity loss ∆oRS opt (G, D, 4) = − ln 0.95. To see why P = (P1 , P2 ) is an P2optimal solution for oRS(G, D, 4), we first note that P satisfies the link-capacity constraints in (3.5). Since k=1 Rk (P) = 4, P satisfies the throughput constraint. Since the minimum fidelity-loss of any s1 -t1 path is − ln 0.95 and the minimum fidelity-loss of any s2 -t2 path is − ln 0.9 > − ln 0.95, P is an optimal solution for instance oRS(G, D, 4). Consider the instance oRS(G, D, 6). Set P1′ = {(π2 , 4)} and P2′ = {(π4 , 2)}. Then P ′ = (P1′ , P2′ ) forms an optimal solution for oRS(G, D, 6) with ∆oRS opt (G, D, 6) = − ln 0.7. Definition 5 (oRS-mRC). Given a quantum network G = (V, E, c, w, q), a commodity set D where |D| = K , a total-throughput requirement T and a minimum-rate requirement Tmin , the optimization version of RSmRC, PK denoted by oRS-mRC, asks for a rate allocation P = (P1 , P2 , . . . , PK ) that minimizes ∆(P) subject to □ k=1 Rk ≥ T, min Rk ≥ Tmin and all link-capacity constraints. 1≤k≤K

We use oRS-mRC(G, D, T, Tmin ) to denote an instance of oRS-mRC, where G = (V, E, c, w, q) is the quantum network, D is the demand set, T is the total-throughput requirement, and Tmin is the minimum rate requirement. We use ∆mRC opt (G, D, T, Tmin ) to denote the optimal value of oRS-mRC(G, D, T, Tmin ). For ease of reading, we mRC may simply use ∆mRC opt to denote ∆opt (G, D, T, Tmin ), if the exact meaning can be obtained from the context without ambiguity. For the example in Fig. 1, we consider the same demand set as above. Consider the instance oRS-mRC(G, D, 4, 2). Set P1 = {(π2 , 2)} and P2 = {(π3 , 2)}. Then P = (P1 , P2 ) forms an optimal solution for oRS-mRC(G, D, 4, 2) with ∆mRC opt (G, D, 4, 2) = − ln 0.9. WePcan verify that P satisfies the link-capacity constraints in (3.5). Since R1 (P) = 2 and R2 (P) = 2, we have 2k=1 Rk (P) ≥ 4 and min1≤k≤2 Rk (P) ≥ 2. Therefore P satisfies both the total-throughput constraint (T = 4) and the minimum rate constraint (Tmin = 2). Moreover, commodity 2 must receive rate at least 2, and its highest-Werner-parameter path is π3 , with W (π3 ) = 0.9. Hence, no feasible allocation can have maximum path loss smaller than − ln 0.9. Therefore, ∆mRC opt = − ln 0.9. ′ Consider the instance oRS-mRC(G, D, 6, 3). Set P1 = {(π1 , 1), (π2 , 2)} and P2′ = {(π3 , 2), (π4 , 1)}. Then ′ P = (P1′ , P2′ ) forms an optimal solution for oRS-mRC(G, D, 6, 3) with ∆mRC opt (G, D, 6, 3) = − ln 0.7. Definition 6 (oMmFair). Given a quantum network G = (V, E, c, w, q), a commodity set D where |D| = K , and a fairness-threshold vector η = (η1 , η2 , . . . , ηK ), the optimization version of MmFair, denoted by oMmFair, asks for a rate allocation P = (P1 , P2 , . . . , PK ) that minimizes ∆(P) subject to R↑ (P) ⪰lex η , and all link-capacity constraints. □ We use oMmFair(G, D, η) to denote an instance of oMmFair, where G = (V, E, c, w, q) is the quantum network, D is the demand set, and η is the fairness-threshold vector. We use ∆fair opt (G, D, η) to denote the fair optimal value of oMmFair(G, D, η). For ease of reading, we may simply use ∆opt to denote ∆fair opt (G, D, η), if the exact meaning can be obtained from the context without ambiguity.

9

For the example in Fig. 1, we consider the same demand set as above. Consider the instance oMmFair(G, D, (2, 2)). Set P1 = {(π2 , 2)} and P2 = {(π3 , 2)}. Then P = (P1 , P2 ) forms an optimal solution for oMmFair(G, D, (2, 2)), with optimal fidelity loss ∆fair opt (G, D, (2, 2)) = − ln 0.9. To see why P = (P1 , P2 ) is an optimal solution for oMmFair(G, D, (2, 2)), we first note that P satisfies the link-capacity constraints in (3.5). Since R↑ (P) = (2, 2) ⪰lex η, P satisfies the fairness-threshold constraint. Moreover, satisfying R↑ (P) ⪰lex (2, 2) requires both commodities to receive rate at least 2. The minimum fidelity loss of any s2 -t2 path is − ln 0.9. Hence, no feasible allocation can have maximum fidelity loss smaller than − ln 0.9. Therefore, P is an optimal solution for oMmFair(G, D, (2, 2)). Consider the instance oMmFair(G, D, (3, 3)). Set P1′ = {(π1 , 1), (π2 , 2)} and P2′ = {(π3 , 2), (π4 , 1)}. Then ′ P = (P1′ , P2′ ) forms an optimal solution for oMmFair(G, D, (3, 3)) with ∆fair opt (G, D, (3, 3)) = − ln 0.7. Note that oMmFair does not lexicographically maximize the throughput vector as its objective. The fairness threshold η is prescribed, and the objective is to minimize the maximum fidelity loss while meeting this threshold. The lexicographically maximum vector is computed later only to test feasibility under a fixed loss threshold. B. Relationship to the Decision Problems If no rate allocation satisfies the corresponding throughput or fairness requirements together with the link-capacity constraints, the optimization instance is infeasible. Proposition 1. For each of RS, RS-mRC, and MmFair, feasibility is monotone in the fidelity-loss threshold. Moreover, if the corresponding optimization problem is feasible, its optimal value is the smallest loss threshold under which the decision problem is feasible. In particular, for any ∆ ≥ 0, the corresponding decision instances mRC fair are feasible if and only if ∆oRS □ opt ≤ ∆, ∆opt ≤ ∆, ∆opt ≤ ∆, respectively. Proof. Consider first RS. A rate allocation P is feasible under loss threshold ∆ if and only if it satisfies the throughput and link-capacity constraints and ∆(P) ≤ ∆. By the definition of ∆oRS opt , such an allocation exists if and only if ∆oRS ≤ ∆. The same argument applies to RS-mRC and MmFair. opt Furthermore, if a rate allocation P is feasible under threshold ∆, then P remains feasible under every threshold ∆′ ≥ ∆. Hence, feasibility is monotone in the fidelity-loss threshold. C. Approximation Parameters In this paper, we will design fully polynomial-time approximation schemes (FPTAS) for the three optimization problems defined in Section 4-A. For any feasible instance of the three optimization problems, let Fopt , Wopt , and ∆opt denote the fidelity, Werner parameter, and fidelity loss of the optimal rate allocation, respectively. Then we must have 4Fopt − 1 Wopt = , and ∆opt = − ln Wopt (4.7) 3 For any feasible rate allocation P , we have 4F (P) − 1 , and ∆(P) = − ln W (P) (4.8) 3 Lemma 1. For any δ ∈ (0, 1), set ϵ = e3 δ , where e is the base of natural logarithm. Then ϵ ∈ (0, 1). Furthermore, let P be any feasible rate allocation such that W (P) =

∆(P) ≤ (1 + ϵ)∆opt .

(4.9)

F (P) ≥ (1 − δ)Fopt .

(4.10)

Then

□ For ease of reading, we leave the proof of this lemma in the appendix.

10

By the standard definition [8], [13], an FPTAS for oRS (oRS-mRC, oMmFair) can compute a rate allocation P such that F (P) ≥ (1 − δ)Fopt while satisfying the link-capacity constraints and the throughput or fairness requirement, for any δ ∈ (0, 1), with running time bounded by a polynomial in the instance size and 1δ . When ϵ = e3 δ , 1ϵ = e3 × 1δ . Hence a running time bounded by a polynomial in the instance and 1ϵ is also bounded by a polynomial in the instance and 1δ . By Lemma 1, it suffices to design an FPTAS in the fidelity-loss domain that can compute a rate allocation P such that ∆(P) ≤ (1 + ϵ)∆opt while satisfying the link-capacity constraints and the throughput or fairness requirement, for any ϵ ∈ (0, 1], with running time bounded by a polynomial in the instance size and 1ϵ . 5. I NTEGER V ERSION OF RS We consider a special case of RS in which the fidelity loss of an edge takes integer values. We develop a pseudo-polynomial-time algorithm to solve iRS. This algorithm is a building block for the FPTAS for the general problems. A. Integer RS For each physical edge e ∈ E , recall that its fidelity loss is ℓ(e) = − ln w(e). For computational purposes, we assume that each edge loss ℓ(e) is a rational number represented in binary. Since w(e) = e−ℓ(e) , in this section we equivalently represent the network as G = (V, E, c, ℓ, q) and consider a special case of RS, denoted by iRS, in which the fidelity loss of an edge takes integer values: ℓ(e) ∈ Z≥0 , ∀e ∈ E . Let L ∈ Z≥0 be an integer fidelity-loss budget. We denote by iRS(G, D, L, T) an instance of iRS with throughput requirement T and fidelity-loss constraint L. B. Hop-Fidelity Expanded Graph The authors of [5] designed a polynomial-time multicommodity-flow-based algorithm to solve a special case of RS where the Werner parameters on all edges are identical. Their algorithm used the concept of layered graph, which appears in Ford and Fulkerson [7, Ch. III, §9, pp. 142-151] in the study of maximal dynamic flows and was later used in [19], [30] for delay-constrained multipath routing. To capture the effect of both hop-count (for entanglement swapping) and fidelity-loss, we use two state dimensions. The fidelity-loss coordinate is needed to enforce the path fidelity constraint, while the hop-count coordinate is needed because a path with h physical edges requires h − 1 swapping operations and hence has end-to-end success probability q h−1 . Accordingly, we D D generalize the layered-graph idea to a hop-fidelity expanded graph GD L = (VL , EL ) for given D and L, where n o VLD = u[h,d] : u ∈ V, 0 ≤ h < n, 0 ≤ d ≤ L, h, d ∈ Z . Here, u[h,d] denotes the state of being at node u after traversing h physical hops from the source and accumulating fidelity-loss cost d. For each physical edge e = (u, v) ∈ E , ELD contains an expanded edge from u[h,d] to v [h+1,d+ℓ(e)] provided that h + 1 ≤ n − 1 and d + ℓ(e) ≤ L: n o
ELD = u[h,d] , v [h+1,d+ℓ(e)] : e = (u, v) ∈ E, 0 ≤ h < n − 1, 0 ≤ d ≤ L − ℓ(e) .
Since each edge in ELD is in the form u[h,d] , v [h+1,d+ℓ(e)] , the hop-fidelity expanded graph GD L is a directed acyclic graph (DAG), due to the hop-count increase from h to h + 1. The acyclic nature makes the hop-fidelity expanded graph GD L a useful tool in solving iRS. More importantly, a physical sk -tk path in G with h hops and [0,0] [h,d] integer fidelity loss d ≤ L corresponds to a path from sk to tk in the expanded graph. Conversely, every [0,0] [h,d] path from sk to tk in the expanded graph projects to an sk -tk walk in G with h hops and fidelity loss d. We use a simple example to illustrate the construction of GD L. Fig. 3 shows the graph G. There are 4 vertices and 5 edges in the graph. The label on each edge e shows (c(e), ℓ(e)). Assume D = {(s1 , t1 )} = {(s, t)} and L = 3. The hop-fidelity expanded graph GD L is shown [0,0] [1,1] in Fig. 4. The physical path s → u → t in G corresponds to the expanded path s →u →t[2,3] in GD L. The physical path s → u → v → t in G corresponds to the expanded path s[0,0] →u[1,1] →v [2,2] →t[3,3] in GD L.

11

(4, 1)

v (5, 1)

) ,4 (8

s

t

(6, 1)

)

,2

(2

u

Fig. 3: Physical graph G = (V, E, c, ℓ, q). The label on edge e denotes (c(e), ℓ(e)).

Fig. 4: Expanded graph GD L corresponding to the graph G in Fig. 3 with D = {(s1 , t1 )} = {(s, t)} and L = 3. The [0,0] [1,1] 3-hop path s →u →v [2,2] →t[3,3] in GD L (using purple and red edges) corresponds to the path s→u→v→t in G. The 2-hop path s[0,0] →u[1,1] →t[2,3] in GD L (using purple and blue edges) corresponds to the path s→u→t in G. Conversely, the expanded path s[0,0] →u[1,1] →t[2,3] in GD L projects to the physical path s → u → t in G, and the expanded path s[0,0] →u[1,1] →v [2,2] →t[3,3] in GD projects to the physical path s → u → v → t in G. L C. An Exact Algorithm for iRS Our algorithm for iRS is based on a Linear Programming (LP) formulation. For an instance iRS(G, D, L, T), we [0,0] construct the hop-fidelity expanded graph GD to terminal L , then solve an LP problem based on flows fk from sk [h,d] L nodes Ωk = {tk : 1 ≤ h < n, 0 ≤ d ≤ L}, k ∈ [K]. For each commodity k and expanded edge (µ, ν), let fk (µ, ν) denote the elementary-pair generation rate allocated to commodity k on that edge. The resulting LP is formally presented in (5.1). For clarity, we use u and v to denote physical nodes in G, and use µ, ν , ξ , and v [h,d] for nodes in the expanded graph.

12

LPRS (G, D, L) :

max ΦL =

K n−1 L X XX

q h−1

k=1 h=1 d=0

s.t.

X (µ,ν)∈E

(µ,t

[h,d] k

)∈E

)

(5.1a)

D L

[0,0]

∀ν ∈ VLD \ ({sk

fk (ν, ξ),

(ν,ξ)∈E

K n−2 X X L−ℓ(e) X

[h,d]

fk (µ, tk

X

fk (µ, ν) = D L

X

} ∪ ΩL k ), ∀k ∈ [K],

(5.1b)

∀e = (u, v) ∈ E : ℓ(e) ≤ L,

(5.1c)

D L

  fk u[h,d] , v [h+1,d+ℓ(e)] ≤ c(e),

k=1 h=0 d=0

fk (µ, ν) = 0, ∀(µ, ν) ∈ ELD , fk (µ, ν) ≥ 0,

∀k,

∀µ ∈ ΩL k,

∀k ∈ [K],

∀(µ, ν) ∈ ELD .

(5.1d) (5.1e)

The objective (5.1a) maximizes the total delivered throughput over all commodities. An expanded terminal [h,d] state tk represents reaching destination tk after traversing h physical edges and accumulating fidelity loss d. If x units of elementary-pair generation flow reach this state, the corresponding path requires h − 1 entanglementswapping operations. Since each swapping operation succeeds independently with probability q , only q h−1 x units [h,d] of end-to-end entanglement are successfully delivered. Therefore, the incoming flow collected at tk is weighted by q h−1 . Summing over all terminal states, all feasible loss values, and all commodities gives the total delivered throughput in (5.1a). For each k ∈ [K], define n−1 L XX

Rk (f )=

h=1 d=0

q h−1 (µ,t

X

[h,d] k

[h,d]

fk (µ, tk

)∈E

).

(5.2)

D L

Rk (f ) is the delivered throughput of commodity k . Consequently, ΦL =

K X

Rk (f ).

(5.3)

k=1

Constraint (5.1b) enforces flow conservation at all non-source and nonterminal states. Constraint (5.1c) imposes link capacities. The formulation also applies to undirected graphs by replacing each undirected edge with two oppositely directed edges sharing the same edge capacity, and the link-capacity constraint (5.1c) can be replaced by a joint constraint requiring the total flow in both directions not to exceed the capacity. Note that we impose the capacity constraint only for edges e ∈ E with ℓ(e) ≤ L, since edges with ℓ(e) > L have no corresponding expanded edges in GD L . Constraint (5.1d) prevents flow from leaving the terminal states. For the example in Fig. 3, consider the instance iRS(G, D, L, T) with D = {(s, t)}, L = 3, T = 2 and q = 0.5. We construct the hop-fidelity expanded graph GD L and solve the corresponding LPRS (G, D, L). An optimal solution of LPRS (G, D, L) is f1 (s[0,0] , u[1,1] ) = 6, f1 (u[1,1] , t[2,3] ) = 2, f1 (u[1,1] , v [2,2] ) = 4, f1 (v [2,2] , t[3,3] ) = 4, with all other flow variables equal to zero. The corresponding objective value is Φ⋆3 = 0.5 × 2 + 0.52 × 4 = 2. Following the chain-decomposition procedure of Ford and Fulkerson [7], we can decompose f into expanded paths. Starting from a terminal node with positive incoming flow, e.g. t[2,3] , and tracing positive-flow incoming edges backward to s[0,0] gives the expanded path π b1 : s[0,0] → u[1,1] → t[2,3] . The bottleneck flow value of π b1 is b(π b1 ) = 2. We then set f1 (e) ← f1 (e) − b(π b1 ) for every edge e on π b1 to obtain the residual flow. We continue this process until no terminal node has a positive incoming flow. The process then yields π b2 : s[0,0] → u[1,1] → [2,2] [3,3] v → t , with b(π b2 ) = 4 in addition to π b1 with b(π b1 ) = 2. Each extracted expanded path is then projected onto the physical graph by removing the hop and fidelityloss indices of its vertices. For example, π b1 : s[0,0] → u[1,1] → t[2,3] projects to π1 : s → u → t, while

13

π b2 : s[0,0] → u[1,1] → v [2,2] → t[3,3] projects to π2 : s → u → v → t. The terminal states show that π1 and π2 have respectively 2 and 3 hops, both with fidelity loss 3. Thus, their delivered rates are rπ1 = q 2−1 b(π b1 ) = 0.5 × 2 = 1 b2 ) = 0.52 × 4 = 1. Hence, the extracted rate allocation is P1 = {(π1 , 1), (π2 , 1)}, with total and rπ2 = q 3−1 b(π delivered throughput R1 = 2. We formalize this path extraction process in the following. Path extraction. In general, we extract a rate allocation from an optimal solution f of LPRS (G, D, L), following the chain-decomposition procedure of Ford and Fulkerson [7, Ch. I, §2, pp. 4-9]. For each commodity k ∈ [K] we [h,d] [h,d] initialize Pk to ∅. Then, select any terminal state tk in ΩL , trace k with positive incoming flow. Starting from tk [0,0] [0,0] [h,d] backward along positive-flow edges until reaching sk . This produces an expanded path π b : sk → · · · → tk , [0,0] with a bottleneck flow value b(π b) ≜ min(µ,ν)∈πb fk (µ, ν) > 0. The backward trace always ends at sk due to both acyclicity and flow conservation. Every backward step decreases the hop index, so the process cannot continue indefinitely. If it stopped at a non-source state while the selected outgoing edge had positive flow, flow conservation would imply positive incoming flow at that state, contradicting termination. Therefore it must reach [0,0] sk . Project the expanded path π b to obtain the corresponding physical path π in G . Since deleting cycles does not violate the link-capacity constraints, does not increase fidelity loss, and does not increase path hop count, we can assume that π is a simple path, without loss of generality. If there exists (π, α) ∈ Pk for some α > 0, replace (π, α) with (π, α+b(π b)×q h−1 ). Otherwise, set Pk ← Pk ∪{(π, b(π b)×q h−1 )}. We then set fk (e) ← fk (e)−b(π b) for every edge e on π b to obtain the residual flow. We continue this process until no terminal node has a positive incoming flow.

Lemma 2. An instance iRS(G, D, L, T) is feasible if and only if the optimal value Φ⋆L of LPRS (G, D, L) satisfies Φ⋆L ≥ T. Moreover, whenever Φ⋆L ≥ T, a feasible rate allocation P = (P1 , P2 , . . . , PK ) of iRS(G, D, L, T) can be extracted from an optimal solution of LPRS (G, D, L) using the above path extraction process. □ Proof. Suppose first that the instance iRS(G, D, L, T) is feasible. Assume that P P = (P1 , P2 , . . . , PK ) is a feasible rate allocation for iRS(G, D, L, T). We must have ∆(Pk ) ≤ L for k ∈ [K], K k=1 Rk (P) ≥ T and the link-capacity constraints in (3.5) are satisfied. P Let (π, rπ ) ∈ Pk for some k ∈ [K]. Let π = v0 → v1 → · · · → vh , and let di = ia=1 ℓ(va−1 , va ), i = 1, 2, . . . , h. Define d0 = 0 as a technical convention. Since dh = ℓ(π) ≤ L, π induces the expanded path [0,0] [1,d ] [h,d ] [a−1,d ] [a,d ] rπ for a = 1, 2, . . . , h. For any k ∈ [K] and v0 → v1 1 → · · · → vh h . Define fkπ (va−1 a−1 , va a ) = qh−1 D any (µ, ν) ∈ EL , define X fk (µ, ν) = fkπ (µ, ν). (5.4) (π,rπ )∈Pk

For each positive-rate physical path π , its induced expanded path carries the same elementary-pair generation flow rπ /q h−1 on every expanded edge, and hence satisfies flow conservation at all intermediate expanded nodes. Therefore, summing over all paths preserves constraint (5.1b). Moreover, forP any physical edge e, summing the K P rπ , which is at constructed flows over all expanded copies corresponding to e gives exactly k=1 (π,rπ )∈Pk qh−1 e∈π

most c(e) by the link-capacity constraints in (3.5). Hence, constraint (5.1c) is alsoPsatisfied. This shows that f is a feasible solution for LPRS (G, D, L) with an objective function value equal to K k=1 Rk (P) ≥ T. Therefore PK ⋆ ΦL ≥ k=1 Rk (P) ≥ T. Conversely, suppose LPRS (G, D, L) has a feasible solution with objective value at least T. Let f be an optimal solution for LPRS (G, D, L) with an objective function value Φ⋆L ≥ T. Apply the path-extraction procedure described above to obtain a rate allocation P = (P1 , . . . , PK ). In each iteration, subtracting the bottleneck value b(π b) from every edge of π b preserves nonnegativity and flow conservation; each extraction zeros at least one positive-flow expanded edge, so the process terminates. Consider an extracted expanded path π b ending at [h,d] tk . After projection and cycle removal, it yields a simple physical path π with ℓ(π) ≤ d ≤ L. The assigned delivered rate is rπ = q h−1 b(π b). If cycle removal reduces the number of hops from h to h′ ≤ h, then the ′ b) ≤ b(π b), so the link-capacity constraints required elementary-pair generation rate on π is qhr′π−1 = q h−h b(π remain satisfied.

14

Moreover, each extracted expanded path contributes q h−1 b(π b) to the LP objective and exactly the same amount to the delivered throughput. Therefore, for everyP commodity k ∈ [K], summing over its extracted paths gives P K ⋆ Rk (P) = Rk (f ). Consequently, K R (P) = k k=1 k=1 Rk (f ) = ΦL . Therefore, summing over all extracted paths gives a feasible rate allocation P = (P1 , . . . , PK ) whose total delivered throughput equals Φ⋆L ≥ T. Hence, the iRS instance is feasible. We summarize our algorithm for iRS in Algorithm 1.
Lemma 3. Algorithm 1 correctly solves the iRS problem in O (Kmn(L + 1))4 L time, where L denotes the input size of the iRS instance. Proof. The correctness follows directly from Lemma 2. The expanded LP has O(Kmn(L + 1)) variables and O(Kmn(L + 1) + Kn2 (L + 1) + m) constraints. Since the underlying undirected graph of G is connected, m ≥ n − 1, and hence both quantities are O(Kmn(L
+ 1)). Using Ye’s potential-reduction algorithm [32], the LP can therefore be solved in O (Kmn(L + 1))4 L time. Path extraction takes O(Kmn2 (L+1)) time, since at most O(Kmn(L+1)) paths are extracted and each can be
processed in O(n) time. This is dominated by the LP-solving time. Thus, Algorithm 1 runs in O (Kmn(L + 1))4 L time. Algorithm 1 E XACT- I RS(G, D, L, T) 1: Solve LPRS (G, D, L) and obtain the optimal value Φ⋆L . 2: if Φ⋆L < T then 3: STOP: infeasible. 4: else 5: Extract and return P . 6: end if

Implementation and graph pruning. In the implementation, the expanded graph is pruned separately for each [0,0] commodity before constructing the LP. For commodity k , a forward BFS from the source state sk identifies all expanded states reachable from the source. A multi-source BFS from the terminal states in ΩL k on the reversed expanded graph identifies all states from which at least one terminal state is reachable. We retain only the states contained in the intersection of these two sets, together with the expanded edges between them. All other states, their incident edges, and the corresponding flow variables are removed. For each commodity, the expanded graph contains O(n2 (L+1)) states and O(mn(L+1)) edges. Thus, the two searches take O(n2 (L+1)+mn(L+1)) = O(mn(L + 1)) time. Hence, pruning the expanded graphs for all K commodities takes O(Kmn(L + 1)) time. 6. A N FPTAS FOR O RS In this section, we develop an FPTAS for solving oRS. For a minimization problem, an FPTAS returns, for any ϵ ∈ (0, 1], a feasible solution whose objective value is at most 1 + ϵ times the optimal value, in time polynomial in the input size and 1/ϵ. Accordingly, for oRS we seek a rate allocation P satisfying ∆(P) ≤ (1 + ϵ)∆oRS opt . oRS We consider the case ∆oRS (G, D, T ) = 0 and the case ∆ (G, D, T ) > 0 separately. Let G be the subgraph of 0 opt opt G with only the edges e ∈ E such that ℓ(e) = 0. Solve LPRS (G0 , D, 0) and denote its optimal objective function value by Φ⋆0 . If Φ⋆0 ≥ T, then ∆oRS opt (G, D, T) = 0 and an optimal solution to oRS(G, D, T) can be obtained by the path extraction from the flow values fk (e). If Φ⋆0 < T, then ∆oRS opt (G, D, T) > 0. We will compute a oRS (1 + ϵ)-approximation in this case. Therefore, we assume ∆opt > 0 in the rest of this section. A. Scaling and Rounding We now consider the general case where the fidelity losses may be real-valued. Let θ > 0 be a scaling parameter. For each edge e ∈ E , define the scaled loss ℓθ (e) = ⌊θℓ(e)⌋ + 1. The +1 is deliberate: it ensures that the scaled

15

loss does not underestimate θℓ(e), while introducing at most one unit of additive rounding error per edge. We have θℓ(e) ≤ ℓθ (e) ≤ θℓ(e) + 1.

For a path π , let ℓθ (π) =

(6.1)

P

e∈π ℓθ (e). Since any path in G has at most n − 1 edges, we have

θℓ(π) ≤ ℓθ (π) ≤ θℓ(π) + n − 1.

(6.2)

For any integer threshold Lθ ≥ 0, let iRSθ (G, D, Lθ , T) denote the instance with the fidelity loss ℓθ and the fidelity-loss budget Lθ . We can use Algorithm 1 to test the feasibility of this instance. Let L⋆θ be the smallest integer threshold such that iRSθ (G, D, Lθ , T) is feasible. B. Bounding the Optimal Value We show how to compute LB > 0 and UB > 0 such that LB ≤ ∆oRS opt ≤ UB and UB ≤ 4 × LB. We call LB and UB a lower bound and an upper bound of ∆oRS , respectively. opt Initial Bounds: We first show how to compute a pair of LB and UB such that UB ≤ nLB. Let 0 < α1 < α2 < · · · < αJ be the distinct positive edge-loss values, and let G(αj ) be the subgraph induced by the edges with loss at most αj . For each αj , we test whether G(αj ) can support throughput T without a path fidelity-loss constraint. To do so, we temporarily assign zero loss to every edge in G(αj ) and solve LPRS (G(αj ), D, 0). The resulting expanded graph retains the hop-count dimension, which is still needed to account for the swapping success probability. Since feasibility is monotone in αj , the smallest feasible value αj ⋆ can be found by solving O(log m) LPs using binary search. We set LB0 = αj ⋆ and UB0 = nαj ⋆ . We have LB0 ≤ ∆oRS opt ≤ (n − 1)αj ⋆ ≤ UB0 ≤ nLB0 .

(6.3)

The lower bound follows from the minimality of αj ⋆ . Indeed, if ∆oRS opt < αj ⋆ , every positive-rate path of an optimal allocation would use only edges with losses strictly smaller than αj ⋆ , contradicting the definition of αj ⋆ . For the upper bound, feasibility in G(αj ⋆ ) yields a flow that can be decomposed into simple paths. Each such path has at most n − 1 edges, each of loss at most αj ⋆ [18], [19], [30]. Approximate Testing: We use the approximate testing technique used in [18],j[19]kto tighten the bounds. For n−1 +n−1. Then T EST(∆, ζ) any ∆ > 0 and ζ ∈ (0, 1], define T EST(∆, ζ) as follows. Set θ = n−1 ∆ζ and Lθ = ζ returns YES if iRSθ (G, D, Lθ , T) is feasible, and returns NO otherwise. The scaling factor is chosen so that the maximum additive rounding error of a simple path, namely n − 1, corresponds to at most ζ∆ in the original loss scale. Thus, a scaled-feasible solution may exceed the tested threshold ∆ by at most the factor 1 + ζ . Lemma 4. For any ∆ > 0 and ζ ∈ (0, 1], the following properties hold: • If T EST (∆, ζ) = Y ES , then ∆oRS opt ≤ (1 + ζ)∆; • if T EST (∆, ζ) = N O , then ∆oRS opt > ∆. □ Proof. First, suppose that T EST(∆, ζ) = Y ES. Then there exists a feasible rate allocation P such that every positive-rate path has scaled loss at most Lθ . Hence, for every positive-rate path π in P ,   n−1 n−1 θℓ(π) ≤ ℓθ (π) ≤ Lθ = +n−1≤ + n − 1. (6.4) ζ ζ Dividing by θ = (n − 1)/(∆ζ) gives ℓ(π) ≤ ∆(1 + ζ). Therefore P is feasible for oRS with maximum fidelity loss at most (1 + ζ)∆, and so ∆oRS opt ≤ (1 + ζ)∆. Next, suppose ∆oRS ≤ ∆ , and let P ⋆ be an optimal rate allocation for oRS. Then every positive-rate path π opt in P ⋆ satisfies ℓ(π) ≤ ∆. By the scaling inequality, ℓθ (π) ≤ θℓ(π) + n − 1 ≤ θ∆ + n − 1 =

16

n−1 + n − 1. ζ

(6.5)

j k Since ℓθ (π) is an integer, we have ℓθ (π)≤ n−1 +n−1= Lθ . Thus P ⋆ is feasible, so T EST(∆, ζ) = Y ES. ζ Therefore, if T EST(∆, ζ) = N O, then ∆oRS opt > ∆. Tighten p the Bounds: Starting from LB0 and UB0 , we tighten the bounds as follows. While UBi > 4LBi , set ∆ ← LBi UBi /2. If T EST(∆, 1) = Y ES, set LBi+1 ← LBi and UBi+1 ← 2∆. Otherwise, set LBi+1 ← ∆ and UBi+1 ← UBi . By Lemma 4, both updates preserve the validity of the lower and p upper bounds. To analyze the number of iterations, define ρi = UBi /LBi . The choice ∆ = LBi UBi /2 makes the ratio between the updated upper and lower bounds the √ √ same in both branches. Indeed, if√T EST(∆, 1) = Y ES, then UBi 2∆ = ρi+1 = LB 2ρ . Otherwise, ρ = = 2ρi . Hence, in either case, ρi+1 = 2ρi . Let zi = log2 (ρi /2). i i+1 ∆ i Then zi+1 = zi /2. Since ρ0 ≤ n, we have z0 = O(log n). Therefore, after O(log log n) iterations, zi ≤ 1, which is equivalent to ρi ≤ 4. Thus, the procedure terminates with LB ≤ ∆oRS opt ≤ UB ≤ 4LB. C. Fully Polynomial Time Approximation Scheme for oRS Assume that we have computed LB and UB such that LB ≤ ∆oRS opt ≤ UB ≤ 4LB. For a given ϵ ∈ (0, 1], n−1 oRS . Thus, the maximum additive rounding error of a simple path is at set θ = n−1 . Then = ϵ LB ≤ ϵ∆ opt ϵLB θ most an ϵ-fraction of the optimal fidelity loss. The constant-factor lower bound is therefore what allows the additive rounding error introduced by scaling to be converted into a multiplicative approximation error. We can compute a rate allocation P whose total throughput is at least T and whose maximum path fidelity loss is at most (1 + ϵ)∆oRS opt . To summarize the above, the complete FPTAS-oRS is presented in Algorithm 2. Algorithm 2 FPTAS- O RS(G, D, T, ϵ) 1: Let G0 be the subgraph of G induced by the zero-loss edges. Solve LPRS (G0 , D, 0). 2: if Φ⋆0 ≥ T then 3: Extract and return the corresponding rate allocation P. 4: end if 5: Compute αj ⋆ . 6: if αj ⋆ does not exist then 7: STOP: infeasible. 8: end if 9: Set LB0 ← αj ⋆ , UB0 ← nαj ⋆ , and i ← 0. 10: while UBi > p 4LBi do 11: Set ∆ ← LBi UBi /2. 12: if T EST(∆, 1) = Y ES then 13: UBi+1 ← 2∆, LBi+1 ← LBi . 14: else 15: UBi+1 ← UBi , LBi+1 ← ∆. 16: end if 17: i ← i + 1. 18: end while 19: Set LB ← LBi and UB ← UBi . 20: Set θ ← n−1 ϵLB and Uθ ← ⌊θUB⌋ + n − 1. 21: By bisection over the integer thresholds Lθ ∈ [0, Uθ ], find the minimum feasible threshold L⋆θ for iRSθ (G, D, Lθ , T). 22: Solve iRSθ (G, D, L⋆θ , T) and extract a rate allocation P. 23: return P.

Theorem 2. Algorithm 2 correctly reports infeasibility if oRS(G, D, TP ) is infeasible. Otherwise, for any ϵ ∈ (0, 1], K oRS it returns a rate allocation P that satisfies link-capacity constraints, k=1 Rk ≥ T and ∆(P) ≤ (1 + ϵ)∆opt . Its

1 n 4 4 8 running time is bounded by O K m n log log n + ϵ4 log ϵ L , where L is the input size of the oRS instance.□ Proof. If the zero-loss test succeeds, Algorithm 2 returns an allocation P with ∆(P) = ∆oRS opt = 0, and the approximation guarantee holds trivially. Hence, in the remainder of the proof, assume ∆oRS opt > 0. If αj ⋆ does

17

not exist, then even G(αJ ), which contains all physical edges, cannot support total throughput T without any path fidelity-loss constraint. Hence, the oRS instance is infeasible. Conversely, if the oRS instance is feasible and ∆oRS opt > 0, such an αj ⋆ must exist. By the initial-bound construction and the bound-tightening procedure, we obtain LB ≤ ∆oRS opt ≤ UB ≤ 4LB. n−1 Approximation guarantee: Algorithm 2 sets θ = ϵLB . Let Uθ = ⌊θUB⌋ + n − 1. Consider an optimal rate allocation P ⋆ for oRS. For every positive-rate path π in P ⋆ , ℓ(π) ≤ ∆oRS opt ≤ UB. By the scaling inequality, ℓθ (π) ≤ θℓ(π) + n − 1 ≤ θUB + n − 1. Since ℓθ (π) is an integer, ℓθ (π) ≤ ⌊θUB⌋ + n − 1 = Uθ . Thus, iRSθ (G, D, Uθ , T) is feasible. Feasibility of iRSθ (G, D, L, T) is monotone in L. Hence, Algorithm 2 can compute the minimum feasible threshold L⋆θ using bisection with the upper bound Uθ . For every positive-rate path π in P ⋆ , ℓθ (π) ≤ θℓ(π) + n − ⋆ oRS 1 ≤ θ∆oRS opt +n−1. Since ℓθ (π) is an integer, P is feasible for the scaled instance with threshold ⌊θ∆opt ⌋+n−1. ⋆ L n−1 oRS oRS oRS θ By the minimality of L⋆θ , L⋆θ ≤ ⌊θ∆oRS opt ⌋ + n − 1 ≤ θ∆opt + n − 1. Therefore, θ ≤ ∆opt + θ = ∆opt + ϵLB ≤ oRS (1 + ϵ)∆opt . Let P be the rate allocation extracted from iRSθ (G, D, L⋆θ , T). For every positive-rate path π in P , θℓ(π) ≤ ℓθ (π) ≤ L⋆θ . It follows that L⋆θ ≤ (1 + ϵ)∆oRS (6.6) opt . θ By Lemma 2, the extracted allocation also satisfies the throughput threshold and all link-capacity constraints in (3.5). Hence, P is a (1 + ϵ)-approximation to oRS. Running time: αj ⋆ can be found by bisection using O(log m) hop-expanded-flow LP solves, which is dominated by the subsequent phases. For the bound-tightening procedure, each call to T EST(∆, 1) uses the scaled threshold
O(n), by Lemma 3, taking O K 4 m4 n8 L time.
The while-loop terminates after O(log log n) iterations. Its total running time is therefore O K 4 m4 n8 log log n L . Since UB/LB ≤ 4, we have Uθ =⌊θUB⌋+n−1= O(n/ϵ). By monotonicity, L⋆θ can be
found by bisection using O(log(n/ϵ)) scaled instances. By Lemma 3, the running time is O K
4 m
4 n8 ϵ14 log nϵ L . Combining all above, the total running time is bounded by O K 4 m4 n8 log log n + ϵ14 log nϵ L . ∆(P) ≤

7. FPTAS FOR O RS- M RC In this section, we present the FPTAS scheme to solve oRS-mRC. A. Integer RS-mRC Let ∆mRC opt denote the optimal value of oRS-mRC(G, D, T, Tmin ). We first consider the integer-loss version of RS-mRC. Let iRS-mRC(G, D, L, T, Tmin ) denote an RS-mRC instance in which ℓ(e) ∈ Z≥0 for every e ∈ E and L is an integer fidelity-loss threshold. P The problem asks whether there exists a rate allocation P that satisfies the link-capacity constraints, ∆(P) ≤ L, K k=1 Rk ≥ T, and Rk ≥ Tmin , k = 1, 2, . . . , K . For a fixed integer threshold L, we construct the hop-fidelity expanded graph GD L as in Section 5. We then solve the following LP: LPmRC (G, D, L, Tmin ) :

max

ΦmRC = L

K X

Rk (f )

(7.1a)

k=1

s.t.

Rk (f ) ≥ Tmin ,

k = 1, 2, . . . , K,

Constraints (5.1b)–(5.1e).

(7.1b) (7.1c)

mRC ⋆

Here, Rk (f ) is the delivered throughput of commodity k , as defined in (5.2). Let ΦL value of LPmRC (G, D, L, Tmin ).

denote the optimal

Lemma 5.
An instance iRS-mRC(G, D, L, T, Tmin ) is feasible if and only if LPmRC (G, D, L, Tmin ) is feasible ⋆ and ΦmRC ≥ T. Moreover, whenever these conditions hold, a feasible rate allocation can be extracted from L an optimal LP solution.

18

Proof. By Lemma 2, the expanded-flow constraints characterize exactly the rate allocations whose positive-rate paths have fidelity loss at most L and that satisfy all link-capacity constraints. By the path-extraction result of Lemma 2, the extracted rate allocation satisfies Rk (P) = Rk (f ) for every k ∈ [K]. Hence, constraints (7.1b) are preserved by the extraction procedure, and every commodity satisfies Rk (P) ≥ Tmin . Therefore, such an allocation satisfies
⋆ the RS-mRC requirements if and only if the LP is feasible and its optimal total throughput satisfies ΦmRC ≥ T. The rate allocation is obtained using the same flow-decomposition procedure as in L Lemma 2. We summarize the exact algorithm for iRS-mRC in Algorithm 3. Algorithm 3 E XACT- I RS- M RC(G, D, L, T, Tmin ) 1: Solve LPmRC (G, D, L, Tmin ). 2: if LPmRC (G, D, L, Tmin ) is infeasible then 3: STOP: infeasible. 4: end if
⋆ 5: Let ΦmRC be its optimal value. L

⋆

6: if ΦmRC < T then L 7: STOP: infeasible. 8: else 9: Extract and return P . 10: end if

B. FPTAS for oRS-mRC With the exact algorithm for iRS-mRC, we can solve oRS-mRC approximately as follows. Scaling and Rounding: We use the same scaling and rounding scheme as in Section 6. For any integer scaled threshold Lθ ≥ 0, let iRS-mRCθ (G, D, Lθ , T, Tmin ) denote the corresponding integer-loss instance under the scaled losses ℓθ . Its feasibility can be tested using Algorithm 3. Therefore, all scaling inequalities established for FPTAS-oRS continue to hold without modification. We first test feasibility on the subgraph induced by the zero-loss edges, using the same flow LP with the additional constraints Rk (f ) ≥ Tmin for all k . If this LP is feasible and its optimal objective value is at least T, then ∆mRC opt = 0, and an optimal rate allocation can be extracted. Otherwise, either the oRS-mRC instance is infeasible or, if it is feasible, ∆mRC opt > 0. The initial-bound search below distinguishes these two cases. Initial Bounds: Let 0 < α1 < α2 < · · · < αJ be the distinct positive edge-loss values, and let G(αj ) be the subgraph induced by the edges with loss at most αj . For each αj , temporarily assign zero loss to every edge of G(αj ) and solve LPmRC (G(αj ), D, 0, Tmin ). We say that αj is feasible if this LP is feasible and its optimal objective value is at least T. Let αj ⋆ be the smallest feasible value, which can be found by binary search. If αj ⋆ does not exist, then the oRS-mRC instance is infeasible even without a path fidelity-loss constraint. Otherwise, since the zero-loss case has already been excluded, ∆mRC opt > 0. ⋆ ⋆ Set LB0 = αj and UB0 = nαj . By the minimality of αj ⋆ , αj ⋆ ≤ ∆mRC opt . Conversely, feasibility of G(αj ⋆ ) yields a rate allocation satisfying the total-throughput and minimum-rate requirements using simple paths with at most n − 1 edges, each having loss at most αj ⋆ . Hence, ∆mRC opt ≤ (n − 1)αj ⋆ . Therefore, LB0 = αj ⋆ ≤ ∆mRC opt ≤ (n − 1)αj ⋆ < UB0 = nαj ⋆ = nLB0 .

(7.2)

Approximate Testing: For any ∆ > 0 and ζ ∈ (0, 1], define T EST- M RC(∆, ζ) as follows. Set θ = n−1 ∆ζ and j k n−1 Lθ = + n − 1. Then T EST- M RC(∆, ζ) returns Y ES if iRS-mRCθ (G, D, Lθ , T, Tmin ) is feasible, and ζ returns N O otherwise. The feasibility test is performed using Algorithm 3. Lemma 6. For any ∆ > 0 and ζ ∈ (0, 1], the following properties hold:

19

1) If T EST- M RC(∆, ζ) = Y ES, then ∆mRC opt ≤ (1 + ζ)∆. mRC 2) If T EST- M RC(∆, ζ) = N O, then ∆opt > ∆. Proof. The scaling inequalities (6.1)–(6.2) remain unchanged. If T EST- M RC(∆, ζ) returns Y ES, the extracted allocation satisfies both the total-throughput and minimum-rate requirements, while its original maximum path loss is at most (1 + ζ)∆. Conversely, if ∆mRC opt ≤ ∆, an optimal oRS-mRC allocation remains feasible under the scaled threshold used by T EST- M RC, by the same scaling argument as in Lemma 4. The additional minimum-rate constraints affect only the commodity rates and therefore do not alter the loss-scaling argument. Tighten the Bounds: Starting from LBq 0 and UB0 , we tighten the bounds using the same procedure as for FPTASLBi UBi oRS. While UBi > 4LBi , set ∆ = . If T EST- M RC(∆, 1) = Y ES, set LBi+1 = LBi , UBi+1 = 2∆. 2 Otherwise, set LBi+1 = ∆, UBi+1 = UBi . By Lemma 6, all updated lower and upper bounds remain valid. After O(log log n) iterations, we obtain LB ≤ ∆mRC opt ≤ UB ≤ 4LB. Final Scaling and Threshold Search: Assume that the bound-tightening procedure has produced LB and UB n−1 ⋆ satisfying LB ≤ ∆mRC opt ≤ UB ≤ 4LB. For a given ϵ > 0, set θ = ϵLB and Uθ = ⌊θ UB⌋ + n − 1. Let Lθ be the smallest integer threshold such that iRS-mRCθ (G, D, L⋆θ , T, Tmin ) is feasible. Such a threshold exists. Indeed, let P ⋆ be an optimal rate allocation for oRS-mRC. For every positive-rate path π ∈ P ⋆ , ℓ(π) ≤ ∆mRC opt ≤ UB. Therefore, by the scaling inequality, ℓθ (π) ≤ θℓ(π) + n − 1 ≤ θ UB + n − 1. Since ℓθ (π) is an integer, ℓθ (π) ≤ ⌊θUB⌋ + n − 1 = Uθ . Hence, iRS-mRCθ (G, D, Uθ , T, Tmin ) is feasible. Since feasibility is monotone in the scaled threshold, L⋆θ can be found by bisection search. We then solve the scaled instance at L⋆θ and extract its rate allocation. We give the FPTAS-oRS-mRC in Algorithm 4. Theorem 3. Algorithm 4 correctly reports infeasibility if the oRS-mRC instance is P infeasible. Otherwise, for any ϵ ∈ (0, 1], it returns a rate allocation P satisfying the link-capacity constraints, K k=1 Rk (P) ≥ T, Rk (P)

≥ 4 m4 n8 log log n + 1 log n L , . Its running time is O K Tmin , k = 1, 2, . . . , K, and ∆(P) ≤ (1 + ϵ)∆mRC opt ϵ4 ϵ where L is the input size of the oRS-mRC instance. Proof. If the zero-loss test succeeds, Algorithm 4 returns a feasible rate allocation P with ∆(P) = ∆mRC opt = 0, and the approximation guarantee holds trivially. If αj ⋆ does not exist, then even the full physical graph cannot satisfy the total-throughput and minimum-rate requirements without any path fidelity-loss constraint. Hence, the oRS-mRC instance is infeasible, and Algorithm 4 correctly reports infeasibility. Otherwise, ∆mRC > 0. opt Algorithm 4 then follows the same initial-bound, bound-tightening, scaling, and final threshold-search arguments as Algorithm 2. The additional constraints Rk (f ) ≥ Tmin , k ∈ [K], affect only the commodity rates and do not alter the loss-scaling arguments. By Lemma 5, the extracted allocation satisfies the total-throughput and minimumrate requirements. Therefore, the same approximation argument as in Theorem 2 gives ∆(P) ≤ (1 + ϵ)∆mRC opt . PK Hence, k=1 Rk (P) ≥ T and Rk (P) ≥ Tmin , k ∈ [K], and all link-capacity constraints are satisfied. Running time: Compared with LPRS (G, D, L), LPmRC (G, D, L, Tmin ) adds exactly K linear constraints and no flow variables. Hence, Algorithm 3 has the same asymptotic running time as Algorithm 1. The number and sizes of the fixed-threshold oracle calls in the zero-loss test, initial-bound search, bound-tightening phase, and final bisection are asymptotically

the same as those in Algorithm 2. Therefore, the total running time is O K 4 m4 n8 log log n + ϵ14 log nϵ L .

20

Algorithm 4 FPTAS- O RS- M RC(G, D, T, Tmin , ϵ) 1: Let G0 be the subgraph induced by the zero-loss edges. 2: Solve LPmRC (G0 , D, 0, Tmin ). 3: if LPmRC (G0 , D, 0, Tmin ) is feasible and (ΦmRC )⋆ ≥ T then 0 4: Extract and return the corresponding allocation P . 5: end if 6: Compute αj ⋆ . 7: if αj ⋆ does not exist then 8: STOP: infeasible. 9: end if 10: Set LB0 ← αj ⋆ , UB0 ← nαj ⋆ , and i ← 0. 11: while UBi > p 4LBi do 12: Set ∆ ← LBi UBi /2. 13: if T EST- M RC(∆, 1) = Y ES then 14: Set LBi+1 ← LBi and UBi+1 ← 2∆. 15: else 16: Set LBi+1 ← ∆ and UBi+1 ← UBi . 17: end if 18: Set i ← i + 1. 19: end while 20: Set LB ← LBi and UB ← UBi . 21: Set θ ← n−1 ϵLB and Uθ ← ⌊θ UB⌋ + n − 1. 22: By bisection over the integer thresholds Lθ ∈ [0, Uθ ], find

the minimum feasible threshold L⋆θ for

iRS-mRCθ (G, D, Lθ , T, Tmin ). 23: Solve the scaled instance at L⋆θ and extract the allocation P . 24: return P .

8. A N FPTAS FOR O M M FAIR In this section, we present the FPTAS framework to solve oMmFair. A. Integer MmFair We first consider the fixed-threshold integer-loss problem iMmFair(G, D, L, η), where ℓ(e) ∈ Z≥0 for every e ∈ E and L is an integer fidelity-loss threshold. The problem asks whether there exists a rate allocation P = (P1 , P2 , . . . , PK ) satisfying the link-capacity constraints, ∆(P) ≤ L, and R(P)↑ ⪰lex η . By Lemma 2, the expanded-flow constraints exactly characterize the rate allocations satisfying the link-capacity constraints and the fidelity-loss threshold L. Therefore, to solve iMmFair, it suffices to compute the lexicographically maximum sorted commodity-throughput vector achievable under these expanded-flow constraints and compare it with η . We compute this vector by progressively fixing bottleneck commodities, following the leximin optimization approach in [15], [20]. Let Q be the set of commodities whose throughputs have already been fixed, and let U be the set of unfixed commodities. For each k ∈ Q, let γk denote its fixed throughput. Initially, Q = ∅ and U = [K]. We first solve LPfair (G, D, L, Q) :

max λ s.t.

21

(8.1a)

Rk (f ) = γk ,

∀k ∈ Q,

(8.1b)

Rk (f ) ≥ λ,

∀k ∈ U,

(8.1c)

Constraints (5.1b)–(5.1e).

(8.1d)

Let λopt (Q) denote its optimal value. Thus, λopt (Q) is the maximum common throughput that can be guaranteed to all currently unfixed commodities, while preserving the throughputs of the fixed commodities. To determine which unfixed commodities must remain at this common throughput, for every k ∈ U , we solve LPfair (G, D, L, Q, k) :

max

Rk (f )

s.t.

Rj (f ) = γj ,

(8.2a) ∀j ∈ Q,

Rj (f ) ≥ λopt (Q),

∀j ∈ U,

Constraints (5.1b)–(5.1e).

(8.2b) (8.2c) (8.2d)

Let λopt (Q, k) be the optimal value of LPfair (G, D, L, Q, k). If λopt (Q, k) = λopt (Q), then commodity k is a bottleneck commodity. We fix the throughput of this commodity at λopt (Q) and add it to Q (removing it from U ). Since at least one commodity is fixed in each iteration, after at most K iterations, U = ∅ and all commodity throughputs have been fixed. We then obtain the lexicographically maximum feasible vector and extract the allocation P from the final flow solution of LPfair (G, D, L, Q) in the last iteration. We give Algorithm 5 to solve iMmFair by computing the lexicographically maximum commodity-throughput vector R↑ achievable under the integer loss threshold L. In each iteration, we define B as the bottleneck set: B(Q) = {k ∈ U : λopt (Q, k) = λopt (Q)}. Algorithm 5 E XACT- I M M FAIR(G, D, L, η) 1: Construct the expanded graph GD L . Set β ← (), Q ← ∅, and U ← {1, 2, . . . , K}. 2: while U ̸= ∅ do 3: Compute λopt (Q) by solving LPfair (G, D, L, Q) and obtain an optimal flow solution f ⋆ . 4: for each k ∈ U do 5: Compute λopt (Q, k) by solving LPfair (G, D, L, Q, k). 6: end for 7: Set B ← ∅. 8: for each k ∈ U do 9: if λopt (Q, k) = λopt (Q) then 10: B ← B ∪ {k}. 11: end if 12: end for 13: for each k ∈ B do 14: γk ← λopt (Q). 15: end for 16: Append |B| copies of λopt (Q) to β. 17: Set Q ← Q ∪ B and U ← U \ B. 18: end while 19: if β ≺lex η then 20: STOP: infeasible. 21: end if 22: Extract P from the flow solution f ⋆ obtained in the final iteration; by Lemma 2, R(P)↑ = β. 23: return P.

Lemma 7. For any fixed integer fidelity-loss threshold L, Algorithm 5 computes the lexicographically maximum sorted feasible commodity-throughput vector β . Consequently, it returns a rate allocation P if and only if iMmFair(G, D, L, η) is feasible. Whenever it returns P , the extracted rate allocation P satisfies ∆(P) ≤ L and R(P)↑ = β ⪰lex η. Moreover, the algorithm terminates after at most K iterations and solves O(K 2 ) expanded-flow LPs. □

22

Proof. Consider an iteration with fixed commodity set Q and unfixed commodity set U . By definition, λopt (Q) is the largest common throughput that can be simultaneously guaranteed to all commodities in U , while preserving Rk (f ) = γk for every k ∈ Q. We first show that the bottleneck set B is nonempty. Suppose, to the contrary, that λopt (Q, k) > λopt (Q), ∀k ∈ U. For each k ∈ U , let f (k) be an optimal solution of LPfair (G, D, L, Q, k). Every such solution satisfies Rj (f (k) )P≥ λopt (Q), ∀j ∈ U, and additionally Rk (f (k) ) > λopt (Q). Since all constraints are linear, the average f¯ = |U1 | k∈U f (k) is feasible and satisfies Rj (f¯) > λopt (Q), ∀j ∈ U . This contradicts the optimality of λopt (Q) in LPfair (G, D, L, Q). Hence, B ̸= ∅. For every k ∈ B, λopt (Q, k) = λopt (Q). Thus, among all feasible solutions satisfying Rj (f ) ≥ λopt (Q), ∀j ∈ U, commodity k cannot have throughput strictly greater than λopt (Q). Therefore, every such solution satisfies Rk (f ) = λopt (Q), ∀k ∈ B. Hence, all commodities in B can be fixed simultaneously at λopt (Q). Moreover, an optimal solution of LPfair (G, D, L, Q) remains feasible after this update. Hence, the common throughput computed in the next iteration cannot be smaller than the current value, and the values appended to β are nondecreasing. We next establish lexicographic optimality. At each iteration, λopt (Q) is the largest value that all currently unfixed commodities can simultaneously attain. Thus, no feasible throughput vector agreeing with the previously fixed entries can have its next smallest entry larger than λopt (Q). Furthermore, every commodity in B must equal this value before any remaining commodity can be increased. Therefore, the commodities fixed in the current iteration form the next block of the lexicographically maximum sorted feasible throughput vector. Applying this argument inductively over all iterations shows that the final vector β is the lexicographically maximum sorted feasible throughput vector. In the final iteration, we must have B = U, since the update U ← U \ B makes U empty. Hence, in the final optimal flow solution f ⋆ , every commodity fixed in an earlier iteration has throughput equal to its prescribed value γk , while every commodity remaining in the final iteration has throughput λopt (Q). Therefore, sorting R1 (f ⋆ ), R2 (f ⋆ ), . . . , RK (f ⋆ ) in nondecreasing order gives β. By the path-extraction result of Lemma 2, Rk (P) = Rk (f ⋆ ), k ∈ [K]. Hence, R(P)↑ = β. Since β is the lexicographically maximum sorted feasible throughput vector, the iMmFair instance is feasible if and only if β ⪰lex η. If β ≺lex η, Algorithm 5 correctly reports infeasibility. Otherwise, the extracted allocation P satisfies R(P)↑ = β ⪰lex η. By Lemma 2, P also satisfies the link-capacity constraints and ∆(P) ≤ L. Finally, since B ̸= ∅ in every iteration, at least one commodity is fixed per iteration, so the algorithm terminates after at most K iterations. With |U | unfixed commodities, one instance of LPfair (G, D, L, Q) of Pand |U | instances 2 ). LPfair (G, D, L, Q, k) are solved. Therefore, the total number of expanded-flow LPs is K + K i = O(K i=1 B. FPTAS for oMmFair Algorithm 5 serves as an exact feasibility test for iMmFair under any fixed integer-loss threshold. We now use this exact test in the same scaling framework as FPTAS-oRS to solve oMmFair. Scaling and Rounding: We use the same scaling and rounding scheme as in Section 6. For any integer scaled threshold Lθ ≥ 0, let iMmFairθ (G, D, Lθ , η) denote the corresponding integer-loss instance under the scaled losses ℓθ . Its feasibility can be tested using Algorithm 5. Therefore, all scaling inequalities established for FPTAS-oRS continue to hold without modification. We first test the zero-loss case. Let G0 be the subgraph induced by the edges with zero loss, and run E XACT- I M M FAIR(G0 , D, 0, η). If it returns a rate allocation P , then ∆fair opt = 0, and P is optimal. Otherwise, either the oMmFair instance is infeasible or, if it is feasible, ∆fair > 0. The initial-bound search below distinguishes opt these two cases. Initial Bounds: Let 0 < α1 < α2 < · · · < αJ be the distinct positive edge-loss values, and let G(αj ) be the subgraph induced by the edges whose losses are at most αj . For each αj , temporarily assign zero loss to every edge of G(αj ) and run E XACT- I M M FAIR(G(αj ), D, 0, η). We say that αj is feasible if the algorithm returns a rate allocation. Let αj ⋆ be the smallest feasible value, which can be found by binary search.

23

If αj ⋆ does not exist, then oMmFair(G, D, η) is infeasible even without a path fidelity-loss constraint. Otherwise, since the zero-loss case has already been excluded, ∆fair opt > 0. Set LB0 = αj ⋆ and UB0 = nαj ⋆ . By the minimality of αj ⋆ , αj ⋆ ≤ ∆fair opt . Conversely, feasibility of G(αj ⋆ ) ↑ yields a rate allocation P = (P1 , P2 , . . . , PK ) satisfying R(P) ⪰lex η, using simple paths with at most n − 1 edges, each having loss at most αj ⋆ . Hence, ∆fair opt ≤ (n − 1)αj ⋆ . Therefore, LB0 = αj ⋆ ≤ ∆fair opt ≤ (n − 1)αj ⋆ < UB0 = nαj ⋆ = nLB0 .

(8.3)

Approximate Testing: For any ∆ > 0 and ζ ∈ (0, 1], define FAIR -T EST(∆, ζ) as follows. Set θ = n−1 ∆ζ and j k Lθ = n−1 + n − 1. Then apply Algorithm 5 to iMmFairθ (G, D, Lθ , η). The procedure returns Y ES if the ζ algorithm returns a rate allocation, and returns N O otherwise. Lemma 8. For any ∆ > 0 and ζ ∈ (0, 1], FAIR -T EST(∆, ζ) satisfies the following: if it returns Y ES, then fair ∆fair opt ≤ (1 + ζ)∆; if it returns N O , then ∆opt > ∆. Proof. The scaling inequalities (6.1)–(6.2) remain unchanged. If FAIR -T EST(∆, ζ) returns Y ES, Algorithm 5 finds a feasible scaled solution satisfying the fairness threshold. By Lemma 2, path extraction preserves every commodity throughput, and hence preserves the lexicographic fairness condition. The same scaling argument as in Lemma 4 then gives ∆fair opt ≤ (1 + ζ)∆. Conversely, suppose ∆fair opt ≤ ∆. An optimal oMmFair allocation is feasible under loss threshold ∆, and by the scaling inequalities, every positive-rate path in this allocation is feasible under the scaled threshold used by FAIR -T EST(∆, ζ). Since Algorithm 5 is an exact fixed-threshold fairness test, FAIR -T EST(∆, ζ) must return Y ES. Therefore, if it returns N O, we must have ∆fair opt > ∆. Tighten the Bounds: Starting from these bounds, we use FAIR -T EST(∆, 1) to perform the same bound-tightening procedure as in Algorithm 2. After O(log log n) iterations, we obtain LB ≤ ∆fair opt ≤ UB ≤ 4LB. Final Scaling and Threshold Search: After the bound-tightening procedure, we have LB ≤ ∆fair opt ≤ UB ≤ 4LB. fair ≤ UB, the scaled version of For a given ϵ > 0, set θ = n−1 and U = ⌊θ UB ⌋+n−1. As in Section 6, since ∆ θ opt ϵLB an optimal oMmFair allocation is feasible under the threshold Uθ . Hence, the minimum feasible scaled threshold can be found by bisection over [0, Uθ ]. The complete algorithm FPTAS-oMmFair is given in Algorithm 6. Theorem 4. Algorithm 6 correctly reports infeasibility if the oMmFair instance is infeasible. Otherwise, for any ϵ ∈ (0, 1], it returns a rate allocation P satisfying the link-capacity constraints, R(P)↑ ⪰lex η, and ∆(P) ≤

−4 6 4 8 fair (1 + ϵ)∆opt . The running time is O K m n log log n + ϵ log(n/ϵ) L , where L is the input size of the oMmFair instance. Proof. If the zero-loss test succeeds, Algorithm 6 returns a feasible rate allocation P with ∆(P) = ∆fair opt = 0, and ⋆ the approximation guarantee holds trivially. If αj does not exist, then even the full physical graph cannot satisfy the fairness requirement R(P)↑ ⪰lex η without any path fidelity-loss constraint. Hence, the oMmFair instance is infeasible, and Algorithm 6 correctly reports infeasibility. Otherwise, ∆fair opt > 0. By Lemma 7, Algorithm 5 is an exact feasibility oracle for iMmFair under any fixed integer-loss threshold. By Lemma 8, the same scaling and bound-tightening arguments as in Theorem 2 apply. Therefore, the returned allocation satisfies R(P)↑ ⪰lex η and ∆(P) ≤ (1 + ϵ)∆fair opt , together with all link-capacity constraints. Running time: Each expanded-flow LP solved by Algorithm 5 has the same asymptotic size as the fixedthreshold LP for iRS, and Algorithm 5 requires O(K 2 ) such LP solves. The number and sizes of the fixedthreshold oracle calls in the zero-loss test, initial-bound search, bound-tightening phase, and final bisection are 6 4 8 asymptotically

the same as those in Algorithm 2. Hence, the total running time is O K m n log log n + −4 ϵ log(n/ϵ) L . The proposed framework can also be used in a more general setting where different commodities may have different fidelity requirements. This extension is discussed in Appendix B.

24

Algorithm 6 FPTAS- O M M FAIR(G, D, η, ϵ) 1: Let G0 be the subgraph induced by the zero-loss edges. 2: Run E XACT- I M M FAIR(G0 , D, 0, η). 3: if it returns a rate allocation P then 4: return P. 5: end if 6: Compute the smallest feasible edge-loss threshold αj ⋆ . 7: if αj ⋆ does not exist then 8: STOP: infeasible. 9: end if 10: Set LB0 ← αj ⋆ , UB0 ← nαj ⋆ , and i ← 0. 11: while UBi > p 4LBi do 12: Set ∆ ← LBi UBi /2. 13: if FAIR -T EST(∆, 1) = Y ES then 14: Set LBi+1 ← LBi and UBi+1 ← 2∆. 15: else 16: Set LBi+1 ← ∆ and UBi+1 ← UBi . 17: end if 18: Set i ← i + 1. 19: end while 20: Set LB ← LBi and UB ← UBi . 21: Set θ ← n−1 ϵLB and Uθ ← ⌊θUB⌋ + n − 1. 22: By bisection over the integer thresholds Lθ ∈ [0, Uθ ], find the minimum feasible threshold L⋆θ for iMmFairθ (G, D, Lθ , η). 23: Apply Algorithm 5 to iMmFairθ (G, D, L⋆θ , η) and obtain its rate allocation P. 24: return P.

9. P ERFORMANCE E VALUATION We evaluate the proposed schemes on a machine running Ubuntu 26.04 LTS, equipped with a 12th Gen Intel Core i9-12900 processor (16 cores, up to 5.1 GHz) and 128 GB RAM. All LPs were solved using Gurobi Optimizer 13.0.2. For each network size n, we generate five Erdős–Rényi network topologies with expected degree 6. Each undirected physical link is independently assigned a capacity uniformly sampled from [20, 200] and a Werner parameter uniformly sampled from [0.9, 1]. The swapping success probability is set as q = 0.8. For each topology, we generate 10 independent demand sets, each containing K = 4 random commodities.

Fig. 5: Mean running time versus the number of nodes for FPTAS algorithms with ϵ = 0.0625.

25

Fig. 6: Mean running time versus 1/ϵ for different network sizes.

We test three objectives: oRS, oRS-mRC, and oMmFair. The approximation parameter is varied over ϵ ∈ {1, 0.5, 0.25, 0.125, 0.0625}. The target rate is set to T = 0.5Tmax , where Tmax is the maximum total throughput achievable without fidelity constraints. For oRS-mRC, Tmin is set to 0.5T /K . For oMmFair, we set the fairnessT (0.60, 0.65, 0.70, 0.75). threshold vector to η = K Fig. 5 shows the mean running time as the network size increases from n = 20 to 50 under the most accurate tested setting, ϵ = 0.0625. FPTAS-oRS completes within 50 s when n = 50, whereas FPTAS-oMmFair requires more time. FPTAS-oRS-mRC generally requires more computation time than FPTAS-oRS, as its feasibility LPs include additional per-commodity minimum-rate constraints. Fig. 6 reports the mean running time as a function of 1/ϵ for different network sizes. The running time tends to increase with 1/ϵ but less than proportionally over the tested range. The reason is that as 1/ϵ increases, the scaled expanded graph contains more candidate states, while many additional states are pruned: expanded states that are unreachable from the source or cannot reach the destination are removed, together with their incident expanded edges and flow variables. 10. C ONCLUSION In this paper, we studied multi-pair rate allocation in quantum networks subject to both throughput and fidelity considerations, where the links may have different fidelity values. We studied three problems: rate sum, rate sum subject to minimum-rate constraints, and max-min fairness. Our work extends [5], which studies rate sum under the assumption that all links have the same fidelity. We proved that all three problems are NP-hard, even for a single-pair case. We then studied optimization versions of the problems, and designed fully polynomial-time approximation schemes for each of them. While our approximation schemes build on the scaling-and-rounding and approximate-testing techniques used in earlier papers [18], [30], we made nontrivial extensions of these techniques to capture the properties of quantum networks. We implemented our approximation schemes and tested them on randomly generated test cases. Our evaluation results demonstrate the effectiveness of our schemes. A PPENDIX A: P ROOF OF L EMMA 1 Proof. From (4.7), we have Wopt = e−∆opt , Fopt =

1 + 3Wopt 1 ≥ . 4 4

(A.1)

1 + 3W (P) . 4

(A.2)

From (4.8), we have W (P) = e−∆(P) , F (P) =

26

Therefore, inequality (4.9) implies Wopt − W (P) = e−∆opt − e−∆(P) −∆opt

≤e

−∆opt

=e

−e

(A.3)

−(1+ϵ)∆opt

(A.4)

−ϵ∆opt

(A.5)

1−e

≤ ϵ∆opt e−∆opt (A.6) ϵ ≤ , (A.7) e where (A.4) follows from (4.9), (A.6) follows from 1 − e−x ≤ x for x ≥ 0, and (A.7) follows from xe−x ≤ 1/e for x ≥ 0. Therefore, we have 1 + 3Wopt 1 + 3W (P) − 4 4 3 = (Wopt − W (P)) 4 3ϵ ≤ . 4e

Fopt − F (P) =

(A.8) (A.9) (A.10)

Moreover, Fopt ≥ 1/4. Therefore, Fopt − F (P) ≤

3ϵ Fopt ≤ δFopt . e

(A.11)

Therefore, we have F (P) ≥ (1 − δ)Fopt .

(A.12) □

This completes the proof of Lemma 1. A PPENDIX B: E XTENSION

The decision problems RS, RS-mRC, and MmFair can be extended to the setting where different commodities have different fidelity requirements. This extension also covers the rate-sum setting of Chakraborty et al. [5], in which different commodities may have different end-to-end fidelity requirements while the physical links have identical fidelity. Hence, their rate-sum setting can be viewed as a special case of the commodity-specific framework considered here. Suppose commodity k has a prescribed Werner-parameter threshold Wk . Let W0 = mink∈[K] Wk be a common reference threshold. For each commodity k , introduce a new virtual source s′k and a virtual edge e′k = (s′k , sk ) W0 with Werner parameter w(e e ′k ) = W . Since W0 ≤ Wk , we have w(e e ′k ) ∈ (0, 1]. The original demand (sk , tk ) is k ′ replaced by (sk , tk ). e = (Ve , E, e e e = E∪ Let G c, w, e q) denote the augmented network, where Ve = V ∪ {s′1 , s′2 , . . . , s′K } and E ′ ′ ′ c(e) = c(e) and w(e) e = w(e). For every virtual edge e′k , {e1 , e2 , . . . , eP K }. For every physical edge e ∈ E , set e ′ ′ set e c(ek ) = e∈E c(e). Every unit of flow traversing ek must subsequently traverse at least one P physical edge, so the flow on e′k cannot exceed the sum of the loads on all physical edges, which is at most e∈E c(e). Thus, the virtual edge does not create an additional bottleneck. Moreover, this capacity has a binary representation of polynomial length in the input size. e = {(s′ , tk ) : k ∈ [K]}. For any sk –tk path π in the original network, let The augmented commodity set is D k π ek = e′k ◦ π denote the corresponding s′k –tk path in the augmented network. Then W0 f (π W ek ) = w(e e ′k )W (π) = W (π). Wk

27

(B.1)

Therefore, f (π W ek ) ≥ W0

⇐⇒

W (π) ≥ Wk .

(B.2)

Equivalently, let ∆k = − ln Wk and ∆0 = − ln W0 . The loss of the virtual edge is e ′ ) = − ln W0 = ∆0 − ∆k . ℓ(e k Wk

(B.3)

eπ ℓ( ek ) = ℓ(π) + ∆0 − ∆k ,

(B.4)

Hence,

and consequently, eπ ℓ( ek ) ≤ ∆0

⇐⇒

ℓ(π) ≤ ∆k .

(B.5)

Thus, the commodity-specific fidelity requirements in the original network are equivalent to the common fidelity requirement W0 in the augmented network. Integer-Loss Formulation for RS: We next describe the corresponding fixed-threshold formulation for the integer-loss version of RS. Suppose the physical edge losses and ∆k , k ∈ [K], are nonnegative integers. Then e ′ ) = ∆0 − ∆k is also a nonnegative integer. For the transformed decision instance, set L = ∆0 . ℓ(e k An original simple path contains at most n − 1 physical edges. Therefore, its corresponding augmented path consists of one virtual edge followed by at most n − 1 physical edges and hence contains at most n edges. e De = (Ve De , E e De ) with Accordingly, construct the augmented hop-fidelity expanded graph G L L L n o e (B.6) VeLD = u[h,d] : u ∈ Ve , 0 ≤ h ≤ n, 0 ≤ d ≤ L , and o
e e e 0 ≤ h < n, 0 ≤ d ≤ L − ℓ(e) . (B.7) u[h,d] , v [h+1,d+ℓ(e)] : e = (u, v) ∈ E, n o e L = t[h,d] : 2 ≤ h ≤ n, 0 ≤ d ≤ L . The lower bound h ≥ 2 For commodity k , define the terminal-state set Ω k k follows because every augmented path contains one virtual edge followed by at least one physical edge. The virtual edge is introduced only for the transformation and does not represent an additional physical swapping operation. Hence, its additional hop must be compensated when computing the delivered throughput. For each commodity k , define eLDe = E

n

ek (f ) = q −1 R

n X L X

q h−1

h=2 d=0

(µ,t

X

[h,d] k

[h,d]

fk (µ, tk

).

(B.8)

e eD )∈E L

Indeed, if an original physical path has r hops and carries elementary-pair generation flow x, its delivered rate is q r−1 x. The corresponding augmented path has r + 1 hops and would contribute q r x under the standard expanded-flow objective. The factor q −1 restores the original delivered rate, since q −1 q r x = q r−1 x.

28

The fixed-threshold integer-loss formulation for the commodity-specific version of RS is eL = max Φ

K X

ek (f ) R

(B.9a)

k=1

s.t.

X

fk (µ, ν) =

e eD (µ,ν)∈E L

X

fk (ν, ξ),

e eD (ν,ξ)∈E L

  e eL , ∀ν ∈ VeLD \ {(s′k )[0,0] } ∪ Ω k ℓ(e) K n−1 X X L− X e

∀k ∈ [K],

(B.9b)

  e fk u[h,d] , v [h+1,d+ℓ(e)] ≤ e c(e),

k=1 h=0 d=0

e ≤ L, e : ℓ(e) ∀e = (u, v) ∈ E fk (µ, ν) = 0, fk (µ, ν) ≥ 0,

eLDe , ∀(µ, ν) ∈ E ∀k ∈ [K],

(B.9c) e L, ∀µ ∈ Ω k

eLDe . ∀(µ, ν) ∈ E

∀k ∈ [K],

(B.9d) (B.9e)

By the same argument as in Lemma 2, together with the compensated throughput definition in (B.8), the e ⋆ ≥ T. Thus, LP (B.9) plays the same role for the commodity-specific RS instance is feasible if and only if Φ L commodity-specific version of RS as LP (5.1) does for the common-threshold version. Path Extraction: The same path-decomposition procedure as in Section 5 can be used, with an adjustment to [h,d] the delivered rate. Consider an extracted augmented expanded path ending at tk with bottleneck flow value b(π b). After dropping the hop-loss indices and removing the first virtual edge, we obtain an sk –tk physical walk in the original network. After cycle removal, let π denote the resulting simple physical path. The delivered rate assigned to π is rπ = q −1 q h−1 b(π b) = q h−2 b(π b). This is exactly the throughput contribution of the augmented path in (B.8). Before cycle removal, the corresponding physical walk has h − 1 physical edges. If cycle removal reduces its hop count to h′ ≤ h − 1, then the elementary-pair generation rate required on each ′ b) ≤ b(π b), because q ∈ (0, 1] and h − h′ − 1 ≥ 0. edge of the resulting physical path is qhr′π−1 = q h−h −1 b(π Hence, projection and cycle removal do not violate the link-capacity constraints. Furthermore, removing the virtual edge and deleting cycles cannot increase the physical path loss, so the corresponding commodity-specific fidelity requirement is also preserved. ek (f ) ≥ Tmin , k ∈ [K]. RS-mRC and MmFair: For RS-mRC, we use LP (B.9) with the additional constraints R The commodity-specific RS-mRC instance is feasible if this modified LP is feasible and its optimal objective value is at least T. For MmFair, LP (B.9) itself is not used as the fairness objective. Instead, we use the same augmented ek (f ) in the fairness formulations of expanded-flow constraints and the compensated commodity throughputs R e e e D, e L, Q, k) is replaced by Section 8. Specifically, every occurrence of Rk (f ) in LPfair (G, D, L, Q) and LPfair (G, e Rk (f ). Algorithm 5 can then be applied to these modified LPs to test whether the commodity-specific MmFair instance satisfies the prescribed fairness threshold. Therefore, the commodity-specific-threshold versions of RS, RS-mRC, and MmFair can be reduced to their corresponding common-threshold fixed-loss formulations on the augmented network. We emphasize that the optimization-problem instances studied in this paper do not include commodity-specific fidelity thresholds as input. Thus, the above construction extends the decision problems, rather than directly extending the FPTASs for oRS, oRS-mRC, and oMmFair. Extending the optimization problems would require a generalized objective and a corresponding approximation analysis. Nevertheless, this transformation provides a useful building block for future studies of more general resource-allocation problems with commodity-specific fidelity requirements.

29

R EFERENCES [1] A. Abane, M. Cubeddu, V. S. Mai, and A. Battou, “Entanglement routing in quantum networks: A comprehensive survey,” IEEE Transactions on Quantum Engineering, vol. 6, pp. 1–39, 2025. [2] K. Azuma, S. E. Economou, D. Elkouss, P. Hilaire, L. Jiang, H.-K. Lo, and I. Tzitrin, “Quantum repeaters: From quantum networks to the quantum internet,” Reviews of Modern Physics, vol. 95, no. 4, p. 045006, 2023. [3] H.-J. Briegel, W. Dür, J. I. Cirac, and P. Zoller, “Quantum repeaters: the role of imperfect local operations in quantum communication,” Physical Review Letters, vol. 81, no. 26, p. 5932, 1998. [4] M. Caleffi, “Optimal routing for quantum networks,” IEEE Access, vol. 5, pp. 22 299–22 312, 2017. [5] K. Chakraborty, D. Elkouss, B. Rijsman, and S. Wehner, “Entanglement distribution in a quantum network: A multicommodity flow-based approach,” IEEE Transactions on Quantum Engineering, vol. 1, pp. 1–21, 2020. [6] W. Dai, T. Peng, and M. Z. Win, “Optimal remote entanglement distribution,” IEEE Journal on Selected Areas in Communications, vol. 38, no. 3, pp. 540–556, 2020. [7] L. Ford Jr and D. Fulkerson, Flows in Networks. Princeton University Press, 1962. [8] M. R. Garey and D. S. Johnson, Computers and Intractability. W.H. Freeman and Company, New York, 1979. [9] H. Gu, Z. Li, X. Wang, D. Yang, G. Xue, and R. Yu, “Cost-aware high-fidelity entanglement distribution and purification in the quantum internet,” IEEE Transactions on Networking, vol. 34, pp. 681–696, 2026. [10] H. Gu, Z. Li, R. Yu, X. Wang, F. Zhou, J. Liu, and G. Xue, “FENDI: Toward high-fidelity entanglement distribution in the quantum internet,” IEEE/ACM Transactions on Networking, vol. 32, no. 6, pp. 5033–5048, 2024. [11] H. Gu, R. Yu, Z. Li, X. Wang, and F. Zhou, “ESDI: Entanglement scheduling and distribution in the quantum internet,” in 2023 32nd International Conference on Computer Communications and Networks (ICCCN). IEEE, 2023, pp. 1–10. [12] C. Joe-Wong, S. Sen, T. Lan, and M. Chiang, “Multiresource allocation: Fairness–efficiency tradeoffs in a unifying framework,” IEEE/ACM Transactions on Networking, vol. 21, no. 6, pp. 1785–1798, 2013. [13] J. Kleinberg and E. Tardos, Algorithm Design. Pearson Education India, 2006. [14] P. Komar, E. M. Kessler, M. Bishof, L. Jiang, A. S. Sørensen, J. Ye, and M. D. Lukin, “A quantum network of clocks,” Nature Physics, vol. 10, no. 8, pp. 582–587, 2014. [15] T. Lan, D. Kao, M. Chiang, and A. Sabharwal, “An axiomatic theory of fairness in network resource allocation.” IEEE, 2010, pp. 1–9. [16] C. Li, T. Li, Y.-X. Liu, and P. Cappellaro, “Effective routing design for remote entanglement generation on quantum networks,” npj Quantum Information, vol. 7, no. 1, p. 10, 2021. [17] J. Li, M. Wang, K. Xue, R. Li, N. Yu, Q. Sun, and J. Lu, “Fidelity-guaranteed entanglement routing in quantum networks,” IEEE Transactions on Communications, vol. 70, no. 10, pp. 6748–6763, 2022. [18] D. H. Lorenz and D. Raz, “A simple efficient approximation scheme for the restricted shortest path problem,” Operations Research Letters, vol. 28, no. 5, pp. 213–219, 2001. [19] S. Misra, G. Xue, and D. Yang, “Polynomial time approximations for multi-path routing with bandwidth and delay constraints,” in IEEE INFOCOM 2009. IEEE, 2009, pp. 558–566. [20] D. Nace and M. Pióro, “Max-min fairness and its applications to routing and load-balancing in communication networks: a tutorial,” IEEE Communications Surveys & Tutorials, vol. 10, no. 4, pp. 5–17, 2008. [21] M. Pant, H. Krovi, D. Towsley, L. Tassiulas, L. Jiang, P. Basu, D. Englund, and S. Guha, “Routing entanglement in the quantum internet,” NPJ Quantum Information, vol. 5, no. 1, p. 25, 2019. [22] N. Rao and S. Batsell, “QoS routing via multiple paths using bandwidth reservation,” in Proceedings. IEEE INFOCOM’1998-IEEE Conference on Computer Communications, 1998, pp. 11–18. [23] S. Shi and C. Qian, “Concurrent entanglement routing for quantum networks: Model and designs,” in Proceedings ACM SIGCOMM, 2020, pp. 62–75. [24] R. Van Meter, Quantum networking. John Wiley & Sons, 2014. [25] R. Van Meter, R. Satoh, N. Benchasattabuse, K. Teramoto, T. Matsuo, M. Hajdušek, T. Satoh, S. Nagayama, and S. Suzuki, “A quantum internet architecture,” in 2022 IEEE International Conference on Quantum Computing and Engineering (QCE). IEEE, 2022, pp. 341–352. [26] G. Vardoyan, E. Van Milligen, S. Guha, S. Wehner, and D. Towsley, “On the bipartite entanglement capacity of quantum networks,” IEEE Transactions on Quantum Engineering, vol. 5, pp. 1–14, 2024. [27] Z. Wang, J. Li, K. Xue, Z. Li, R. Li, N. Yu, Q. Sun, and J. Lu, “Fair-eas: Entanglement allocation and selection for process-oriented fairness in quantum communication networks,” IEEE Transactions on Communications, vol. 73, no. 7, pp. 4841–4854, 2024. [28] Z. Wang and J. Crowcroft, “Quality-of-service routing for supporting multimedia applications,” IEEE Journal on Selected Areas in Communications, vol. 14, no. 7, pp. 1228–1234, 1996. [29] R. F. Werner, “Quantum states with einstein-podolsky-rosen correlations admitting a hidden-variable model,” Physical Review A, vol. 40, no. 8, p. 4277, 1989. [30] G. Xue, W. Zhang, J. Tang, and K. Thulasiraman, “Polynomial time approximation algorithms for multi-constrained qos routing,” IEEE/ACM Transactions on Networking, vol. 16, no. 3, pp. 656–669, 2008. [31] D. Yang, G. Xue, X. Fang, S. Misra, and J. Zhang, “Routing in max-min fair networks: A game theoretic approach,” in The 18th IEEE International Conference on Network Protocols. IEEE, 2010, pp. 1–10. [32] Y. Ye, “An O(n3 L) potential reduction algorithm for linear programming,” Mathematical programming, vol. 50, no. 1, pp. 239–258, 1991.

30

[33] Y. Zeng, J. Zhang, J. Liu, Z. Liu, and Y. Yang, “Entanglement routing design over quantum networks,” IEEE/ACM Transactions on Networking, vol. 32, no. 1, pp. 352–367, 2023. [34] Q. Zhang, N. Di Cicco, M. Ibrahimi, R. C. Almeida, A. Gatto, R. Boutaba, and M. Tornatore, “Link configuration for fidelityconstrained entanglement routing in quantum networks,” in IEEE INFOCOM 2025-IEEE Conference on Computer Communications. IEEE, 2025, pp. 1–10. [35] Y. Zhao and C. Qiao, “Redundant entanglement provisioning and selection for throughput maximization in quantum networks,” in IEEE INFOCOM 2021-IEEE Conference on Computer Communications. IEEE, 2021, pp. 1–10. [36] Y. Zhao, G. Zhao, and C. Qiao, “E2e fidelity aware routing and purification for throughput maximization in quantum networks,” in IEEE INFOCOM 2022-IEEE Conference on Computer Communications. IEEE, 2022, pp. 480–489.

31

Related documents

• Recon?figurable measurement scheme compatible with MDI-QKD and BB84 protocols using single-laser sideband generation#821909
• Privacy in continuous-variable distributed quantum sensing#927158
• One-shot Routing in Quantum Networks#1077679
• Quantum phase estimation with optimal confidence interval using three control qubits#635727
• Quantum phase estimation with optimal confidence interval using three control qubits#633378