Quantum Complexity of Weighted Diameter and Radius in CONGEST Networks
share
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 O(min{n^9/10D^3/10,n}), where D denotes the unweighted diameter. This exhibits the advantages of quantum communication over classical communication since computing a (3/2-ε)-approximation of the diameter and radius in a classical CONGEST network takes Ω(n) rounds, even if D is constant [Abboud, Censor-Hillel, and Khoury, DISC '16]. We also prove a lower bound of Ω(n^2/3) for (3/2-ε)-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 O(√(nD))-round algorithm for unweighted diameter/radius [PODC '18].
READ FULL TEXT