Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2502.20148 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913710763671552 |
|---|---|
| author | Wesołowski, Adam Bao, Jinge |
| author_facet | Wesołowski, Adam Bao, Jinge |
| contents | The problems of computing eccentricity, radius, and diameter are fundamental to graph theory. These parameters are intrinsically defined based on the distance metric of the graph. In this work, we propose quantum algorithms for the diameter and radius of undirected, weighted graphs in the adjacency list model. The algorithms output diameter and radius with the corresponding paths in $\widetilde{O}(n\sqrt{m})$ time. Additionally, for the diameter, we present a quantum algorithm that approximates the diameter within a $2/3$ ratio in $\widetilde{O}(\sqrt{m}n^{3/4})$ time. We also establish quantum query lower bounds of $Ω(\sqrt{nm})$ for all the aforementioned problems through a reduction from the minima finding problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_20148 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Quantum algorithms and lower bounds for eccentricity, radius, and diameter in undirected graphs Wesołowski, Adam Bao, Jinge Quantum Physics Data Structures and Algorithms The problems of computing eccentricity, radius, and diameter are fundamental to graph theory. These parameters are intrinsically defined based on the distance metric of the graph. In this work, we propose quantum algorithms for the diameter and radius of undirected, weighted graphs in the adjacency list model. The algorithms output diameter and radius with the corresponding paths in $\widetilde{O}(n\sqrt{m})$ time. Additionally, for the diameter, we present a quantum algorithm that approximates the diameter within a $2/3$ ratio in $\widetilde{O}(\sqrt{m}n^{3/4})$ time. We also establish quantum query lower bounds of $Ω(\sqrt{nm})$ for all the aforementioned problems through a reduction from the minima finding problem. |
| title | Quantum algorithms and lower bounds for eccentricity, radius, and diameter in undirected graphs |
| topic | Quantum Physics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2502.20148 |