Quantum Complexity of Weighted Diameter and Radius in CONGEST Networks

DOI10.1145/3519270.3538441MaRDI QIDQ6120955zbMATH OpenOpenAlexWikidataFDO

Authors Xudong Wu, Penghui Yao

Publication date 26 March 2024

Published in Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2206.02767

zbMATH Keywords

congest modelquantum communication complexity

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Abstract: 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 $widetildeOleft(minleft{n}^{9/10}{D}^{3/10},nightight)$, 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 $widetildeOmega(n)$ rounds, even if $D$ is constant [Abboud, Censor-Hillel, and Khoury, DISC '16]. We also prove a lower bound of $widetildeOmega(n^{2/3})$ for $(3/2-varepsilon)$-approximating the weighted diameter/radius in quantum CONGEST networks, even if $D=Theta(logn)$. 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 $widetildeOleft(sqrtnDight)$-round algorithm for unweighted diameter/radius [PODC '18].

Cited in

(2)

• Distributed fast crash-tolerant consensus with nearly-linear quantum communication
• On the power of quantum distributed proofs

This page was built for publication: Quantum Complexity of Weighted Diameter and Radius in CONGEST Networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6120955)