Notes: A Link Layer Protocol for Quantum Networks

论文作者：Axel Dahlberg, Matthew Skrzypczyk, Tim Coopmans 等 12 人
Notes by 李辰剑 2022-12-14

---

Contents

• 作者背景
• 论文背景
• 核心内容
• 实证评估
• 对工作的评价

作者背景

这是一篇 2019 年发表在计算机网络顶级期刊 SIGCOMM 上的论文，方向为量子网络。近年来，量子计算和量子通信一直是研究的热点方向，而量子网络正是量子通信中的一个概念。

虽然量子网络离大规模实现还很远，但是远在荷兰的 Delft 大学的 QuTech 研究组却选择将其作为主攻方向，几乎将全部的资源押注在量子网络上，近年来也确实取得了许多前沿成果，本篇论文就是其中之一。

我观察了这篇论文的一作二作，发现他们在近五年才有了引用量，且近几年引用量快速上升。可以推测，他们是 QuTech 研究组（Delft 大学研究量子计算和量子信息的课提组）的博士生，是学术界的下一代。这篇论文目前已经获得120的引用量（数据来自 Google Scholar），得到了学界的广泛关注。这篇文章，再加上几位博士生快速上升的引用量，说明他们可能是正在升起的学术新星。

QuTech研究组官方网站链接：https://qutech.nl/

论文背景

近年来，量子计算和量子信息一直是研究的热点方向之一。量子通信是量子信息的主要部分，其目标是利用量子力学的特性（例如量子纠缠）做到超越经典通信的能力。例如，由于无法被完整克隆，量子态无法像经典信息一样被复制并发送，但利用一对提前共享的纠缠对，便可以将一个量子态从一处传送到另一处。又如，利用一对提前共享的纠缠对，只发送一个经典 bit 便可在通信双方之间传送 2 bit 信息——这又被称为“超密编码” (superdense coding)。

由此可见，纠缠对在量子通信中起着重要的作用，大多数的量子通信方案都直接依赖于它。然而，在现实世界中真正产生纠缠对并非一件容易的事，想让远距离的通信双方长时间持有纠缠对更是难上加难。困难主要包括如下几项：

1. 单次脉冲（可以理解为硬件设备的输入）不一定能触发纠缠产生过程，往往需要重复多次。
2. 纠缠对的一部分（纠缠光子）需要沿光纤传播，过程中会有噪声和损耗；而量子态类似模拟信息，无法像数字信息一样中继放大，因此真正通信双方获得的纠缠对总是带噪声的。
3. 量子态极脆弱、易受环境噪声影响，因而量子态只能存储很短的时间。目前主流的技术方案可以将量子态存储数十毫秒到数秒时间——取决于不同的物理实现。如此之短的存储时间给纠缠对的产生与分发和随后的量子通信带来了极大的挑战。

面对如此多的挑战，近年来学界给出的答案是：借鉴经典计算机网络的体系结构，通过分层逐步解决问题。

经典计算机网络是一个通过分层逐步解决问题、逐步实现复杂功能的典型例子。物理层负责基本通信、链路层负责建立点对点连接、网络层负责路由和建立跨结点连接、传输层负责可靠通信，不同协议层各司其职、层层抽象，最终才将狂野的物理介质驯化为温柔可靠的计算机网络，可以在任意点对点之间进行高效、可靠的信息传输。

类比经典计算机网络的结构，研究人员设想量子通信也可以分为四个协议层：物理层负责基本的纠缠产生、屏蔽物理细节，链路层负责在光纤直接相连的节点间可靠地产生和分发纠缠对，网络层负责在任意两个节点（可能没有直接相连的链路）建立纠缠对，而最后由传输层负责利用纠缠对传送量子态，进行 quantum teleportation 等高级操作。

这篇论文的工作，便是基于现有的物理实现提出了基本的链路层协议，并对该协议进行了初步的性能分析。

