Quantum Network Optimization: From Optimal Routing to Fair Resource Allocation

https://dl.acm.org/doi/10.1145/3726854.3727312

Abs

量子网络是实现大规模长距离量子通信的关键基础设施，但在路由优化和资源分配方面面临重大挑战，主要源于其概率性特性和量子资源的限制。现有方法通常孤立地解决这些问题，例如直接应用经典路由算法、不考虑公平性地最大化总收益来分配资源，或以临时方式改进公平性而缺乏严谨模型。本文提出了一个通用框架来系统性地解决这些挑战。首先，使用路由代数作为数学基础，对量子网络度量进行了全面分析，并设计了可证明最优的路由算法以应对其概率特性带来的独特挑战。其次，构建了一个优化模型，在考虑各种量子资源约束的同时，兼顾并发请求间的公平性，并设计了高效的近最优启发式算法来求解该模型。该框架为未来量子网络的设计和管理提供了理论见解和实际解决方案。

1. Intro

量子网络优化面临两个核心挑战：1）计算最优路径以最大化反映网络概率特性的性能指标；2）在多个并发通信请求间高效分配有限的量子资源（如量子比特）。

许多研究忽略了量子网络度量的独特属性，错误地应用了经典路由算法（如Dijkstra或Yen算法），缺乏系统性的数学基础来分析这些度量并设计专用算法。虽然有工作意识到了非等张性问题，但其解决方案需要枚举所有简单路径，计算上不可行。现有方法要么完全忽略公平性，要么通过临时方法（如加权轮询WRR）处理，缺乏严格的模型。此外，一些模型忽略了节点量子比特的严格限制，或者在量子比特稀缺时建立冗余纠缠对的方案不切实际。

本文通过将路由和资源分配统一到一个通用框架中来应对这些挑战。建立了路由代数理论作为量子网络最优路由的系统性数学基础。这使得能够对不同量子网络度量进行严格优化，并深入理解这些度量的独特特性。研究了这些度量的代数性质，并开发了可证明能找到各种场景下最优及top-K最优路径的路由算法。理论分析了所提方法与常规方法之间的最优性差距，并确定了该差距显著的条件。构建了一个全面的整数规划模型，该模型同时处理并发请求间的公平性目标，并遵守基于路由算法得到的top-K最优路径的各种量子资源约束。开发了解决方案，包括专门的启发式算法和拉格朗日松弛结合次梯度方法。大量模拟表明，启发式算法在显著降低计算复杂度的同时实现了接近最优的性能。

2. Background

量子路由度量：

• 吞吐量 和 保真度 是两个基本度量。本文主要关注吞吐量优化，因为它是优化保真度的前提（改善保真度通常需要牺牲部分纠缠对进行纠错和纯化）。
• 期望吞吐量（EXT）：计算源和目的地之间可建立的量子链路的期望数量。计算复杂，且通常假设链路上不同纠缠对独立同分布。
• 可达速率（AR）：基于纠缠对生成能力定义。对于路径 $l = u_0u_1...u_n$，$AR(l) = p^{n-1} \cdot \min\{C(u_i, u_{i+1})\}$，其中$p$是纠缠交换成功概率，$C(u, v)$是信道容量。

资源分配：
先前研究主要关注在节点量子内存和信道容量约束下最大化吞吐量。挑战在于量子比特作为离散资源分配。现有方法在考虑节点约束或公平性方面存在不足。

3. Method

3.1 基于路由代数的最优路由

问题：经典路由算法（如Dijkstra, Yen）依赖于度量的等张性（Isotonicity）：如果路径a优于路径b，那么将a和b与任何第三条路径c连接后，$a\oplus c$仍然优于$b\oplus c$。然而，量子网络度量（如EXT和AR）不满足等张性，直接应用经典算法可能导致选择次优路径。

解决方案：路由代数框架

• 定义：路由代数是一个五元组 $(S, \preceq, L, \oplus, w)$。其中$S$是路径权重集合，$\preceq$是$S$上的全序，$L$是所有路径的集合，$w: L \rightarrow S$是权重函数，$\oplus$是路径连接操作。
• 关键属性：
  • 单调性：路径延伸不会改善路径权重。
  • 等张性：路径偏好在对路径进行延伸时保持不变。
