Quantum advantage is well-established in centralized computing, where quantum algorithms can solve certain problems exponentially faster than classical ones. In the distributed setting, significant progress has been made in bandwidth-limited networks, where quantum distributed networks have shown computational advantages over classical counterparts. However, the potential of quantum computing in networks that are constrained only by large distances is not yet understood. We focus on the LOCAL model of computation (Linial, FOCS 1987), a distributed computational model where computational power and communication bandwidth are unconstrained, and its quantum generalization. In this brief survey, we summarize recent progress on the quantum-LOCAL model outlining its limitations with respect to its classical counterpart: we discuss emerging techniques, and highlight open research questions that could guide future efforts in the field.
Quantum advantage is well-established in centralized computing, where quantum algorithms can solve certain problems exponentially faster than classical ones. In the distributed setting, significant progress has been made in bandwidth-limited networks, where quantum distributed networks have shown computational advantages over classical counterparts. However, the potential of quantum computing in networks that are constrained only by large distances is not yet understood. We focus on the LOCAL model of computation (Linial, FOCS 1987), a distributed computational model where computational power and communication bandwidth are unconstrained, and its quantum generalization. In this brief survey, we summarize recent progress on the quantum-LOCAL model outlining its limitations with respect to its classical counterpart: we discuss emerging techniques, and highlight open research questions that could guide future efforts in the field.
There are two central models considered in (fault-free synchronous) distributed computing: the CONGEST model, in which communication channels have limited bandwidth, and the LOCAL model, in which communication channels have unlimited bandwidth. Very recently, Le Gall and Magniez (PODC 2018) showed the superiority of quantum distributed computing over classical distributed computing in the CONGEST model. In this work we show the superiority of quantum distributed computing in the LOCAL model: we exhibit two computational tasks that can be solved in a constant number of rounds in the quantum setting but require Omega(n) rounds in the classical (randomized) setting, where n denotes the size of the network.
We connect three distinct lines of research that have recently explored extensions of the classical LOCAL model of distributed computing: A. distributed quantum computing and non-signaling distributions [e.g. STOC 2024], B. finitely-dependent processes [e.g. Forum Math. Pi 2016], and C. locality in online graph algorithms and dynamic graph algorithms [e.g. ICALP 2023]. We prove new results on the capabilities and limitations of all of these models of computing, for locally checkable labeling problems (LCLs). We show that all these settings can be sandwiched between the classical LOCAL model and what we call the randomized online-LOCAL model. Our work implies limitations on the quantum advantage in the distributed setting, and we also exhibit a new barrier for proving tighter bounds. Our main technical results are these: 1. All LCL problems solvable with locality O(log⋆n) in the classical deterministic LOCAL model admit a finitely-dependent distribution with locality O(1). This answers an open question by Holroyd [2024], and also presents a new barrier for proving bounds on distributed quantum advantage using causality-based arguments. 2. In rooted trees, if we can solve an LCL problem with locality o(logloglogn) in the randomized online-LOCAL model (or any of the weaker models, such as quantum-LOCAL), we can solve it with locality O(log⋆n) in the classical deterministic LOCAL model. One of many implications is that in rooted trees, O(log⋆n) locality in quantum-LOCAL is not stronger than O(log⋆n) locality in classical LOCAL.
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.
The exploration of distributed quantum computing (DQC) represents a significant frontier in quantum information science, aiming to harness the unique properties of quantum mechanics to solve complex computational problems effectively. This paper discusses the diverse architectures and models that facilitate the distribution of quantum computing tasks across multiple quantum nodes, thereby addressing the limitations inherent in single quantum devices. DQC systems exploit the principles of superposition and entanglement to enhance computational capabilities beyond what classical computing systems can achieve. We examine various DQC architectures, including both quantum-classical hybrid systems and fully quantum distributed systems, highlighting their respective benefits and challenges. Key issues such as coherence, communication overhead, and error correction are discussed in detail, and we analyze specific use cases where DQC demonstrates superior performance relative to classical computing approaches, including optimization problems in logistics and finance, as well as quantum simulations for material science. Furthermore, we identify future research directions aimed at overcoming existing barriers to the practical implementation of DQC systems. By assessing the current landscape and future possibilities of DQC, this paper underscores the transformative potential of distributed quantum computing in various fields, paving the way for realizing more complex quantum algorithms and applications.
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).
Quantum computing and distributed systems may enter a mutually beneficial partnership in the future. On the one hand, it is much easier to build a number of small quantum computers rather than a single large one. On the other hand, the best results concerning some of the fundamental problems in distributed computing can potentially be dramatically improved upon by taking advantage of the superior resources and processing power that quantum mechanics offers. This survey has the purpose to highlight both of these benefits. We first review the current results regarding the implementation of arbitrary quantum algorithms on distributed hardware. We then discuss existing proposals for quantum solutions of leader election - a fundamental problem from distributed computing. Quantum mechanics allows leader election to be solved with no communication, provided that certain pre-shared entanglement is already in place. Further, an impossibility result from classical distributed computing is circumvented by the quantum solution of anonymous leader election - a unique leader is elected in finite time with certainty. Finally, we discuss the viability of these proposals from a practical perspective. Although, theoretically, distributed quantum computing looks promising, it is still unclear how to build quantum hardware and how to create and maintain robust large-scale entangled states. Moreover, it is not clear whether the costs of creating entangled states and working with them are smaller than the costs of existing classical solutions.