论文标题
量子分布式的集合在线上的不相交的复杂性
Quantum Distributed Complexity of Set Disjointness on a Line
论文作者
论文摘要
在线路上的设置脱节是在分布式计算方案中，在长度$ d $的路径上排列的分布式计算方案中的设置脱节问题。它是由Le Gall和Magniez（PODC 2018）引入的，目的是证明了Concest模型中任意网络直径的量子分布式复杂性的下限。但是，当处理器在路径的中间顶点上使用的本地内存仅由O $（\ log n）$ Qubits组成时，它们才能提供下限。我们证明了$ \widetildeΩ\ big的无条件下限（\ sqrt [3] {n d^2} + \ sqrt {n} \，\ big）$ rounds in set diss set diss set disse n set dis seet dis set dis noce diss in Condentness与$ d + 1 $ 1 $处理器。 The result gives us a new lower bound of $\widetildeΩ \big( \sqrt[3]{nδ^2}+\sqrt{n} \, \big)$ on the number of rounds required for computing the diameter $δ$ of any $n$-node network with quantum messages of size O$(\log n)$ in the CONGEST model. 我们在上面的分布式计算方案与查询复杂性的新模型之间绘制连接。我们使用的信息理论技术用于在线路上进行集合偏差，这也适用于此查询模型中的回合数。我们提供了一种在此查询模型中设置差异的算法，其圆形复杂性与上面所述的圆形下限相匹配，最多可达到一个多毛体因子。这为在线路上获得了更好的圆形下限提供了一个障碍。同时，它暗示了解决该问题更好的通信协议的可能性。
Set Disjointness on a Line is a variant of the Set Disjointness problem in a distributed computing scenario with $d+1$ processors arranged on a path of length $d$. It was introduced by Le Gall and Magniez (PODC 2018) for proving lower bounds on the quantum distributed complexity of computing the diameter of an arbitrary network in the CONGEST model. However, they were only able to provide a lower bound when the local memory used by the processors on the intermediate vertices of the path consists of O$( \log n)$ qubits for $n$-bit inputs. We prove an unconditional lower bound of $\widetildeΩ\big(\sqrt[3]{n d^2}+\sqrt{n} \, \big)$ rounds for Set Disjointness on a Line with $d + 1$ processors. The result gives us a new lower bound of $\widetildeΩ \big( \sqrt[3]{nδ^2}+\sqrt{n} \, \big)$ on the number of rounds required for computing the diameter $δ$ of any $n$-node network with quantum messages of size O$(\log n)$ in the CONGEST model. We draw a connection between the distributed computing scenario above and a new model of query complexity. The information-theoretic technique we use for deriving the round lower bound for Set Disjointness on a Line also applies to the number of rounds in this query model. We provide an algorithm for Set Disjointness in this query model with round complexity that matches the round lower bound stated above, up to a polylogarithmic factor. This presents a barrier for obtaining a better round lower bound for Set Disjointness on the Line. At the same time, it hints at the possibility of better communication protocols for the problem.