我们前面提到，真实世界中的量子态是极其脆弱的。为了抑制噪声，目前量子计算的主流物理实现方案往往都需要苛刻的物理条件。超导量子比特体系结构会将整个体系冷却到 10mK 以下，远远低于液氮温度；离子阱体系则需要高真空环境，二者成本都非常高昂。然而在量子通信中，往往只需要一到二个量子比特参与纠缠，因此可以选择 量子比特数较少的 NV 色心作为物理实现方案。NV 色心是金刚石晶格中的一种缺陷结构，由于金刚石结构极其稳定，因此在室温常压条件下也能维持量子态相干。在这篇文章中，便采用了 NV 色心作为物理实验平台。

核心内容

论文首先讨论了上层对链路层可能的需求，然后设计了一套链路层和物理层之间的接口，最后给出了物理层和链路层的实现。

上层需求

为了定义好协议，首先需要探讨上层（网络层，或应用层）对链路层有哪些可能的需求。论文中将应用归为四类：

直接测量 (Measure Directly, MD)。纠缠对产生之后由双方节点直接测量。这种需求往往来自物理实验：例如验证贝尔不等式（今年的诺贝尔物理奖）、光子的符合测量（即测量双端同时测出光子的概率，英文为 coincidence measurement）等等。由于纠缠对产生后直接测量、不需要转移到量子存储单元中，因此这一类需求对硬件的要求较低，产生的结果质量相对较好。

生成纠缠并保持 (Create and Keep, CK)。在这种情况中，纠缠对产生并被分发到双方节点，但不直接测量，而是保存在量子存储单元中以备日后使用。随后，双方节点可以在自己的量子比特上进行量子门电路操作（即进行酉变换），从而完成量子态传送、超密编码等各式各样的任务。大部分的量子通信技术都可以归为这类需求。

发送量子比特，或量子传态 (Send Qubit, SQ)。顾名思义，生成用于发送量子比特的纠缠对。对链路层而言，链路层只负责生成纠缠而不负责随后的传态，因此这一需求和生成纠缠并保持其实是一样的。但由于量子传态这一应用意义重大，作者将其归为单独一类需求。

供网络层使用 (Network Layer, NL)。顾名思义，在相邻（有量子链路直接连接）的节点间生成纠缠对，供网络层生成距离更远的纠缠对。值得一提的是，如果 AB 节点和 BC 节点间都有共享纠缠对，那么 B 节点可以通过“纠缠交换” (entanglement swapping[3]) 将 AB 和 BC 之间的纠缠消耗掉，生成 AC 之间的共享纠缠对。这样一来，网络层便可以在没有直接链路的节点之间生成纠缠。这便是链路层生成纠缠供网络层使用的主要目的。

层间接口

为了让设计协议具体实现时可以有的放矢，首先要定义好链路层协议和上层应用间的接口。

在论文中提出的接口中，上层协议在向链路层请求纠缠资源时可以给定以下参数：

1. 对端节点。
2. 请求类型：直接测量 (M, Create and Measure) 或生成纠缠并保持 (K, Create and Keep)。
3. 需要的纠缠对数量。允许上层协议一次性请求多个纠缠对有利于降低请求本身的开销，从而提升吞吐量。
4. 原子性：若请求了多对纠缠对，是否要求同时生成所有纠缠对（原子性标志设为真），或是允许逐个生成（标志设为假）。注意，由于量子存储器容量非常有限，同时请求（将原子性设为真）多个纠缠对可能会导致硬件无法实现，从而报错返回。
5. 连续返回 (Consecutive)：若请求了多个纠缠对并允许逐个生成，是否要在每个纠缠对生成时立刻通知上层（连续返回标志设为真），或只需要在所有纠缠对生成之后统一通知上层（标志设为假）。
6. 等待时间 $t_{\max}$：请求纠缠的上层协议愿意等待的最大时间。
7. 目的 ID (Purpose ID)：一个数字 ID，用来帮助上层或链路层标识每一条流。既可以帮助链路层识别上层的意图，也可以帮助上层标识某一条流，也可以起到类似端口的作用，在一条链路上帮助链路层实现多个上层应用的多路复用。
8. 优先级：帮助链路层中的调度器 (Scheduler) 进行调度。论文中，作者将 NL 的优先级设为最高，CK 次之，MD最后。
9. 最低保真度 (Desired Mininum Fidelity, $F_{\min}$)：这是一个纯量子的参数，也是唯一一个量子参数。由于可以处在任意叠加态，量子比特更像模拟信息，而非数字信息。不像数字信息比特在传输中只有两种可能（正确传输或翻转出错），量子态的失真是一个连续变化的量。业界常用保真度 (Fidelity) $F\in[0,1]$来度量。这个最低保真度便是要求链路层产生的纠缠对（两个量子比特构成的量子态）的最低质量要求。

