Quantum Complexity of Weighted Diameter and Radius in CONGEST Networks
IEEE Transactions on Information Theory · 2026-08 · 72 (8) · 5818-5829
DOI: 10.1109/tit.2026.3704289 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Information Theory, 2026-08. Verfasst von Xudong Wu und 1 weiteren Autor:innen. Die Arbeit nennt 26 Literaturangaben. Gefördert von: National Natural Science Foundation of China, Quantum Science and Technology-National Science and Technology Major Project, NSFC/Research Grants Council (RGC) Joint Research Scheme.
Abstract (Originalsprache)
This paper investigates the round complexity of computing the weighted diameter and radius of a graph in the quantum CONGEST model. We present a quantum algorithm that achieves a ( $1\boldsymbol {+} {o}$ (1))-approximation of the diameter and radius with a round complexity of $O$ ( ${n} ^{\text {3/4}}{D}^{\text {1/4}}$ ) up to logarithmic factors, where $n$ is the number of nodes and $D$ represents the unweighted diameter. This highlights the advantages of quantum communication over classical communication, as computing a (3/ $2\boldsymbol {-} \boldsymbol {\varepsilon } $ )-approximation of the diameter and radius in a classical CONGEST network requires near-linear in $n$ rounds according to Abboud et al. [DISC ’16], even when $D$ is constant. On the other hand, we establish a lower bound of $\boldsymbol {\Omega } $ ( ${n} ^{\text {2/3}}$ ) up to logarithmic factors, for (3/ $2\boldsymbol {-} \boldsymbol {\varepsilon } $ )-approximating the weighted diameter/radius in quantum CONGEST networks, even when ${D} \boldsymbol {=} \boldsymbol {\Theta } $ ( $\boldsymbol {\log {n}}$ ). Consequently, in quantum CONGEST networks, computing the weighted diameter and radius of graphs with small $D$ proves to be strictly harder than their unweighted counterparts, as compared to Le Gall and Magniez’s algorithm for unweighted diameter/radius, which runs in near-square-root- nD rounds [PODC ’16].
Förderung
- National Natural Science Foundation of China
- Quantum Science and Technology-National Science and Technology Major Project
- NSFC/Research Grants Council (RGC) Joint Research Scheme
- Natural Science Foundation of Jiangsu Province
- Fundamental and Interdisciplinary Disciplines Breakthrough Plan of the Ministry of Education of China
- “111 Center”
- Fundamental Research Funds for the Central Universities
Zitieren
APA
Wu, X., & Yao, P. (2026). Quantum Complexity of Weighted Diameter and Radius in CONGEST Networks. IEEE Transactions on Information Theory, 72(8), 5818-5829. https://doi.org/10.1109/tit.2026.3704289
Vancouver
Wu X, Yao P. Quantum Complexity of Weighted Diameter and Radius in CONGEST Networks. IEEE Transactions on Information Theory. 2026;72(8):5818-5829. doi:10.1109/tit.2026.3704289
BibTeX
@article{Wu2026,
author = {Wu, Xudong and Yao, Penghui},
title = {Quantum Complexity of Weighted Diameter and Radius in CONGEST Networks},
journal = {IEEE Transactions on Information Theory},
year = {2026},
volume = {72},
number = {8},
pages = {5818--5829},
doi = {10.1109/tit.2026.3704289}
}
EUVIMED