Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2206.02767 · IEEE Transactions on Information Theory

Quantum Complexity of Weighted Diameter and Radius in CONGEST Networks

Xudong Wu, Penghui Yao

Published Jul 20, 2022• 7 citations
arXivHTMLPDF

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.
DOI
10.1109/tit.2026.3704289

Related papers

Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks

François Le Gall, Frédéric Magniez

The computation of the diameter is one of the most central problems in distributed computation. In the standard CONGEST model, in which two adjacent nodes can exchange O(log n) bits per round (here n denotes the number of nodes of the network), it is known that exact computation of the diameter requires Ω(n) rounds, even in networks with constant diameter. In this paper we investigate quantum distributed algorithms for this problem in the quantum CONGEST model, where two adjacent nodes can exchange O(log n) quantum bits per round. Our main result is a O(√D )-round quantum distributed algorithm for exact diameter computation, where D denotes the diameter. This shows a separation between the computational power of quantum and classical algorithms in the CONGEST model. We also show an unconditional lower bound Ω(√ ) on the round complexity of any quantum algorithm computing the diameter, and furthermore show a tight lower bound Ω(√D ) for any distributed quantum algorithm in which each node can use only poly(log n) quantum bits of memory.

arXiv:1804.02917•ACM Symposium on Principles of Distributed Computing (PODC)•Jul 23, 2018•36 citations

Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks

François Le Gall, Frédéric Magniez

The computation of the diameter is one of the most central problems in distributed computation. In the standard CONGEST model, in which two adjacent nodes can exchange O(log n) bits per round (here n denotes the number of nodes of the network), it is known that exact computation of the diameter requires Ω(n) rounds, even in networks with constant diameter. In this paper we investigate quantum distributed algorithms for this problem in the quantum CONGEST model, where two adjacent nodes can exchange O(log n) quantum bits per round. Our main result is a O(√D )-round quantum distributed algorithm for exact diameter computation, where D denotes the diameter. This shows a separation between the computational power of quantum and classical algorithms in the CONGEST model. We also show an unconditional lower bound Ω(√ ) on the round complexity of any quantum algorithm computing the diameter, and furthermore show a tight lower bound Ω(√D ) for any distributed quantum algorithm in which each node can use only poly(log n) quantum bits of memory.

•Jan 14, 2019•0 citations

Quantum algorithms and lower bounds for eccentricity, radius, and diameter in undirected graphs

Adam Wesołowski, Jinge Bao

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.

arXiv:2502.20148•Feb 27, 2025•0 citations

Complexity of Eccentricities and All-Pairs Shortest Paths in the Quantum CONGEST Model

Changsheng Wang, Xudong Wu, Penghui Yao

Computing the distance parameters of a network, including the diameter, radius, eccentricities and the all-pairs shortest paths (APSP) is a central problem in distributed computing. This paper investigates the distance parameters in the quantum CONGEST models and establishes almost linear lower bounds on eccentricities and APSP, which match the classical upper bounds. Our results imply that there is not quantum speedup for these two problems. In contrast with the diameter and radius, exchanging quantum messages is able to save the communication when the networks have low diameters [F. L. Gall and F. Magniez, Sublinear-time quantum computation of the diameter in CONGEST networks, in Proc. 2018 ACM Symp. Principles of Distributed Computing (PODC), (2018), pp. 337–346; F. Magniez and A. Nayak, arXiv:2002.11795 ]. We obtain the lower bounds via a reduction from the two-way quantum communication complexity of the set intersection [A. A. Razborov, Izv. Math. 159 (2003)].

arXiv:2206.02766•SPIN•Aug 23, 2021•4 citations

Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model

Taisuke Izumi, François Le Gall, Frédéric Magniez

