Classical and Quantum Distributed Algorithms for the Survivable Network Design Problem

我们研究了可存活网络设计问题（SNDP），有时也称为广义斯坦纳问题的分布式经典和量子方法。这些问题概括了许多有趣的复杂图形问题，例如旅行推销员问题、斯坦纳树问题和k连通网络问题。据我们所知，尚未在我们考虑的分布式环境中制定过SNDP的经典或量子算法。我们描述了一些启发式算法，用于解决一般问题，但在SNDP的特定参数化下给出了具体的近似界限，这些界限特别适用于SNDP概括的三个问题。我们使用了经典的集中式算法框架，该框架最初在（Goemans＆Bertsimas 1993）中进行了研究，并提供了其分布式实现。值得注意的是，我们通过利用该框架中的量子最短路径计算获得了渐近量子加速，这扩展了（Kerger等人2023年）的最新工作。这些结果引发了一个问题，即是否存在应用规模实例的问题，经典模型和量子模型之间存在分离。

分布式经典和量子方法在可生存网络设计问题上的应用

在经典算法框架下实现分布式算法，并且利用量子最短路径计算实现了渐近量子加速。

论文提出了一种分布式算法框架，并且在该框架下实现了可生存网络设计问题的解决方案。论文还利用量子最短路径计算实现了渐近量子加速。实验结果表明，该算法在特定参数化下能够得到具体的近似界限，这个结果对于可生存网络设计问题的三个特殊情况（旅行推销员问题、斯坦纳树问题和k连通网络问题）都成立。该研究成果还引发了一个问题：是否存在经典和量子模型在应用规模实例上的区别。

相关研究包括 Goemans & Bertsimas 1993 和 Kerger等人在2023年的最新工作。