随后，链路层向上层请求的返回会包含以下信息：

1. 纠缠对 ID $Ent_{\mathrm{ID}}$：用于标识每一对生成的纠缠对，便于通信双方标识纠缠对资源。在每个时刻，每个仍然存活的纠缠对的 ID 全局唯一。
2. 量子比特 ID（只对 K 类请求有效）：类似一个指针，标识纠缠对中位于本地的量子比特在量子存储单元中的位置。
3. 纠缠优度 (Goodness) $G$：对生成的纠缠对的保真度的估计。应有$G\ge F_{\min}$。由链路层中的保真度估计单元估计得到。（对 M 类请求的定义稍有不同，详见论文）
4. 测量结果（仅对 M 类请求有效）。
5. 生成纠缠对所花时间。
6. 保真度估计单元估计纠缠优度所花费的时间。

当链路层无法顺利完成请求时，也可能返回以下报错信息：

1. 若无法在请求的时间内完成任务（$t_{\max}$太小），返回 TIMEOUT。
2. 若要求的保真度太高，现有硬件无法完成（$F_{\min}$太高），返回 UNSUPP。
3. 量子存储单元全部清空也不足以存放要求的同时生成的纠缠对数量，返回 MEMEXCEEDED。
4. 量子存储单元目前的剩余容量不足以存放要求的同时生成的纠缠对数量，返回 OUTOFMEM。
5. 若对端节点拒绝参与，返回 DENIED。

最后，由于已经生成的纠缠对可能随着时间推移而退相干（失效），链接层也可能为此发送 EXPIRE 消息，通知上层该纠缠对已失效。

物理平台

在最后进入协议实现之前，我们还要考虑一下具体的物理实现平台。事实上，物理实现的限制对随后的协议实现有着不可忽视的影响。

我们前面已经讨论过，在量子通信和量子网络中 NV 色心是一个比较经济的物理实现方案，不需要超导平台的超低温和离子阱平台的高真空。事实上，在 Delft 大学的论文作者们能接触到的也只有 NV 色心平台。下面我们简要介绍一下 NV 色心平台，重点关注这一物理平台对协议设计产生的影响。

NV 色心是金刚石晶格中的一种缺陷结构，由一个替换了碳原子的氮原子和一个相邻的碳原子空缺组成（图a），结构的英文名 Nitrogen-Vacancy Center 也由此而来。在 NV 色心中，由电子的自旋量子态构成直接通信的量子比特，由邻近的碳原子核自旋量子态构成存储用的量子态。量子态通过外加电磁波进行控制。对 NV 色心感兴趣的读者可以进一步参考[4]。

我们更关心的是 NV 色心平台上的纠缠产生过程（见图c）。NV 色心的纠缠生成可以抽象为如下过程：首先，发射一束微波脉冲，触发 NV 色心中的量子跃迁过程，生成一个纠缠态。这一过程并非百分之百成功，而是以一定概率发生，概率约在千分之一量级（这是一个极小的概率！）。纠缠态由 NV 色心中的电子和一个光子构成，电子留在 NV 色心中，而光子则沿光纤传输，负责随后与 B 生成纠缠。