This paper considers the triangle finding problem in the CONGEST model of distributed computing. Recent works by Izumi and Le Gall (PODC'17), Chang, Pettie and Zhang (SODA'19) and Chang and Saranurak (PODC'19) have successively reduced the classical round complexity of triangle finding (as well as triangle listing) from the trivial upper bound $O(n)$ to $\tilde O(n^{1/3})$, where~$n$ denotes the number of vertices in the graph. In this paper we present a quantum distributed algorithm that solves the triangle finding problem in $\tilde O(n^{1/4})$ rounds in the CONGEST model. This gives another example of quantum algorithm beating the best known classical algorithms in distributed computing. Our result also exhibits an interesting phenomenon: while in the classical setting the best known upper bounds for the triangle finding and listing problems are identical, in the quantum setting the round complexities of these two problems are now $\tilde O(n^{1/4})$ and $\tilde Θ(n^{1/3})$, respectively. Our result thus shows that triangle finding is easier than triangle listing in the quantum CONGEST model.

arXiv:1908.11488•Aug 30, 2019•16 citations

Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model

Izumi, Taisuke, Le Gall, François, Frédéric Magniez

This paper considers the triangle finding problem in the CONGEST model of distributed computing. Recent works by Izumi and Le Gall (PODC'17), Chang, Pettie and Zhang (SODA'19) and Chang and Saranurak (PODC'19) have successively reduced the classical round complexity of triangle finding (as well as triangle listing) from the trivial upper bound O(n) to Õ(n^{1/3}), where n denotes the number of vertices in the graph. In this paper we present a quantum distributed algorithm that solves the triangle finding problem in Õ(n^{1/4}) rounds in the CONGEST model. This gives another example of quantum algorithm beating the best known classical algorithms in distributed computing. Our result also exhibits an interesting phenomenon: while in the classical setting the best known upper bounds for the triangle finding and listing problems are identical, in the quantum setting the round complexities of these two problems are now Õ(n^{1/4}) and Θ~(n^{1/3}), respectively. Our result thus shows that triangle finding is easier than triangle listing in the quantum CONGEST model.

Leibniz international proceedings in informatics•Jan 1, 2020•2 citations
The computation of the diameter is one of the most central problems in distributed computation. In the standard CONGEST model, in which two adjacent nodes can exchange O(log n) bits per round (here n denotes the number of nodes of the network), it is known that exact computation of the diameter requires Ω(n) rounds, even in networks with constant diameter. In this paper we investigate quantum distributed algorithms for this problem in the quantum CONGEST model, where two adjacent nodes can exchange O(log n) quantum bits per round. Our main result is a O(√D )-round quantum distributed algorithm for exact diameter computation, where D denotes the diameter. This shows a separation between the computational power of quantum and classical algorithms in the CONGEST model. We also show an unconditional lower bound Ω(√ ) on the round complexity of any quantum algorithm computing the diameter, and furthermore show a tight lower bound Ω(√D ) for any distributed quantum algorithm in which each node can use only poly(log n) quantum bits of memory.
The computation of the diameter is one of the most central problems in distributed computation. In the standard CONGEST model, in which two adjacent nodes can exchange O(log n) bits per round (here n denotes the number of nodes of the network), it is known that exact computation of the diameter requires Ω(n) rounds, even in networks with constant diameter. In this paper we investigate quantum distributed algorithms for this problem in the quantum CONGEST model, where two adjacent nodes can exchange O(log n) quantum bits per round. Our main result is a O(√D )-round quantum distributed algorithm for exact diameter computation, where D denotes the diameter. This shows a separation between the computational power of quantum and classical algorithms in the CONGEST model. We also show an unconditional lower bound Ω(√ ) on the round complexity of any quantum algorithm computing the diameter, and furthermore show a tight lower bound Ω(√D ) for any distributed quantum algorithm in which each node can use only poly(log n) quantum bits of memory.
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 O~(nm)\widetilde{O}(n\sqrt{m})O(nm​) time. Additionally, for the diameter, we present a quantum algorithm that approximates the diameter within a 2/32/32/3 ratio in O~(mn3/4)\widetilde{O}(\sqrt{m}n^{3/4})O(m​n3/4) time. We also establish quantum query lower bounds of Ω(nm)Ω(\sqrt{nm})Ω(nm​) for all the aforementioned problems through a reduction from the minima finding problem.
Computing the distance parameters of a network, including the diameter, radius, eccentricities and the all-pairs shortest paths (APSP) is a central problem in distributed computing. This paper investigates the distance parameters in the quantum CONGEST models and establishes almost linear lower bounds on eccentricities and APSP, which match the classical upper bounds. Our results imply that there is not quantum speedup for these two problems. In contrast with the diameter and radius, exchanging quantum messages is able to save the communication when the networks have low diameters [F. L. Gall and F. Magniez, Sublinear-time quantum computation of the diameter in CONGEST networks, in Proc. 2018 ACM Symp. Principles of Distributed Computing (PODC), (2018), pp. 337–346; F. Magniez and A. Nayak, arXiv:2002.11795 ]. We obtain the lower bounds via a reduction from the two-way quantum communication complexity of the set intersection [A. A. Razborov, Izv. Math. 159 (2003)].
This paper considers the triangle finding problem in the CONGEST model of distributed computing. Recent works by Izumi and Le Gall (PODC'17), Chang, Pettie and Zhang (SODA'19) and Chang and Saranurak (PODC'19) have successively reduced the classical round complexity of triangle finding (as well as triangle listing) from the trivial upper bound O(n)O(n)O(n) to O~(n1/3)\tilde O(n^{1/3})O~(n1/3), where~nnn denotes the number of vertices in the graph. In this paper we present a quantum distributed algorithm that solves the triangle finding problem in O~(n1/4)\tilde O(n^{1/4})O~(n1/4) rounds in the CONGEST model. This gives another example of quantum algorithm beating the best known classical algorithms in distributed computing. Our result also exhibits an interesting phenomenon: while in the classical setting the best known upper bounds for the triangle finding and listing problems are identical, in the quantum setting the round complexities of these two problems are now O~(n1/4)\tilde O(n^{1/4})O~(n1/4) and Θ~(n1/3)\tilde Θ(n^{1/3})Θ~(n1/3), respectively. Our result thus shows that triangle finding is easier than triangle listing in the quantum CONGEST model.
This paper considers the triangle finding problem in the CONGEST model of distributed computing. Recent works by Izumi and Le Gall (PODC'17), Chang, Pettie and Zhang (SODA'19) and Chang and Saranurak (PODC'19) have successively reduced the classical round complexity of triangle finding (as well as triangle listing) from the trivial upper bound O(n) to Õ(n^{1/3}), where n denotes the number of vertices in the graph. In this paper we present a quantum distributed algorithm that solves the triangle finding problem in Õ(n^{1/4}) rounds in the CONGEST model. This gives another example of quantum algorithm beating the best known classical algorithms in distributed computing. Our result also exhibits an interesting phenomenon: while in the classical setting the best known upper bounds for the triangle finding and listing problems are identical, in the quantum setting the round complexities of these two problems are now Õ(n^{1/4}) and Θ~(n^{1/3}), respectively. Our result thus shows that triangle finding is easier than triangle listing in the quantum CONGEST model.