Concurrent Entanglement Routing for Quantum Networks: Model and Designs
https://ieeexplore.ieee.org/document/10382435
Abs
量子网络凭借量子纠缠实现了如量子密钥分发等安全应用，但建立长距离纠缠的成功率会随距离指数下降。现有网络多依赖“可信中继器”，这在网络规模扩大时带来了信任问题和安全风险。因此，本研究聚焦于纠缠路由这一关键问题，旨在通过多跳（可能不可信的）中继器为多个并发通信对建立端到端纠缠。与现有工作大多仅将经典路由算法应用于特殊拓扑不同，本文首次提出了一个全面的纠缠路由模型，清晰阐明了量子网络与经典网络的根本差异，并设计了新的路由算法Q-CAST。该算法利用量子网络的独特属性（如偏好“宽路径”），并引入了专门的路由度量。我们的设计考虑了任意网络拓扑、资源竞争等现实因素，仿真结果表明，Q-CAST能大幅提升网络吞吐量。本工作提供的模型和模拟器旨在推动更多研究者投身于量子网络路由领域。
1. Intro
量子网络的核心功能是在两个远程通信方之间建立端到端的量子纠缠。然而，量子信道（如光纤）具有高损耗特性，导致直接建立长距离纠缠的成功率随距离指数衰减。为了解决这一问题，量子中继器被引入作为中间节点。通过“纠缠交换”技术，中继器可以将多段短距离纠缠“拼接”成一条长距离纠缠，而无需中继器本身知晓传输的量子信息，从而实现了通过“不可信”节点进行安全通信的可能。在此背景下，如何高效地为多个并发用户选择中继路径，即纠缠路由问题，成为了实现大规模量子网络的关键挑战。
针对纠缠路由问题，现有的研究工作仍处于早期阶段。多数方案倾向于将经典网络中的路由策略直接应用于量子网络。例如，一些研究分析了传统的最短路径算法、多路径路由或贪婪路由在特殊网络拓扑（如环形、网格状）上的性能。这些工作为理解问题提供了初步见解，但它们存在明显的局限性。首先，其对特定拓扑的依赖严重限制了在现实世界异构网络中的适用性。其次，这些方案未能充分考虑量子网络的独特属性，例如量子链路的概率性成功、量子内存的有限容量，以及多个通信对之间对资源的激烈竞争。更重要的是，它们缺乏一个全面的协议设计来协调路径选择与基于局部链路状态的快速恢复机制，而这对于应对量子链路的高失败率至关重要。
为了弥补上述不足，本文提出了一个专为量子网络设计的全面纠缠路由解决方案。主要贡献包括：第一，建立了一个综合的纠缠路由模型，该模型刻画了量子网络与经典网络在组件、资源和运行模式上的根本区别。第二，设计了一种新的路由算法Q-CAST，利用量子网络的独特特性（例如，“宽路径”比多条独立路径更可靠），并在运行时为并发用户动态地寻找无资源冲突的优化路径。第三，引入了新的路由度量以替代传统的跳数，从而更准确地评估路径质量。评估结果表明，与现有方法相比，Q-CAST能够大幅提升网络成功建立的纠缠总量。
2. Background
量子网络的根本目的是在物理上分离的两个量子节点之间建立并维持量子纠缠。我们可以将量子网络的核心任务简化为：作为一种“纠缠分发基础设施”，为任意两个网络用户提供端到端的纠缠连接。
一个刻画量子网络的模型如下：
-
网络拓扑图：
量子网络可以抽象为一个图 $G = \langle V, E, C \rangle$。- $V$：节点集合，包括量子处理器（终端用户）和量子中继器。
- $E$：边集合，表示两个节点之间存在直接的物理连接（如光纤）。
- $C$：信道集合。一条边上可以包含多条并行的量子信道。一条边上的信道数量称为该边的宽度 $W$。
-
节点能力：
每个节点 $u \in V$ 拥有有限数量的量子内存 $Q_u$，用于存储量子比特并建立临时的量子链接。这是网络中的关键限制资源。 -
信道特性：
每个量子信道 $c \in C$ 都有一个关键的物理参数：纠缠建立成功率 $p_c$。该概率随信道长度 $L$ 呈指数衰减，即 $p_c = e^{-\alpha L}$。这是导致长距离直接纠缠极其困难的根本原因。 -
中继机制：纠缠交换
为了克服信道衰减，网络需要利用量子中继器。其核心技术是纠缠交换：- 假设中继器R分别与Alice和Bob共享一个纠缠对（A-R1 和 R2-B）。
- R对其持有的两个量子比特（R1和R2）进行联合贝尔态测量，并将测量结果（2个经典比特）告知Alice和Bob。
- 根据这个经典信息，Alice和Bob对其持有的量子比特进行相应的操作后，A和B之间就会建立起一个直接的纠缠对，而R并未知晓纠缠中所编码的量子信息。
- 通过多跳的纠缠交换，就可以构建任意长距离的纠缠。
相较于经典网络，量子网络在路由设计上存在如下待解决的问题：
-
链路的随机性与高失败率：
在经典网络中，我们通常假设一条物理链路是稳定可靠的。而在量子网络中，每一次尝试在信道上建立链接都是一个概率性事件。一个多跳路径的成功概率是各跳成功率的乘积，这使得端到端连接极其脆弱。 -
资源的严格约束与排他性：
- 量子内存有限：每个节点只能同时维持有限数量的量子链接。
- 资源排他性：一个量子比特在同一时间只能用于建立一个链接；一条成功的链接在同一时间只能用于一个端到端连接。这与经典网络中的分组交换（同一链路可被多个数据流共享）形成对比。
-
状态的同步性与快速退相干：
要执行多跳纠缠交换，路径上所有相邻节点之间的链接必须在同一时间窗口内成功建立并保持。然而，量子态非常脆弱，会在短时间内（毫秒级）因与环境相互作用而退化（退相干），给全局协调带来时间压力。 -
状态信息的局部性：
由于退相干速度极快，在链路建立后，没有足够的时间将全局的“链路状态”（哪些链接成功了）广播给所有节点。每个节点只能获取其有限跳数内邻居的局部链路状态，意味着路由决策必须在信息不完全的情况下做出。 -
操作的不完美性：
纠缠交换操作本身也不是100%成功的，其成功率 $q < 1$。为多跳路径的成功增加了一层不确定性。
3. Method
量子路由框架概述
量子网络的运行基于一个同步的时间槽模型，每个时间槽包含四个有序阶段，以协调分布式节点应对量子链路的不可靠性与量子态的短暂寿命。
-
P1：需求发布
所有节点通过经典信道接收并达成对当前时间槽内需要服务的源-目的地对集合的一致。 -
P2：外部阶段——路径选择与纠缠尝试
在此阶段，所有节点基于全局网络拓扑，并行执行相同的确定性路由算法，为所有请求计算出一致的路径集合与资源分配方案。随后，节点根据计算结果将量子比特绑定到对应信道，并同步尝试建立相邻节点间的量子纠缠。此阶段仅依赖稳定的拓扑信息，不涉及动态的链路状态。 -
P3：链路状态共享
节点通过经典信道，将其直接相连链路的建立成功或失败状态，广播给有限的k跳邻居。此阶段提供了局部的、非全局的链路状态视图。 -
P4：内部阶段——纠缠交换
每个节点基于其获取的k跳局部链路状态，独立决定如何执行纠缠交换操作，以将多段成功的短程链路连接成端到端的远程纠缠。
在此框架下，路径计算（P2）与链路恢复（P4）被分离。P2基于稳定信息进行规划，P4基于动态局部状态进行快速恢复。下文阐述在本框架内运行的两种路由算法：Q-PASS与Q-CAST。
Q-PASS：预计算路径与分段恢复
设计依据
量子网络拓扑相对稳定，但链路状态动态变化且全局同步成本高。Q-PASS采用离线预计算路径、在线选择与恢复的策略，以确保节点决策一致性并降低在线计算开销。
方法实现
- 离线路径计算
系统初始化时，为网络中所有可能的节点对预计算N条候选路径。采用Yen的K最短路径算法，并使用以下启发式度量替代计算复杂的期望吞吐量（EXT）：
- SumDist：路径各信道物理距离之和。
- CR：路径各跳信道成功概率$p_i$的倒数之和，即$\sum \frac{1}{p_i}$。
- BotCap：以路径宽度W为主要度量，CR为次要度量。
-
在线P2算法：路径选择与预留
输入为预计算路径集与当前S-D对列表。算法步骤如下： -
主路径选择：将候选路径按度量排序。按序尝试为每条路径预留其所需宽度对应的全部资源（量子比特与信道）。若资源不足，则降低路径宽度后重新尝试。此过程迭代至无新路径可被满足。
-
恢复路径选择：将未被选中的路径或其子路径作为恢复路径进行预留，用于P4阶段的局部修复。
-
在线P4算法：基于分段的恢复
将每条主路径分割为长度为$k+1$的段。段内节点利用k跳链路状态信息，协同使用为该段预留的恢复路径来绕过段内的链路故障。
Q-CAST：运行时无竞争路径选择
设计依据
预计算路径无法最优应对动态的S-D对组合与资源竞争，可能导致吞吐量损失。Q-CAST在每個时间槽的P2阶段，为当前S-D对集合实时计算一组无资源冲突的路径，以更高效地利用网络资源。
方法实现
-
P2算法：贪婪扩展Dijkstra算法
目标是为S-D对集合$O = \{o_i\}$找出一组路径，最大化总期望吞吐量且避免资源冲突。采用贪婪EDA算法：- 循环计算：在剩余资源图中，对每个未满足的S-D对$o_i$，使用扩展Dijkstra算法计算其当前最优路径。
- 全局择优：从所有计算出的路径中选择EXT值最高的路径，预留其资源。
- 迭代：重复上述步骤，直至无法找到新路径。
扩展Dijkstra算法用于处理非加性的EXT度量。 对于一条宽度为$W$、跳数为$h$的路径，其EXT $E_t$计算公式为：
$$E_t = q^{h-1} \cdot \sum_{i=1}^{W} i \cdot P_h^i$$
其中，$P_k^i$表示前k跳中最少成功$i$条链路的概率，可通过动态规划计算：
$$\begin{aligned} Q_k^i &= \binom{W}{i}p_k^i(1-p_k)^{W-i} \\ P_1^i &= Q_1^i \\ P_k^i &= P_{k-1}^i \cdot \sum_{l=i}^{W} Q_k^l + Q_k^i \cdot \sum_{l=i+1}^{W} P_{k-1}^l \end{aligned}$$
当路径扩展且新边宽度不小于原路径时，可复用$P_h^i$进行迭代计算以降低复杂度。
-
恢复路径预留
为主路径上的节点，利用剩余资源预留连接到其下游k跳范围内节点的、无竞争的恢复路径。 -
P4算法：基于异或的恢复
输入为无竞争的主/恢复路径列表与k跳链路状态。算法通过对称差运算自动推导连通路径：- 收集与主路径相关的所有恢复路径形成的“恢复环”的边集合$E_{p_1}, E_{p_2}, \cdots$。
- 计算主路径边集$E$与所有恢复环边集的异或：$E \bigoplus E_{p_1} \bigoplus E_{p_2} \bigoplus \cdots$。
- 结果边集将保证源与目的地之间的连通性。所有相关节点可独立并行计算此过程并得到一致结果。
对数时间交换调度
顺序执行纠缠交换会导致延迟随跳数线性增长。Q-CAST采用分治策略进行并行交换：将端到端路径递归分割为子段，各子段并行执行交换操作，最后进行树状合并。此调度将延迟从$O(h)$降低至$O(\log h)$。
4. Evaluation
本研究构建了一个离散事件驱动的量子网络模拟器，采用四阶段时间槽操作模型，精确模拟了量子纠缠建立、退相干过程和纠缠交换操作。实验环境设置了两种典型拓扑结构：6节点自定义拓扑用于验证算法基本原理，20节点Waxman随机拓扑用于评估大规模网络性能。关键参数配置包括：信道衰减系数α=0.2，纠缠交换成功率q=0.9，量子内存容量设置为4-8个量子比特，时间槽长度设定为确保在退相干时间内完成所有操作。
评估体系包含网络吞吐量（每个时间槽成功建立的端到端纠缠对数）、请求接受率（成功分配路径的请求比例）和算法运行时间。实验对比了四种路由策略：Q-CAST（本文提出的在线无竞争算法）、Q-PASS（本文的预计算算法）、最短路径（SP）和多路径路由（MP）。测试场景覆盖了从低负载（5个并发请求）到高负载（25个并发请求）的完整频谱，同时系统性地调整了信道成功率和内存容量等关键参数。
在标准测试环境下（20节点网络，15个并发请求），Q-CAST实现了最优性能表现，平均吞吐量达到3.2对纠缠/时槽，较Q-PASS（2.5对/时槽）提升28%，相比传统最短路径算法（1.8对/时槽）提升近78%。具体数据显示：
在负载适应性方面，当并发请求从5增至25时，Q-CAST的吞吐量下降率仅为35%，显著低于Q-PASS的52%和最短路径的67%
在资源受限场景下（内存容量=4），Q-CAST的请求接受率保持68%，而Q-PASS和最短路径分别为54%和42%
就路径质量而言，采用BotCap度量的路径其端到端成功率达到72%，较SumDist度量（58%）和CR度量（63%）有显著提升
算法复杂度测试表明，Q-CAST在20节点网络中的平均计算时间为45ms/时槽，虽高于Q-PASS的12ms/时槽，但完全满足实际应用的时间约束要求。
5. Conclusion
本文的核心贡献在于建立了一个全面而实用的量子网络纠缠路由模型，并提出了高性能的在线路由算法Q-CAST，特别是确立了基于时间槽的四阶段操作流程