论文标题
交通拥堵模型中分布式量子查询的框架
A Framework for Distributed Quantum Queries in the CONGEST Model
论文作者
论文摘要
量子通信模型是交货模型的变体，其中消息由$ o（\ log（n））$ Qubits组成。我们使用并行征服的概念提供了一个通用框架，用于在量子拥堵中实现量子查询算法。我们将框架应用于两个设置中的分布式量子查询：当数据通过网络分布时，并绘制网络定义输入的理论问题。第一个在拥挤中有点不寻常，但是我们的结果几乎直接遵循。第二个对于交通拥堵模型来说是更传统的，但是在这里，我们需要一些经典的交通拥堵步骤才能获得我们的结果。 在带有分布式数据的设置中，我们展示了一个网络如何使用$ \ tilde {o}（\ sqrt {kd}+d）$ ground安排$ k $日期之一的会议，并使用$ d $ the网络直径。我们还为元素独特性提供了算法：如果所有节点均包含$ k $数字的列表，他们可以在$ \ tilde o中找到重复（k^{2/3} d^{1/3}+d）$ rounds。我们还将分布式Deutsch-Jozsa问题的方案概括为从[Arxiv：Quant-PH/9802040]中考虑的两党设置到一般网络，从而在交货中的精确经典和精确的量子方案之间进行了新的分离。 当输入是网络结构本身时，我们几乎直接恢复了Le Gall和Magniez的$ O（\ sqrt {nd}）$圆直径计算算法[ARXIV：1804.02917]。我们还以相同数量的回合计算半径，并在$ \ tilde {o}（d+d+d^{3/2}/ε）$ rounds中给出$ε$ addive的平均偏心度。最后，我们为循环检测和周长计算的问题提供了量子加速。我们检测到图表是否具有最多的$ k $ in $ o（k+（kn）^{1/2-1/θ（k）}）$ rounds的长度周期。对于周长计算，我们给出了一个$ \ tilde {o}（g+（gn）^{1/2-1/θ（g）}）$ round算法，用于带有Girth $ G $的图形，超过了已知的经典下限。
The Quantum CONGEST model is a variant of the CONGEST model, where messages consist of $O(\log(n))$ qubits. We give a general framework for implementing quantum query algorithms in Quantum CONGEST, using the concept of parallel-queries. We apply our framework for distributed quantum queries in two settings: when data is distributed over the network, and graph theoretical problems where the network defines the input. The first is slightly unusual in CONGEST but our results follow almost directly. The second is more traditional for the CONGEST model but here we require some classical CONGEST steps to get our results. In the setting with distributed data, we show how a network can schedule a meeting in one of $k$ dates using $\tilde{O}(\sqrt{kD}+D)$ rounds, with $D$ the network diameter. We also give an algorithm for element distinctness: if all nodes together hold a list of $k$ numbers, they can find a duplicate in $\tilde O(k^{2/3}D^{1/3}+D)$ rounds. We also generalize the protocol for the distributed Deutsch-Jozsa problem from the two-party setting considered in [arXiv:quant-ph/9802040] to general networks, giving a novel separation between exact classical and exact quantum protocols in CONGEST. When the input is the network structure itself, we almost directly recover the $O(\sqrt{nD})$ round diameter computation algorithm of Le Gall and Magniez [arXiv:1804.02917]. We also compute the radius in the same number of rounds, and give an $ε$-additive approximation of the average eccentricity in $\tilde{O}(D+D^{3/2}/ε)$ rounds. Finally, we give quantum speedups for the problems of cycle detection and girth computation. We detect whether a graph has a cycle of length at most $k$ in $O(k+(kn)^{1/2-1/Θ(k)})$ rounds. For girth computation we give an $\tilde{O}(g+(gn)^{1/2-1/Θ(g)})$ round algorithm for graphs with girth $g$, beating the known classical lower bound.
