Quantum Distributed Algorithm for the All-Pairs Shortest Path Problem in the CONGEST-CLIQUE Model.
Quantum Distributed Algorithm for the All-Pairs Shortest Path Problem in the CONGEST-CLIQUE Model.
复制标题
CONGEST-CLIQUE 模型中全对最短路径问题的量子分布式算法。
DOI：
10.1145/3293611.3331628
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Taisuke Izumi,Francois Le Gall
中科院分区：
文献类型：
--
作者：
Ryota Eguchi;Naoki Kitamura;Taisuke Izumi;Taisuke Izumi,Francois Le Gall,Frederic Magniez;Yuval Emek,Noga Harlev,Taisuke Izumi;Yuichi Sudo,Fukuhito Ooshita,Taisuke Izumi,Hirotsugu Kakugawa,Toshimitsu Masuzawa;Taisuke Izumi,Francois Le Gall
全对最短路径问题是分布式计算中最核心的问题之一。在拥挤团模型中，n个节点通过在同步轮次中交换O(łog n)比特的消息在完全连接的网络上相互通信，最著名的APSP通用算法使用？(N1/3)轮次。打破这一障碍是分布式图算法中的一个根本挑战。本文首次研究了拥挤团模型中的量子分布式算法，其中节点可以交换O(Logn)个量子比特的消息，并且证明了这一障碍是可以被打破的：我们构造了拥挤团模型中权为多项式的有向图APSP的一个(N1/4)轮量子分布式算法。在量子环境中的这种加速比与标准拥塞模型的情况形成了对比，Elkin等人对标准拥塞模型进行了研究。(PODC 2014)表明量子通信并没有提供比经典通信更大的优势。我们的量子算法基于Vassilevska Williams和Williams(JACM 2018)发现的APSP和图形中负三角形的检测之间的关系。我们算法的量子部分利用了Le Gall和Magniez(PODC 2018)最近开发的量子分布式搜索框架。我们的主要技术贡献是一种方法，展示了如何在不引入拥塞的情况下并行实现多个量子搜索(图中的每条边一个)。
The All-Pairs Shortest Path problem (APSP) is one of the most central problems in distributed computation. In the CONGEST-CLIQUE model, in which n nodes communicate with each other over a fully connected network by exchanging messages of O(łog n) bits in synchronous rounds, the best known general algorithm for APSP uses Õ(n1/3) rounds. Breaking this barrier is a fundamental challenge in distributed graph algorithms. In this paper we investigate for the first time quantum distributed algorithms in the CONGEST-CLIQUE model, where nodes can exchange messages of O(log n) quantum bits, and show that this barrier can be broken: we construct a Õ(n1/4)-round quantum distributed algorithm for the APSP over directed graphs with polynomial weights in the CONGEST-CLIQUE model. This speedup in the quantum setting contrasts with the case of the standard CONGEST model, for which Elkin et al. (PODC 2014) showed that quantum communication does not offer significant advantages over classical communication.Our quantum algorithm is based on a relationship discovered by Vassilevska Williams and Williams (JACM 2018) between the APSP and the detection of negative triangles in a graph. The quantum part of our algorithm exploits the framework for quantum distributed search recently developed by Le Gall and Magniez (PODC 2018). Our main technical contribution is a method showing how to implement multiple quantum searches (one for each edge in the graph) in parallel without introducing congestions.