Recently, several claims have been made that certain fundamental problems of distributed computing, including Leader Election and Distributed Consensus, begin to admit feasible and efficient solutions when the model of distributed computation is extended so as to apply quantum processing. This has been achieved in one of two distinct ways: (1) by initializing the system in a quantum entangled state, and/or (2) by applying quantum communication channels. In this paper, we explain why some of these prior claims are misleading, in the sense that they rely on changes to the model unrelated to quantum processing. On the positive side, we consider the aforementioned quantum extensions when applied to Linial's well-established LOCAL model of distributed computing. For both types of extensions, we put forward valid proof-of-concept examples of distributed problems whose round complexity is in fact reduced through genuinely quantum effects, in contexts which do not depend on the anonymity of nodes. Finally, we show that even the quantum variants of the LOCAL model have non-trivial limitations, captured by a very simple (purely probabilistic) notion which we call "physical locality" (PLOCAL). While this is strictly weaker than the "computational locality" of the classical LOCAL model, it nevertheless implies that for many distributed combinatorial optimization problems, such as Maximal Independent Set, the best currently known lower time bounds cannot be broken by applying quantum processing, in any conceivable way.
Recently, several claims have been made that certain fundamental problems of distributed computing, including Leader Election and Distributed Consensus, begin to admit feasible and efficient solutions when the model of distributed computation is extended so as to apply quantum processing. This has been achieved in one of two distinct ways: (1) by initializing the system in a quantum entangled state, and/or (2) by applying quantum communication channels. In this paper, we explain why some of these prior claims are misleading, in the sense that they rely on changes to the model unrelated to quantum processing. On the positive side, we consider the aforementioned quantum extensions when applied to Linial's well-established LOCAL model of distributed computing. For both types of extensions, we put forward valid proof-of-concept examples of distributed problems whose round complexity is in fact reduced through genuinely quantum effects, in contexts which do not depend on the anonymity of nodes. Finally, we show that even the quantum variants of the LOCAL model have non-trivial limitations, captured by a very simple (purely probabilistic) notion which we call "physical locality" (PLOCAL). While this is strictly weaker than the "computational locality" of the classical LOCAL model, it nevertheless implies that for many distributed combinatorial optimization problems, such as Maximal Independent Set, the best currently known lower time bounds cannot be broken by applying quantum processing, in any conceivable way.
In this work, we give two results that put new limits on distributed quantum advantage in the context of the LOCAL model of distributed computing: 1) We show that there is no distributed quantum advantage for any linear program. Put otherwise, if there is a quantum-LOCAL algorithm 𝒜 that finds an α-approximation of some linear optimization problem Π in T communication rounds, we can construct a classical, deterministic LOCAL algorithm 𝒜' that finds an α-approximation of Π in T rounds. As a corollary, all classical lower bounds for linear programs, including the KMW bound, hold verbatim in quantum-LOCAL. 2) Using the above result, we show that there exists a locally checkable labeling problem (LCL) for which quantum-LOCAL is strictly weaker than the classical deterministic SLOCAL model. Our results extend from quantum-LOCAL to finitely dependent and non-signaling distributions, and one of the corollaries of our work is that the non-signaling model and the SLOCAL model are incomparable in the context of LCL problems: By prior work, there exists an LCL problem for which SLOCAL is strictly weaker than the non-signaling model, and our work provides a separation in the opposite direction.
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.
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.
We present the first local problem that shows a super-constant separation between the classical randomized LOCAL model of distributed computing and its quantum counterpart. By prior work, such a separation was known only for an artificial graph problem with an inherently global definition [Le Gall et al. 2019]. We present a problem that we call iterated GHZ, which is defined using only local constraints. Formally, it is a family of locally checkable labeling problems [Naor and Stockmeyer 1995]; in particular, solutions can be verified with a constant-round distributed algorithm. We show that in graphs of maximum degree Δ, any classical (deterministic or randomized) LOCAL model algorithm will require Ω(Δ) rounds to solve the iterated GHZ problem, while the problem can be solved in 1 round in quantum-LOCAL. We use the round elimination technique to prove that the iterated GHZ problem requires Ω(Δ) rounds for classical algorithms. This is the first work that shows that round elimination is indeed able to separate the two models, and this also demonstrates that round elimination cannot be used to prove lower bounds for quantum-LOCAL. To apply round elimination, we introduce a new technique that allows us to discover appropriate problem relaxations in a mechanical way; it turns out that this new technique extends beyond the scope of the iterated GHZ problem and can be used to e.g. reproduce prior results on maximal matchings [FOCS 2019, PODC 2020] in a systematic manner.
We present a distributed quantum algorithm that 3-colors cycles in O(1) rounds, with high probability. It follows that all locally checkable labeling problems (LCLs) that have round complexity O(log∗n) in the classical LOCAL model can be solved in O(1) rounds in the quantum-LOCAL model, with high probability; this includes problems such as maximal independent set and maximal matching in bounded-degree graphs. This presents the first natural examples of graph problems with an asymptotic distributed quantum advantage for the LOCAL model; all prior examples that separate LOCAL and quantum-LOCAL are artificial problems constructed merely for the sake of demonstrating quantum advantage.
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.