通信双方（A 与 B）同时进行这一过程，生成的光子沿光纤分别传播，来到连接了 A 与 B 的中继器 H。H 在收到来自 A 与 B 的光子之后进行纠缠交换（对纠缠交换的定义见前），从而废弃两个光子，在 A 处电子和 B 处电子之间建立量子纠缠，并通知 AB 双方纠缠已经成功建立。

由于 H 没有量子存储单元可以暂存光子，双方光子必须同时到达。这要求 A 和 B 之间必须建立非常精确的时间同步——精确到纳秒。这给物理层硬件的设计带来了很大挑战。

协议实现

物理层 为了让链路层可以建立在坚实的基础上，作者为链路层设计一个假象的物理层协议 MHP (Midpoint Heralding Protocal)，负责对物理设备进行基本的抽象，随后让链路层协议建立在 MHP 之上。作者设想 MHP 由专用硬件完成，类似经典计算机网络中网卡扮演的角色。为了满足精确的时间控制，MHP 有自己的时间周期，在每个周期中询问(polling)上层是否有纠缠生成需求，而不是被动等待中断。此外，由于苛刻的时间控制要求，MHP 也被设计得尽可能简化，不保存任何状态。

链路层 每个节点的链路层由协议（双方的约定）和一些其它组件构成。

• 一个同步的队列。一个容纳了所有来自上层的请求的队列，类似路由器中的出端队列。由前述讨论可知，链路双端必须同时触发量子过程才能生成纠缠对。因此，链路两端的节点必须持有一个内容相同的队列用于同步双方行为。这个分布式队列由经典通信进行传输和同步，且必须是确定性的，以保证双端的行为同步。
• 量子存储管理器。帮助链路层存储已经生成的纠缠对（中的量子比特）。
• 保真度估计装置。利用当前的物理参数和来自量子存储单元的信息，估计生成的纠缠对的保真度。
• 调度器。调度器负责为队列中的请求规划先后顺序，负责选出接下来将要完成的请求项。规划器必须是确定性的、不能依赖于概率，这是为了保证链路两端节点的行为一致。

EGP 协议。作者设计的链路层协议名为 EGP，即纠缠生成协议 (Engantlement Generation Protocol)。有了前面这么多内容的铺垫，协议的运作其实已经呼之欲出了，只需要把前面介绍的单元顺势组合即可。

EGP 的工作从收到上层的 CREATE 请求开始。首先，EGP 利用保真度估计装置估计硬件性能，并基于估计结果拒绝掉硬件无法完成的请求参数。然后，EGP 将请求加入队列并同步至对端节点。随后，调度器抽调出队列中的下一个可用请求项，指示 MHP 在下一个周期中生成纠缠，直到 MHP 成功返回。如果是 K 类（Keep，保持纠缠）请求，在这一步中还将使用量子存储管理器为生成的纠缠对规划量子存储空间。最后，EGP 得到 MHP 的「纠缠生成成功」返回后找到对应的请求项 ID（MHP的返回是异步的，类似磁盘控制器的异步返回）并向上层返回。最后返回的结果对不同的请求类型（直接测量还是保持纠缠）会稍有不同，返回参数中的拟合优度由保真度估计装置估计得到。

实证评估

有了纸面上的协议之后，还需要将协议真正实现、进行实验验证，才能证明协议 1)是否能正常工作 2)是否具有优秀的性能。

测试环境

论文作者采用了两种方式进行实证评估 (Evaluation)：在经典计算机上模拟量子网络，和在真正的 NV 色心物理平台上实验。首先，论文作者们在超算 Cartesius 上用量子网络模拟程序对他们提出的协议进行了模拟，得到了各种结果。随后，他们又在手头可用的 NV 色心硬件上进行了实验，与模拟数据进行了对比。模拟和实验的数据吻合地很好，共同印证数据的正确性。

