The focus of this paper is on {\em quantum distributed} computation, where we investigate whether quantum communication can help in {\em speeding up} distributed network algorithms. Our main result is that for certain fundamental network problems such as minimum spanning tree, minimum cut, and shortest paths, quantum communication {\em does not} help in substantially speeding up distributed algorithms for these problems compared to the classical setting. In order to obtain this result, we extend the technique of Das Sarma et al. [SICOMP 2012] to obtain a uniform approach to prove non-trivial lower bounds for quantum distributed algorithms for several graph optimization (both exact and approximate versions) as well as verification problems, some of which are new even in the classical setting, e.g. tight randomized lower bounds for Hamiltonian cycle and spanning tree verification, answering an open problem of Das Sarma et al., and a lower bound in terms of the weight aspect ratio, matching the upper bounds of Elkin [STOC 2004]. Our approach introduces the {\em Server model} and {\em Quantum Simulation Theorem} which together provide a connection between distributed algorithms and communication complexity. The Server model is the standard two-party communication complexity model augmented with additional power; yet, most of the hardness in the two-party model is carried over to this new model. The Quantum Simulation Theorem carries this hardness further to quantum distributed computing. Our techniques, except the proof of the hardness in the Server model, require very little knowledge in quantum computing, and this can help overcoming a usual impediment in proving bounds on quantum distributed algorithms.
The focus of this paper is on {\em quantum distributed} computation, where we investigate whether quantum communication can help in {\em speeding up} distributed network algorithms. Our main result is that for certain fundamental network problems such as minimum spanning tree, minimum cut, and shortest paths, quantum communication {\em does not} help in substantially speeding up distributed algorithms for these problems compared to the classical setting. In order to obtain this result, we extend the technique of Das Sarma et al. [SICOMP 2012] to obtain a uniform approach to prove non-trivial lower bounds for quantum distributed algorithms for several graph optimization (both exact and approximate versions) as well as verification problems, some of which are new even in the classical setting, e.g. tight randomized lower bounds for Hamiltonian cycle and spanning tree verification, answering an open problem of Das Sarma et al., and a lower bound in terms of the weight aspect ratio, matching the upper bounds of Elkin [STOC 2004]. Our approach introduces the {\em Server model} and {\em Quantum Simulation Theorem} which together provide a connection between distributed algorithms and communication complexity. The Server model is the standard two-party communication complexity model augmented with additional power; yet, most of the hardness in the two-party model is carried over to this new model. The Quantum Simulation Theorem carries this hardness further to quantum distributed computing. Our techniques, except the proof of the hardness in the Server model, require very little knowledge in quantum computing, and this can help overcoming a usual impediment in proving bounds on quantum distributed algorithms.
We study lower bounds for quantum distributed computing, where a set of nodes (representing quantum computers) interconnected by an underlying network consisting of (bandwidth-restricted) links, communicate using quantum communication. Nodes have unlimited computational power and may share an unlimited number of entangled qubits. Our main contribution is a simple uniform technique for proving lower bounds for quantum distributed algorithms. In particular, we identify a new quantum communication model called the Server model which provides a connection between distributed algorithms and communication complexity: it is strong enough to capture the hardness of several distributed computing problems, while weak enough that several hard problems in two-party communication complexity remain hard; to this end, we identify a set of communication complexity techniques that can be carried over to the Server model, namely techniques based on nonlocal games. We show that these techniques serve as a fundamental tool in proving lower bounds in quantum distributed computing. The new techniques help us to prove several non-trivial quantum distributed lower bounds (which are the first-known quantum bounds for fundamental global problems such as minimum spanning tree, shortest paths etc.), some of which are new even in the classical setting. First, it allows us to show that all previous classical lower bounds of more than twenty verification and optimization graph problems in [Das Sarma et al., STOC 11] also hold in the quantum setting. Many of these bounds are tight, implying a large class of problems that do not gain an advantage from quantum effects. Our results also imply the following new results in the classical communication models: (1) the first randomized lower bounds for Hamiltonian cycle and spanning tree verification problems in both the distributed computing and the communication complexity model, answering the open problem of Das Sarma et al. and subsuming many bounds in [Babai, Frankl, and Simon, FOCS 96], and (2) the first lower bound that is tight for all weight aspect ratios, matching previous upper bounds of [Elkin, STOC 04]. Submitted for a Regular Presentation. The full version of this paper can be found as [15] at http://arxiv.org/abs/1207.5211. ∗Department of Computer Science, Ben-Gurion University, Beer-Sheva, 84105, Israel. E-mail: elkinm@cs.bgu.ac.il. †Division of Mathematical Sciences, Nanyang Technological University, Singapore 637371 & Centre for Quantum Technologies, National University of Singapore, Singapore 117543. E-mail: hklauck@gmail.com. Research at the Centre for Quantum Technologies is funded by the Singapore Ministry of Education and the National Research Foundation. ‡Division of Mathematical Sciences, Nanyang Technological University, Singapore 637371. Work partially done while at University of Vienna, Austria. E-mail: danupon@gmail.com. §Division of Mathematical Sciences, Nanyang Technological University, Singapore 637371 & Department of Computer Science, Brown University, Providence, RI 02912, USA. E-mail: gopalpandurangan@gmail.com. Supported in part by the following research grants: Nanyang Technological University grant M58110000, Singapore MOE Academic Research Fund (AcRF) Tier 2 grant MOE2010-T2-2-082, and a grant from the US-Israeli Binational Science Foundation (BSF).
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) for leader election, broadcast, and MST, and O~(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 O~(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.
In this thesis, I study how quantum computation and quantum communication can help large networks of computers to solve computational problems faster. I also connect the notion of locality between various models, including distributed quantum algorithms and online graph algorithms, and show that locality in online graph algorithms can be used to provide bounds for distributed quantum advantage. Towards proving distributed quantum advantage, I present the first family of LCL problems which shows a quantum advantage for distributed graph algorithms. Here LCLs, or Locally Checkable Labeling problems, are a family of graph problems described by a finite set of local constraints, and I mainly focus on them in this thesis. The models of distributed computing which this result separates are the classical LOCAL model and the quantum-LOCAL model. In both of these models, a network of computers exchanges messages in synchronous rounds, and the running time of the algorithm directly corresponds with locality, that is, how far the computers see in the network. In this thesis, I also introduce new models of computing that capture locality in stronger settings. Most notably, I introduce the online-LOCAL model which captures the locality of online graph algorithms, and show that it is, asymptotically, roughly as strong as the classical LOCAL model for solving LCL problems on rooted regular trees. I provide an online-LOCAL algorithm for finding a 3-coloring of a bipartite graph with lower locality than is possible in the classical LOCAL model, and show that the algorithm is tight. To draw things together, I show that quantum-LOCAL and online-LOCAL are indeed related to each other: any quantum-LOCAL algorithm can be simulated in the randomized online-LOCAL model. The converse does not hold in general, but an online-LOCAL algorithm solving an LCL problem in rooted, possibly non-regular, trees can be simulated in the classical LOCAL model—and thus in the quantum-LOCAL model—with an exponential cost in locality, putting indirectly a bound on the maximum possible attainable quantum advantage. Finally, I consider the sinkless orientation problem, which holds a central role in our understanding of the locality of LCL problems in the classical LOCAL model, and provide a simpler and more direct proof for its hardness using the supported LOCAL model. I also provide a simpler algorithm solving sinkless orientation in the SLOCAL model, which is a sequential version of the LOCAL model.
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(4n) communication bound. Considering k pairwise-connected processors (each with n/k data qubits and m ancillas), we prove the communication complexity satisfies O(max{4(1−1/k)n−m,n}) -- for example, O(2n) 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.
Computing set joins of two inputs is a common task in database theory. Recently, Van Gucht, Williams, Woodruff and Zhang [PODS 2015] considered the complexity of such problems in the natural model of (classical) two-party communication complexity and obtained tight bounds for the complexity of several important distributed set joins. In this paper we initiate the study of the *quantum* communication complexity of distributed set joins. We design a quantum protocol for distributed Boolean matrix multiplication, which corresponds to computing the composition join of two databases, showing that the product of two n×n Boolean matrices, each owned by one of two respective parties, can be computed with O(nℓ3/4) qubits of communication, where ℓ denotes the number of non-zero entries of the product. Since Van Gucht et al. showed that the classical communication complexity of this problem is Θ(nℓ), our quantum algorithm outperforms classical protocols whenever the output matrix is sparse. We also show a quantum lower bound and a matching classical upper bound on the communication complexity of distributed matrix multiplication over F2. Besides their applications to database theory, the communication complexity of set joins is interesting due to its connections to direct product theorems in communication complexity. In this work we also introduce a notion of *all-pairs* product theorem, and relate this notion to standard direct product theorems in communication complexity.