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:2602.15529

Tight Communication Bounds for Distributed Algorithms in the Quantum Routing Model

Fabien Dufoulon, Frédéric Magniez, Gopal Pandurangan

quant-phcs.DCSubmitted Feb 17, 2026• Announced Feb 18, 2026• 0 citations• Revised Mar 2, 2026 (v2)
v1 · Feb 17, 2026v2 · Mar 2, 2026
arXivHTMLPDF

Abstract

We present new distributed quantum algorithms for fundamental distributed computing problems, namely, leader election, broadcast, Minimum Spanning Tree (MST), and Breadth-First Search (BFS) tree, in arbitrary networks. These algorithms are (essentially) optimal with respect to their communication (message) complexity in the {\em quantum routing model} introduced in [PODC 2025]. The message complexity of our algorithms is $\tilde{O}(n)$ for leader election, broadcast, and MST, and $\tilde{O}(\sqrt{mn})$ for BFS ($n$ and $m$ are the number of nodes and edges of the network, respectively). These message bounds are nearly tight in the quantum routing model since we show almost matching corresponding quantum message lower bounds. Our results significantly improve on the prior work of [PODC 2025], who presented distributed quantum algorithms under the same model that had a message complexity of $\tilde{O}(\sqrt{mn})$ for leader election. Our algorithms demonstrate the significant communication advantage that quantum routing has over classical in distributed computing, since $Ω(m)$ is a well-established classical message lower bound for leader election, broadcast, MST, and BFS that applies even to randomized Monte-Carlo algorithms [JACM 2015]. Thus, our quantum algorithms can, in general, give a quadratic advantage in the communication cost for these fundamental problems. A main technical tool we use to design our distributed algorithms is quantum walks based on electric networks. We posit a framework for using quantum walks in the distributed setting to design communication-efficient distributed quantum algorithms. Our framework can be used as a black box to significantly reduce communication costs and may be of independent interest. Additionally, our lower-bound technique for establishing distributed quantum message lower bounds can also be applied to other problems.

Comments
Minor modifications compared to v1, intended to provide additional detail for the lower bounds. To prove the Query Complexity to Message Complexity Reduction Lemma (Lemma 7.3), we emphasize that we consider a slight variation of the adjacency array model with stronger queries

Related papers

Exponential Quantum Advantage for Message Complexity in Distributed Algorithms

François Le Gall, Maël Luce, Marchand, Joseph +1 more

We investigate how much quantum distributed algorithms can outperform classical distributed algorithms with respect to the message complexity (the overall amount of communication used by the algorithm). Recently, Dufoulon, Magniez and Pandurangan (PODC 2025) have shown a polynomial quantum advantage for several tasks such as leader election and agreement. In this paper, we show an exponential quantum advantage for a fundamental task: routing information between two specified nodes of a network. We prove that for the family of ``welded trees" introduced in the seminal work by Childs, Cleve, Deotto, Farhi, Gutmann and Spielman (STOC 2003), there exists a quantum distributed algorithm that transfers messages from the entrance of the graph to the exit with message complexity exponentially smaller than any classical algorithm. Our quantum algorithm is based on the recent "succinct" implementation of quantum walks over the welded trees by Li, Li and Luo (SODA 2024). Our classical lower bound is obtained by ``lifting'' the lower bound from Childs, Cleve, Deotto, Farhi, Gutmann and Spielman (STOC 2003) from query complexity to message complexity.

arXiv:2510.01657•Oct 2, 2025•0 citations

Brief Announcement: Exponential Quantum Advantage for Message Complexity in Distributed Algorithms

François Le Gall, Maël Luce, Joseph Marchand +1 more

We investigate how much quantum distributed algorithms can outperform classical distributed algorithms with respect to the message complexity (the overall amount of communication used by the algorithm). Recently, Dufoulon, Magniez and Pandurangan (PODC 2025) have shown a polynomial quantum advantage for several tasks such as leader election and agreement. In this paper, we show an exponential quantum advantage for a fundamental task: routing information between two specified nodes of a network. We prove that for the family of “welded trees” introduced in the seminal work by Childs, Cleve, Deotto, Farhi, Gutmann and Spielman (STOC 2003), there exists a quantum distributed algorithm that transfers messages from the entrance of the graph to the exit with message complexity exponentially smaller than any classical algorithm. Our quantum algorithm is based on the recent “succinct” implementation of quantum walks over the welded trees by Li, Li and Luo (SODA 2024). Our classical lower bound is obtained by “lifting” the lower bound from Childs, Cleve, Deotto, Farhi, Gutmann and Spielman (STOC 2003) from query complexity to message complexity. A full version of this paper can be found on arXiv [21].