值得一提的是，在 2022 年（论文实际上发表于 2019 年，但也没差几年:-）的今天，量子网络已经基本有了硬件实现，不再是只停留在纸面上的理论。作者们将他们可以使用的 NV 色心量子网络硬件称为”LAB”，即“实验室”用例。在 LAB 环境中，基于 NV 色心的节点 A 和 B 相距 2 米，分别用光纤与位于 AB 中间的中继站相连。实验环境的几个基本参数如下：俩节点间的传播时延为 9.7ns，而测量所需时间为 3.7 μs；每次触发保真度为$F=1-\alpha$纠缠态（物理层的一次微波脉冲触发纠缠态生成的过程）的成功率约为 $p_{\mathrm{succ}}=\alpha\cdot 10^{-3}$——其中 $\alpha$ 为可调参数。$\alpha$ 也展现了「纠缠生成成功率」和「生成纠缠态质量」之间的 tradeoff。

论文中提到的另一个量子网络用例是所谓的 QL2020。QL2020 中，计划将距离 25km 的两个欧洲城市用电信光缆建立连接，组成一个量子网络。由于距离较远，传播时延将达到 145μs。同时，由于光纤较长，光子在光纤中的损耗也将更大，为量子通讯带来更大的挑战。由于论文发表时 QL2020 尚未建成，论文作者只能基于基本参数在超算中对其进行模拟。作者也在超算中模拟了 LAB 的用例。

评估方法

作者在每个 MHP 周期以如下概率向 MHP 发送纠缠生成请求，请求$k$个纠缠对：

$$\text{Prob}=\frac{f_P\cdot p_{\mathrm{succ}}}{E\cdot k}$$

其中，$p_{\mathrm{succ}}$ 是每次微波脉冲能成功生成纠缠对的概率（见前）；$E$ 是 MHP 完成某类请求需要的周期数的期望，如下表所示；$k$是请求的纠缠对数量，在小于给定参数 $k_\max$ 的区间内随机选取；$f_P$ 是负载因子，用于研究不同负载下协议的性能表现。不同情况的具体参数见下表。

实验环境: 请求类型	LAB: MD	LAB: CK/NL	QL2020
MHP完成请求花费的周期数期望	1	1.1	~16

不同的负载测试情形	LOW	HIGH	ULTRA
对应的负载因子数值$f_P$	0.7	0.99	1.5

请求中，作者将最低保真度要求 $F_{\min}$ 设为0.64。

评估结果

论文中首先测试了仅有单类纠缠生成请求的情况。最终得到的各类结果中，生成纠缠对的质量（保真度）大约在0.7​上下，吞吐量大约在 6 对纠缠对/秒左右。与此相对，等待时间则糟糕得多：每一个生成纠缠对的请求至少要等待数秒才能被完成，在负载较重的情况下则可能要等待数十秒甚至上百秒才能被完成。具体数据我总结在如下表格中：

实验环境: 请求类型	LAB: MD	LAB: CK/NL	QL2020: MD	QL2020: CK/NL
平均保真度$F_{\mathrm{avg}}$	0.707~0.779	0.745~0.757	0.723~0.767	0.626~0.653

实验环境: 请求类型: 负载	LAB: CK/NL: HIGH/ULTRA	LAB: MD: HIGH/ULTRA	LAB: NL/CK: LOW	LAB: MD: LOW	QL2020: *:*
平均吞吐量$th_{\mathrm{avg}}$（纠缠对/秒）	6.05~6.47	6.51~7.094	4.44~4.72	4.86~5.22	约为LAB对应项的1/14

实验环境: 请求类型: 负载	QL2020: NL: LOW	QL2020: NL: HIGH	QL2020: NL: ULTRA
平均时延	10.97s	142.9s	521.5
实验环境: 请求类型: 负载	QL2020: MD: LOW	QL2020: MD: HIGH	QL2020: MD: ULTRA
平均时延	0.544s	3.318s	32.34s

可以看到，1)不同的情况下平均保真度基本不变，没有明显的规律 2)更高的负载带来了更高的吞吐量，但也使时延明显上升。

