


























This paper studies the round complexity of computing the weighted diameter and radius of a graph in the quantum CONGEST model. We present a quantum algorithm that $(1+o(1))$-approximates the diameter and radius with round complexity $\widetilde O\left(\min\left\{n^{9/10}D^{3/10},n\right\}\right)$, where $D$ denotes the unweighted diameter. This exhibits the advantages of quantum communication over classical communication since computing a $(3/2-\varepsilon)$-approximation of the diameter and radius in a classical CONGEST network takes $\widetildeΩ(n)$ rounds, even if $D$ is constant [Abboud, Censor-Hillel, and Khoury, DISC '16]. We also prove a lower bound of $\widetildeΩ(n^{2/3})$ for $(3/2-\varepsilon)$-approximating the weighted diameter/radius in quantum CONGEST networks, even if $D=Θ(\log n)$. Thus, in quantum CONGEST networks, computing weighted diameter and weighted radius of graphs with small $D$ is strictly harder than unweighted ones due to Le Gall and Magniez's $\widetilde O\left(\sqrt{nD}\right)$-round algorithm for unweighted diameter/radius [PODC '18].
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。