论文笔记| Concurrent Entanglement Routing for Quantum Networks: Model and Designs

Brief

• Authors: Shouqian Shi and Chen Qian
• University of California
• SIGCOMM 2020

量子互联网中的路由问题。现有的量子互联网模型中，一个典型的应用场景就是秘钥分发，也就是两个节点之间通过量子信道来进行秘密共享，这样能够实现信息论上的安全。但是基于量子的秘钥分发通常是基于纠缠或者是单光子的，有一个问题是纠缠对的传输距离短、持续时间短，因此相聚很远的节点之间就很难进行直接的纠缠分发。

现有的量子网络中的做法是使用一个可信中继来进行传输距离的扩展（比如京沪量子干线中有济南和合肥的可信中继），可是这个可信中继的引入使得网络的安全性似乎不那么强了。为了解决这种问题，一个新的被称为 Swapping 的量子纠缠操作被引入。Swapping 是指将两个纠缠对耦合在一起，形成一个长距离纠缠对的操作。这样只需要可信中继和通信双方分别建立量子纠缠对，而后进行一次 Swapping 操作即可实现通信双方的纠缠对的构造；此时，可信中继也无法干预秘钥分发，从而保障了系统的安全。

一个量子互联网场景下，任意两个量子节点之间都可以进行秘钥交换，只需要进行多次 Swapping 操作即可。但是，每一个量子节点的能力是有限的：量子纠缠对的信道数量是有限的、量子比特存储能力是有限的、量子纠缠对的持续时间是有限的。在这种情况下，路由和资源分配就变成了一个问题。怎么样选取中间节点，使得网络的吞吐量最大化呢？

文章将秘钥分发离散称为若干的周期进行，每个周期分为四阶段进行：

1. 网络接收需要进行秘钥分发的通信双方的申请，也就说接收多个 SD 对（Source-Destination）
2. 网络根据拓扑结构和 SD 对进行选路，选择若干个候选路径
3. 网络根据选路情况建立纠缠对（有概率失败）
4. 网络根据局部纠缠对的建立情况，来进行 Swapping 操作，从而构成完整的量子信道建立。

文章提出了两种具体的路由算法，分别是：

1. Q-PASS，这种算法在四阶段前引入了一个离线阶段，预先计算出了每两个通信双方之间的可能路径，而后在第二阶段进行竞争性地选路，选取优先级最高的若干条路径，之后进行量子纠缠的建立。
2. Q-CAST，这种路由算法没有离线阶段，每次根据输入的 SD 对来及时的计算可能的路径。而后，使用一个贪婪算法（扩展的迪姐斯特拉算法）进行主要路径和保留路径的选取，选取一条路径后直接分配所需要的资源，尽力而为的建立连接。

作者进行了模拟实验，发现 Q-CAST 相比已有算法有更好的吞吐量、鲁棒性和扩展性。