论文标题
量子局部模型中三色环的非平凡下限
Non-trivial lower bound for 3-coloring the ring in the quantum LOCAL model
论文作者
论文摘要
我们考虑了分布式计算的本地模型，其中在一轮通信中，每个节点都可以向其每个邻居发送任意大小的消息。众所周知，从经典上讲，$ n $ node环的圆形复杂性为$θ（\ log^*\！n）$。在通信是量子的情况下，只有琐碎的范围：至少必须进行一些交流。 我们研究了分布式算法，用于为仅执行单个单向通信的环着色。从经典上讲，已经知道这种有限的通信可以将所需颜色的数量从$θ（n）$减少到没有通信时，将所需颜色的数量减少到$θ（\ log n）$。在这项工作中，我们表明，在$ n $中，任何量子单一单向分布式算法的概率呈指数为小。
We consider the LOCAL model of distributed computing, where in a single round of communication each node can send to each of its neighbors a message of an arbitrary size. It is know that, classically, the round complexity of 3-coloring an $n$-node ring is $Θ(\log^*\!n)$. In the case where communication is quantum, only trivial bounds were known: at least some communication must take place. We study distributed algorithms for coloring the ring that perform only a single round of one-way communication. Classically, such limited communication is already known to reduce the number of required colors from $Θ(n)$, when there is no communication, to $Θ(\log n)$. In this work, we show that the probability of any quantum single-round one-way distributed algorithm to output a proper $3$-coloring is exponentially small in $n$.