• 定理：EXT和AR的代数不满足等张性（通过反例证明）。
• 核心思想：通过最大等张约简（GR） 将非等张的全序$\preceq$转换为等张的偏序$\preceq_{GR}$。GR的定义是：$w(a) \preceq_{GR} w(b)$ 当且仅当 对于所有路径$x$，有 $w(a\oplus x) \preceq w(b\oplus x)$。当等张性被破坏时，通过使路径权重不可比较来建立等张性。

3.2 路由算法

D-Dijkstra (Dominant Dijkstra) 算法

• 解决问题：在偏序$\preceq_{GR}$下，每个节点可能保留多条不可比较的“支配”路径。经典Dijkstra只保留一条路径是不够的。
• 设计思路：扩展Dijkstra算法，在每个节点维护一个“当选路径”集合，包含所有在该节点未被其他路径支配的路径。优先级队列仍按原始全序$\preceq$排序以保证效率。
• 算法流程：
  1. 计算GR。
  2. 初始化每个节点的当选路径集为空，优先级队列包含源节点。
  3. 当队列非空时，弹出当前全序最优路径。
  4. 将当前路径与当前节点的当选路径集合并，并使用Dominant函数（根据$\preceq_{GR}$）更新当选路径集。
  5. 如果当选路径集有更新，则松弛当前路径的出边，将新路径加入队列。
• 正确性：算法终止时，每个目的节点的当选路径集包含了在所有简单路径中处于支配地位的路径（在$\preceq_{GR}$下）。
• 复杂度：$O(P|E| \log(P|E|) + P^2|E|)$，其中$P$是任何节点保留的最大支配路径数。

KOP (K-Optimal Paths) 算法

• 解决问题：在非等张度量$\preceq$下找到top-K简单路径。
• 设计思路：扩展Yen’s算法。首先使用D-Dijkstra（基于$\preceq_{GR}$）找到初始最优路径。然后，通过系统性地分解已发现路径为根路径和支路路径来生成候选路径，同时修改网络以避免重复路径。
• 算法流程：
  1. 计算GR。
  2. 使用D-Dijkstra找到初始路径集，加入候选队列B（按$\preceq$排序）。
  3. 弹出B中最优路径作为$A_0$。
  4. 对于k从1到K-1：
     • 对于$A_{k-1}$中的每个节点位置i：
       • 设置支路节点，根路径。
       • 临时移除与之前路径共享根路径的边和节点（除支路节点）。
       • 使用D-Dijkstra从支路节点到目的地计算支路路径。
       • 将根路径与支路路径连接后的新路径加入B。
     • 从B中弹出最优路径，若未被选中则加入$A_k$。
• 正确性：算法终止时返回关于$\preceq$的top-K简单路径。
• 复杂度：$O(K P |V| |E| \log(P|E|) + K P^2 |V| |E|)$，计算量较大。

H-KOP (Heuristic K-Optimal Paths) 算法

• 解决问题：KOP计算复杂度高，不适合大规模网络。
• 设计思路：在KOP的支路路径计算中，用标准的Dijkstra算法（基于原始全序$\preceq$）替代D-Dijkstra（基于$\preceq_{GR}$）。这显著减少了计算开销，但可能牺牲部分最优性。
• 优势：在最优性和计算效率之间取得良好平衡，适用于在线路由。

3.3 EXT路由的深入分析与误差界

EXT的简化表达式

• 原始EXT计算复杂。通过Abel部分求和推导出简化形式：
  $EXT(l) = \left(\prod_{n\in l^\circ} p_n\right) \cdot \sum_{i=1}^W P_i^+(l)$
  其中$P_i^+(l) = \prod_{j=1}^h Q_i^+(j)$ 是路径$l$上至少成功$i$个链路的概率。此形式计算更高效，且适用于非独立同分布链路。

EXT的GR推导

• 通过定理3.5和引理3.10，推导出EXT的GR等价于：
  $EXT(a) \preceq_{GR} EXT(b) \Leftrightarrow \text{对于所有 } j \in \{1,2,...,W\}, \text{ 有 } \left(\prod_{n\in a^\circ} p_n\right) \cdot \sum_{i=1}^j P_i^+(a) \geq \left(\prod_{n\in b^\circ} p_n\right) \cdot \sum_{i=1}^j P_i^+(b)$
