← Back to papers
Quantum Complexity of Weighted Diameter and Radius in CONGEST Networks
Xudong Wu, Penghui Yao·June 6, 2022·DOI: 10.1145/3519270.3538441
Computer SciencePhysics
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
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 Õ (min (n n9/10D3/10, n)) , where D denotes the unweighted diameter.