ACM Symposium on Principles of Distributed Computing (PODC)•Jul 1, 2026•0 citations

Quantum Communication Advantage for Leader Election and Agreement

Fabien Dufoulon, Frédéric Magniez, Gopal Pandurangan

This work focuses on understanding the quantum message complexity of two central problems in distributed computing, namely, leader election and agreement in synchronous message-passing communication networks. We show that quantum communication gives an advantage for both problems by presenting quantum distributed algorithms that significantly outperform their respective classical counterparts under various network topologies.

arXiv:2502.07416•ACM Symposium on Principles of Distributed Computing (PODC)•Jun 13, 2025•1 citation

Quantum Distributed Algorithms for Approximate Steiner Trees and Directed Minimum Spanning Trees

Phillip Kerger, David E. Bernal Neira, Zoe Gonzalez Izquierdo +1 more

We present two algorithms in the Quantum CONGEST-CLIQUE model of distributed computation that succeed with high probability; one for producing an approximately optimal Steiner Tree, and one for producing an exact directed minimum spanning tree, each of which uses$\overline{O}(n^{1/4})$rounds of communication and$\tilde{O}(n^{9/4})$messages, achieving a lower asymptotic round and message complexity than any known algorithms in the classical CONGEST-CLIQUE model. At a high level, we achieve these results by combining classical algorithmic frameworks with quantum subroutines. Additionally, we characterize the constants and logarithmic factors involved in our algorithms as well as related classical algorithms, otherwise obscured by$\overline{O}$notation, revealing that advances are needed to render both the quantum and classical algorithms practical.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•2 citations

The Quantum Message Complexity of Distributed Wake-Up with Advice

Peter Robinson, Ming Ming Tan

We consider the distributed wake-up problem with advice, where nodes are equipped with initial knowledge about the network at large. After the adversary awakens a subset of nodes, an oracle computes a bit string (``the advice'') for each node, and the goal is to wake up all sleeping nodes efficiently. We present the first upper and lower bounds on the message complexity for wake-up in the quantum routing model, introduced by Dufoulon, Magniez, and Pandurangan (PODC 2025). In more detail, we give a distributed advising scheme that, given $α$ bits of advice per node, wakes up all nodes with a message complexity of $O( \sqrt{\frac{n^3}{2^{\max\{\lfloor (α-1)/2 \rfloor},0\}}}\cdot\log n )$ with high probability. Our result breaks the $Ω( \frac{n^2}{2^α} )$ barrier known for the classical port numbering model in sufficiently dense graphs. To complement our algorithm, we give a lower bound on the message complexity for distributed quantum algorithms: By leveraging a lower bound result for the single-bit descriptor problem in the query complexity model, we show that wake-up has a quantum message complexity of $Ω( n^{3/2} )$ without advice, which holds independently of how much time we allow. In the setting where an adversary decides which nodes start the algorithm, most graph problems of interest implicitly require solving wake-up, and thus the same lower bound also holds for other fundamental problems such as single-source broadcast and spanning tree construction.

quant-pharXiv:2602.05801•Feb 6, 2026•0 citations

Communication Complexity of Distributed Unitary Synthesis

Longcheng Li, Xiaoming Sun, Jialin Zhang +1 more

