EUVIMEDEUVIMED entdecken
Crossref

Quantum Complexity of Weighted Diameter and Radius in CONGEST Networks

Xudong Wu, Penghui Yao

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →