Back to Search
Start Over
Quantum Complexity of Weighted Diameter and Radius in CONGEST Networks
- Source :
- Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing (PODC 2022), pp. 120-130, 2022
- Publication Year :
- 2022
-
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 $\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\Omega(n)$ rounds, even if $D$ is constant [Abboud, Censor-Hillel, and Khoury, DISC '16]. We also prove a lower bound of $\widetilde\Omega(n^{2/3})$ for $(3/2-\varepsilon)$-approximating the weighted diameter/radius in quantum CONGEST networks, even if $D=\Theta(\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].<br />Comment: 24 pages. accepted by PODC 2022
- Subjects :
- Computer Science - Distributed, Parallel, and Cluster Computing
Quantum Physics
Subjects
Details
- Database :
- arXiv
- Journal :
- Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing (PODC 2022), pp. 120-130, 2022
- Publication Type :
- Report
- Accession number :
- edsarx.2206.02767
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1145/3519270.3538441