We study space-bounded communication complexity for unitary implementation in distributed quantum processors, where we restrict the number of qubits per processor to ensure practical relevance and technical non-triviality. We model distributed quantum processors using distributed quantum circuits with nonlocal two-qubit gates, defining the distributed communication complexity of a unitary as the minimum number of such nonlocal gates required for its realization, up to permutations of data qubit positions. Our contributions are twofold. First, for general $n$-qubit unitaries, we improve upon the trivial $O(4^n)$ communication bound. Considering $k$ pairwise-connected processors (each with $n/k$ data qubits and $m$ ancillas), we prove the communication complexity satisfies $O\left(\max\{4^{(1-1/k)n - m}, n\}\right)$ -- for example, $O(2^n)$ when $m=0$ and $k=2$ -- and establish the tightness of this upper bound. We further extend the analysis to approximation models and general network topologies. Second, for special unitaries, we show that both the Quantum Fourier Transform (QFT) and Clifford circuits admit linear upper bounds on communication complexity in the exact model, outperforming the trivial quadratic bounds applicable to these cases. In the approximation model, QFT's communication complexity reduces drastically from linear to logarithmic, while Clifford circuits retain a linear lower bound. These results offer fundamental insights for optimizing communication in distributed quantum unitary implementation, advancing the feasibility of large-scale DQC systems.