随后，作者又将多类纠缠生成请求 (NL/CK/MD) 混合起来，测量不同调度策略对延时的影响。结果如下图所示：

作者研究了两种不同的排队策略对延迟的影响：一种是简单的先入先出（First Come First Server, FCFS, 见上），另一种是加权队列（Weighted Fiar Queue, WFQ, 见下），NL 型请求优先级最高，CK 次之，NL 最次。可见，先入先出时不同类型的请求的延迟几乎一样。而采用加权队列时，虽然 NL 型请求的服务质量得到了保障，但 MD 类请求的延时却突破了天际，数次达到 100 秒以上。

在这一部分，我略去了很多具体的参数和结果的具体细节。如有问题，请参考原文。

对工作的评价

这篇论文给出了一个量子网络的链路层模型/协议，填补了学界目前研究的空白。虽然受限于量子硬件，对协议的验证二号分析还很初步，但仍然是一篇有价值的工作。

我认为论文的闪光点有如下几个方面：

首先，论文作者在设计链路层协议的时候充分考虑了量子网络硬件的局限性，例如量子态能被存储的时间很短、双方物理硬件需要很精确的时间对齐等等。这直接导致了同步队列等设计，也让协议对未来量子网络可能的硬件更有针对性。

然后，作者还在真正的量子网络硬件（NV 色心）上进行了实验，让整个工作建立在真实的物理实现和实验数据之上，而不仅仅是通过超算模拟。物理实验的结果与超算模拟的结果吻合地很好，这又反过来印证了超算的模拟结果，让超算的其它模拟结果也更可信。由于量子计算和通信的硬件并未成熟，许多领域内的论文偏向于采用超算模拟；而能采用真实的物理平台进行实验而不仅仅用超算模拟，无疑是一个加分项。

最后，论文的结构安排非常棒。先给出物理层概述，然后基于物理层限制提出协议设计的方向和限制，再到层间接口设计、链路层组件介绍，最后引入协议，逻辑非常流畅。有了前面的铺垫，在最后给出核心内容的时候我感到非常自然，几乎没有跳跃。

在优点之外，论文的研究结果也有一些不足，还有未来研究的空间。首先，受限于研究时有限的硬件条件，论文只考虑了 NV 色心平台上的一个真实量子链路，实验验证显得有些单薄。可以想见，待未来量子网络的技术更为成熟后，会有更多的论文研究这一链路层协议在不同硬件上（距离更长的链路、更复杂的量子网络拓扑、不同的硬件平台）上的表现。

其次，从实验数据上来看，这一链路层协议的时延较高。自向链路层请求纠缠对到链路层返回，少则数秒，多则上百秒；这一时间不论是对于计算机程序还是对于用户来说都有些太长了。观察分析结果可以发现极高的时延来自于排队，类似经典网络中的 Buffer Bloat 现象。也许后续的研究可以优化协议，缓解这一问题。

参考文献

此处参考文献是为了便于读者寻找资源和表明图品出处，格式并不标准，请见谅。

由于是论文笔记，因此引用原论文的地方在笔记中都没有标，只有引用其它论文会标注。

[1] 原论文 A Link Layer Protocol for Quantum Networks, Axel Dahlberg, Matthew Skrzypczyk, Tim Coopmans et. al., QuTech of Delft Univ. of Science and Technology, SIGCOMM‘19.

[2] 引用图片 Concurrent Entanglement Routing for Quantum Networks: Model and Designs, Shouqian Shi, Chen Qian, SIGCOMM‘20

[3] 提出纠缠交换的论文 Experimental entanglement swapping: entangling photons that never interacted, Jian-Wei Pan（潘建伟！）, Dik Bouwmeester, Harald Weinfurter, and Anton Zeilinger, Physical Review Letters (1998).

[4] NV色心综述 Diamond NV centers for quantum computing and quantum networks, Lilian Childress and Ronald Hanson, MRS Bulletin 38, 2 (2013), 134–138.