• 意义：路径$l$的权重可以表示为一个$W$维向量：
  $( EXT(l)_{\text{for}_1\text{link}}, EXT(l)_{\text{for}_{\leq2}\text{links}}, ..., EXT(l)_{\text{for}_{\leq W}\text{links}} )$
  GR下的支配性判断转化为该向量的乘积序。

直接应用Dijkstra的误差分析

• 问题：当$\preceq$非等张时，直接应用Dijkstra可能错过全局最优路径。
• 分析：定义了相对误差$\varepsilon = 1 - \eta$，其中$\eta = EXT(a\oplus x) / EXT(b\oplus x)$。通过分析找到$\eta$的下界。
• 结论：相对误差$\varepsilon$存在一个严格上界 $(W-1)/W$。$W$是任何节点对间允许的最大量子链路数。这表明在最坏情况下，直接应用Dijkstra可能产生显著误差，尤其是在某些跳的多量子链路成功概率很低时。

3.4 量子网络中的公平资源分配

公平性模型 (M1)

• 目标：最大化所有S-D对中最小的利润（max-min公平性）。利润可以是EXT或其他度量。
• 决策变量：
  • $z$: 最小利润阈值。
  • $x_{ijk}$: 二进制变量，表示是否为S-D对$i$的第$j$条路径分配$k$个量子链路。
• 约束：
  • (9a) 每个S-D对的总利润 $\geq z$。
  • (9b) 每个瓶颈节点$n$的量子比特消耗 $\leq$ 其容量$Q_n$。
  • (9c) 每个瓶颈边$m$的信道资源消耗 $\leq$ 其容量$C_m$。
  • (9d) 为每条路径选择恰好一种分配方案。
• 问题复杂度：是MMKP的推广，属于强NP难问题。

启发式公平算法 (Algorithm 3)

• 解决问题：精确求解M1计算不可行，需要高效的近似算法。
• 设计思路：从最大分配开始（每条路径分配$W$个链路），迭代地减少分配直到满足所有资源约束，同时尽量保持最低利润$z$的最大化。
• 算法流程：
  1. 初始化所有路径分配最大量子链路数。
  2. 计算当前资源约束违反程度$R^*$（最大超过1的比率）。
  3. 当存在违反约束时（$R^* > 1$）：
     a. 找到最 violated 的约束（节点或边）及其关联路径集合$L$。
     b. 使用启发式规则从$L$中选择一条路径减少其分配的量子链路数。
     c. 更新利润和资源使用情况。
• 启发式规则：
  • Heuristic 1 (侧重公平性)：对于候选路径，模拟减少一个链路，计算新的全局最小利润。选择使新的全局最小利润最大的路径（即对最小利润损伤最小）。若平局，选当前利润最高的路径。
  • Heuristic 2 (平衡公平性与约束解决)：对于候选路径，计算减少一个链路造成的全局最小利润损失$\Delta z_l$与违反约束减少量$\Delta R_{ij}$的比值。选择使比值$\Delta z_l / \Delta R_{ij}$最小的路径（即用最小的公平性损失换取最大的约束解决）。若平局，选当前利润最高的路径。$\Delta R_{ij}$定义为路径遍历的所有活跃 violated 约束的违反度减少之和。

拉格朗日松弛与次梯度方法

• 方法：将资源约束(9b)(9c)和公平性约束(9a)松弛到目标函数中，引入拉格朗日乘子。原问题分解为多个独立的子问题（每个路径一个），这些子问题可以快速求解。使用次梯度方法迭代更新乘子。
• 局限性：在公平性模型中，次梯度方法表现不佳，容易陷入局部极值或不可行解，且收敛慢。

4. Evaluation

路由算法评估：在五种不同规模的随机网络和三种边生成方法下，将KOP和H-KOP与Yen’s算法进行对比，结果显示H-KOP在保持接近KOP最优性的同时，其计算效率显著高于KOP，并且在所有测试场景下均优于直接应用Yen’s算法，尤其在易导致非等张性的网络配置（E3）中优势更为明显。

资源分配算法评估：在不同网络规模和源-目的地对数量的设定下，将两种启发式算法与子梯度法及加权轮询进行对比，并使用Gurobi求解器作为最优基准，实验表明启发式算法（特别是Heuristic 2）能够在毫秒级时间内获得接近最优的解，其性能远优于子梯度法和加权轮询，实现了求解质量与计算效率的良好平衡。