quant-pharXiv:2511.04250•IEEE Transactions on Information Theory•Nov 7, 2025•0 citations
We present new distributed quantum algorithms for fundamental distributed computing problems, namely, leader election, broadcast, Minimum Spanning Tree (MST), and Breadth-First Search (BFS) tree, in arbitrary networks. These algorithms are (essentially) optimal with respect to their communication (message) complexity in the {\em quantum routing model} introduced in [PODC 2025]. The message complexity of our algorithms is O~(n)\tilde{O}(n)O~(n) for leader election, broadcast, and MST, and O~(mn)\tilde{O}(\sqrt{mn})O~(mn​) for BFS (nnn and mmm are the number of nodes and edges of the network, respectively). These message bounds are nearly tight in the quantum routing model since we show almost matching corresponding quantum message lower bounds.
Our results significantly improve on the prior work of [PODC 2025], who presented distributed quantum algorithms under the same model that had a message complexity of O~(mn)\tilde{O}(\sqrt{mn})O~(mn​) for leader election. Our algorithms demonstrate the significant communication advantage that quantum routing has over classical in distributed computing, since Ω(m)Ω(m)Ω(m) is a well-established classical message lower bound for leader election, broadcast, MST, and BFS that applies even to randomized Monte-Carlo algorithms [JACM 2015]. Thus, our quantum algorithms can, in general, give a quadratic advantage in the communication cost for these fundamental problems.
A main technical tool we use to design our distributed algorithms is quantum walks based on electric networks. We posit a framework for using quantum walks in the distributed setting to design communication-efficient distributed quantum algorithms. Our framework can be used as a black box to significantly reduce communication costs and may be of independent interest. Additionally, our lower-bound technique for establishing distributed quantum message lower bounds can also be applied to other problems.
We investigate how much quantum distributed algorithms can outperform classical distributed algorithms with respect to the message complexity (the overall amount of communication used by the algorithm). Recently, Dufoulon, Magniez and Pandurangan (PODC 2025) have shown a polynomial quantum advantage for several tasks such as leader election and agreement. In this paper, we show an exponential quantum advantage for a fundamental task: routing information between two specified nodes of a network. We prove that for the family of ``welded trees" introduced in the seminal work by Childs, Cleve, Deotto, Farhi, Gutmann and Spielman (STOC 2003), there exists a quantum distributed algorithm that transfers messages from the entrance of the graph to the exit with message complexity exponentially smaller than any classical algorithm. Our quantum algorithm is based on the recent "succinct" implementation of quantum walks over the welded trees by Li, Li and Luo (SODA 2024). Our classical lower bound is obtained by ``lifting'' the lower bound from Childs, Cleve, Deotto, Farhi, Gutmann and Spielman (STOC 2003) from query complexity to message complexity.
We investigate how much quantum distributed algorithms can outperform classical distributed algorithms with respect to the message complexity (the overall amount of communication used by the algorithm). Recently, Dufoulon, Magniez and Pandurangan (PODC 2025) have shown a polynomial quantum advantage for several tasks such as leader election and agreement. In this paper, we show an exponential quantum advantage for a fundamental task: routing information between two specified nodes of a network. We prove that for the family of “welded trees” introduced in the seminal work by Childs, Cleve, Deotto, Farhi, Gutmann and Spielman (STOC 2003), there exists a quantum distributed algorithm that transfers messages from the entrance of the graph to the exit with message complexity exponentially smaller than any classical algorithm. Our quantum algorithm is based on the recent “succinct” implementation of quantum walks over the welded trees by Li, Li and Luo (SODA 2024). Our classical lower bound is obtained by “lifting” the lower bound from Childs, Cleve, Deotto, Farhi, Gutmann and Spielman (STOC 2003) from query complexity to message complexity. A full version of this paper can be found on arXiv [21].
We present two algorithms in the Quantum CONGEST-CLIQUE model of distributed computation that succeed with high probability; one for producing an approximately optimal Steiner Tree, and one for producing an exact directed minimum spanning tree, each of which usesO‾(n1/4)\overline{O}(n^{1/4})O(n1/4)rounds of communication andO~(n9/4)\tilde{O}(n^{9/4})O~(n9/4)messages, achieving a lower asymptotic round and message complexity than any known algorithms in the classical CONGEST-CLIQUE model. At a high level, we achieve these results by combining classical algorithmic frameworks with quantum subroutines. Additionally, we characterize the constants and logarithmic factors involved in our algorithms as well as related classical algorithms, otherwise obscured byO‾\overline{O}Onotation, revealing that advances are needed to render both the quantum and classical algorithms practical.
We consider the distributed wake-up problem with advice, where nodes are equipped with initial knowledge about the network at large. After the adversary awakens a subset of nodes, an oracle computes a bit string (``the advice'') for each node, and the goal is to wake up all sleeping nodes efficiently. We present the first upper and lower bounds on the message complexity for wake-up in the quantum routing model, introduced by Dufoulon, Magniez, and Pandurangan (PODC 2025). In more detail, we give a distributed advising scheme that, given ααα bits of advice per node, wakes up all nodes with a message complexity of O(n32max⁡{⌊(α−1)/2⌋,0}⋅log⁡n)O( \sqrt{\frac{n^3}{2^{\max\{\lfloor (α-1)/2 \rfloor},0\}}}\cdot\log n )O(2max{⌊(α−1)/2⌋,0}n3​​⋅logn) with high probability. Our result breaks the Ω(n22α)Ω( \frac{n^2}{2^α} )Ω(2αn2​) barrier known for the classical port numbering model in sufficiently dense graphs. To complement our algorithm, we give a lower bound on the message complexity for distributed quantum algorithms: By leveraging a lower bound result for the single-bit descriptor problem in the query complexity model, we show that wake-up has a quantum message complexity of Ω(n3/2)Ω( n^{3/2} )Ω(n3/2) without advice, which holds independently of how much time we allow. In the setting where an adversary decides which nodes start the algorithm, most graph problems of interest implicitly require solving wake-up, and thus the same lower bound also holds for other fundamental problems such as single-source broadcast and spanning tree construction.
We study space-bounded communication complexity for unitary implementation in distributed quantum processors, where we restrict the number of qubits per processor to ensure practical relevance and technical non-triviality. We model distributed quantum processors using distributed quantum circuits with nonlocal two-qubit gates, defining the distributed communication complexity of a unitary as the minimum number of such nonlocal gates required for its realization, up to permutations of data qubit positions. Our contributions are twofold. First, for general nnn-qubit unitaries, we improve upon the trivial O(4n)O(4^n)O(4n) communication bound. Considering kkk pairwise-connected processors (each with n/kn/kn/k data qubits and mmm ancillas), we prove the communication complexity satisfies O(max⁡{4(1−1/k)n−m,n})O\left(\max\{4^{(1-1/k)n - m}, n\}\right)O(max{4(1−1/k)n−m,n}) -- for example, O(2n)O(2^n)O(2n) when m=0m=0m=0 and k=2k=2k=2 -- and establish the tightness of this upper bound. We further extend the analysis to approximation models and general network topologies. Second, for special unitaries, we show that both the Quantum Fourier Transform (QFT) and Clifford circuits admit linear upper bounds on communication complexity in the exact model, outperforming the trivial quadratic bounds applicable to these cases. In the approximation model, QFT's communication complexity reduces drastically from linear to logarithmic, while Clifford circuits retain a linear lower bound. These results offer fundamental insights for optimizing communication in distributed quantum unitary implementation, advancing the feasibility of large-scale DQC systems.