1 Introduction↩︎

1.1 Context and Motivation↩︎

From the origins of quantum information, the paradoxes and advantages of quantum resources were discussed around nonlocal phenomena, such as the CHSH game [1], whose quantum advantage, as permitted by the theory, was later confirmed experimentally. Since then, there has been growing interest from computer scientists in the study of networks composed of quantum computers, where nodes exchange qubits over communication links, with or without congestion, and with or without pre-shared entanglement.

In particular, significant efforts have been devoted to understanding whether quantum resources can help overcoming obstacles related to locally-bounded computation. This issue has been addressed in the so-called LOCALmodel [2], which assumes a set of \(n\) processing nodes connected by a network modeled as a simple connected graph, and exchanging data via the edges of that graph. The main purpose of this model is to capture locality. That is, computation proceeds as a sequence of synchronous rounds, where, at each round, every node performs arbitrarily calculation, sends an arbitrarily large message to each of its neighbors, and receives the messages from its neighbors. In the quantum variant of LOCAL, the nodes are quantum computers, and the messages can include qubits. The main complexity measure is the number of rounds, which also measures the maximum distance between any two nodes exchanging information during the execution of an algorithm. Many significant results have been recently established in this model, whether it be quantum lower bounds [3]–[5], or the demonstration of quantum advantages [6]–[8].

It was recently shown [5] that quantum resources do not help for 3-coloring trees. Establishing this result uses the fact that the probability distribution defined by the collection of output values produced by nodes performing an \(r\)-round quantum algorithm in LOCAL(with or without pre-shared entanglement) is non-signaling at distance \(r\). The non-signaling property [3], [9] (also referred to as the \(\varphi\)-LOCALmodel in [10]) formalizes the principle of physical causality within the framework of distributed computing. It states that, in any \(r\)-round algorithm, a node cannot be influenced by information originating more than \(r\) hops away from it. Equivalently, the distribution of outputs of a node \(v\) in a graph \(G\) can only depend on nodes within distance at most \(r\) from \(v\) in \(G\). This principle holds independently from whether the node initially share pre-entangled quantum states, or not. Lower bounds based on the non-signaling principle are essentially using indistinguishability arguments: if a problem can be solved in one graph but not in another, the number of rounds must be large enough for the algorithm to distinguish the two cases. The authors in [5] have shown that any non-signaling distribution at distance \(r\) producing a proper 3-coloring of \(n\)-node trees with probability at least \(\epsilon\) satisfies \(r=\Omega(\log n - \log\log 1/\epsilon)\), as long as \(\epsilon>e^{-n}\). Interestingly, this lower bound essentially matches the known \(O(\log n)\)-round upper bound for 3-coloring trees in LOCAL, which can be reached by a deterministic algorithm (see [11]). It follows that quantum resources bring no advantages as far as 3-coloring \(n\)-node trees is concerned. The important case of rooted trees was however left open in [5].

1.1.1 Quantum 3-Coloring Rooted Trees↩︎

Rooted trees play a central role in distributed computing, merely because spanning trees are basic objects at the core of distributed algorithm design for graph problems [2], [12], [13] and most algorithms for spanning tree construction actually produce rooted spanning trees. The deterministic algorithm by Cole and Vishkin [14] can be used to compute a proper 3-coloring of any \(n\)-node rooted tree in \(O(\log^\star n)\) rounds, which is tight thanks to Linial’s seminal \(\Omega(\log^\star n)\) lower bound [15]. The latter can actually be viewed as marking the beginning of the fruitful research line aiming at studying the impact of locality in network computing. Yet, it is only known [16] that this lower bound extends to the randomized variant of LOCAL. Whether quantum resources can help overcoming this lower bound remains open, despite several attempts [3], [5], [17].

Answering this question appears to face an important obstacle. As said before, the collection of outputs of the nodes performing a quantum distributed algorithm on a graph is a joint probability distribution over the nodes, and, compared to classical randomized algorithms, quantum algorithms may induce stronger correlations between the outputs of distant nodes. The aforementioned non-signaling property follows from the mere observation that such correlations remain constrained by the fact that information cannot be propagated faster than the communication radius of the algorithm (i.e., its number of rounds). Locality however impose another constraint, in the absence of shared resources across nodes (such as shared randomness or a pre-shared quantum state): outputs from distant parts of the network remain independent. This is referred to as the finite-dependence property in the literature. It captures the fact that, in a \(r\)-round algorithm, two nodes which are \(2r+1\) hops away have radius-\(r\) neighbors that do not intersect, and therefore they have independent outputs.

Unfortunately, using solely non-signaling and finite dependence is not sufficient to establish quantum lower bounds for coloring rooted trees. Indeed, it was recently shown in [3] that the obstacle for proving non-signaling finitely-dependent lower bound in cycles proved in [18], [19] generalizes to any graph. Specifically, the authors in [3] show that, for any locally checkable labeling (LCL) problem with \(O(\log^\star n)\)-round deterministic complexity in the LOCALmodel, there exists an output distribution that is both non-signaling and finitely dependent at constant distance. As 3-coloring is an LCL problem with round complexity \(O(\log^\star n)\), this result is apparently ruining any hope to derive even super-constant lower bound in the quantum setting using only the non-signaling and finite dependence properties. There is catch though.

LCL problems are defined for graphs (or families of graphs, e.g., trees) for which the maximum degree is upper bounded by a constant \(\Delta\). Therefore, while the results in [18], [19] are preventing the design of quantum lower bounds \(\omega(1)\) for 3-coloring cycles using solely the non-signaling and finite dependence properties, and while [3] is preventing the same for 3-coloring rooted trees, the latter holds only for rooted trees whose maximum degree is bounded by a constant \(\Delta\). Therefore, it does not apply to general rooted trees, whose maximum degrees may be arbitrarily large. We shall show how to exploit this catch. But before that, let us further explore the case of rooted trees with bounded maximum degree, by considering the extreme case of rooted paths, and, by extension, cycles with a consistent notion of clockwise and counter clockwise direction provided to the nodes.

1.1.2 Quantum 2-Coloring Even-Length Cycles↩︎

It is known since the seminal work of Linial [15] that \(2\)-coloring even-size cycles is highly nonlocal: There are no deterministic algorithms running faster than \(\frac{n}{2}-1\) rounds. The high nonlocality of 2-coloring cycles was confirmed in [10], which shows that no quantum algorithms, even using pre-shared entanglement, can 2-color \(n\)-node cycles (\(n\) even) in less than \(\lceil \frac{n-2}{4}\rceil\) rounds. The question of whether quantum resources can help for the design of a 2-coloring algorithm twice faster than the best classical algorithm was however left open.

As for Question 1, answering Question 2 appears to face an important obstacle. The lower bound \(\lceil \frac{n-2}{4}\rceil\) in [10] was actually shown to be tight for non-signaling distributions, in the sense that the global output distribution \(\mathcal{D}\) consisting of choosing any one of the two possible 2-coloring with probability \(\frac{1}{2}\) was shown to be non-signaling at distance \(\lceil \frac{n-2}{4}\rceil\), apparently ruining any hope of improving the lower bound using solely the non-signaling property. There is however again a catch. The output distribution \(\mathcal{D}\) from [10] is defined only for \(n\)-node cycles. In contrast, a quantum algorithm for an even-length cycles \(C_n\) can be executed in other graphs. A node noticing the presence of nodes with degree different from 2 may output whatever, but a node having only nodes of degree 2 in its view outputs one of the two colors as in a cycle, and the distribution of outputs from these nodes is non signaling. We shall show how to exploit this fact for improving the lower bound \(\lceil \frac{n-2}{4}\rceil\).

1.2 Our Results↩︎

We provide a negative answer to both Questions 1 and 2. To our knowledge, our lower bounds are the first fine-grain bounds for quantum-LOCAL, either in the “Ramsey regime” of round-complexity \(O(\log^\star n)\), or in the “linear regime” of round-complexity \(\Omega(n)\). We detail our result below, distinguishing the answer to Question 1 from the answer to Question 2.

1.2.1 Rooted Trees↩︎

We prove that any quantum-LOCALalgorithm for 3-coloring \(n\)-node \(\Delta\)-ary rooted trees succeeding with probability at least \(1-O(1/\Delta)\) requires \(\Omega(\log^\star \Delta)\) rounds. This holds for any \(\Delta\) large enough (\(\Delta\geq 300\) suffices), and not exceeding \(n^{1/\log^\star n}\). An important consequence (see 5) of this result is obtained with, e.g., \(\Delta=\Theta(\log n)\), from which it results that any quantum-LOCALalgorithm for 3-coloring \(n\)-node rooted trees succeeding with probability at least \(1-O(1/\log n)\), requires \(\Omega(\log^\star n)\) rounds.

Our lower bound is established in the more general non-signaling, finitely-dependent framework, using a technique that differs from the indistinguishability arguments on which essentially all previous non-signaling lower bounds were based [5]. Moreover, to the best of our knowledge, this is the first lower bound exploiting the finitely-dependence property. Our technique can actually be viewed as a form of round-elimination, applicable to non-signaling, finitely-dependent distributions by exploiting the recursive structure of rooted trees.

Recall that round-elimination [20] is now a standard technique for establishing lower bounds in the classical LOCALmodel. It essentially generalizes Linial’s original argument for establishing his lower bound on 3-coloring cycles to arbitrary locally checkable labeling (LCL) problems, as defined in [21]. Roughly, it provides a systematic way to transform any LCL problem \(\Pi\) into a problem \(\Pi'\) such that, for any \(r\geq 1\), \(\Pi\) is solvable in \(r\) rounds if and only if \(\Pi'\) is solvable in \(r-1\) rounds. Iterating the transformation \(r\) times eventually results in a problem \(\Pi''\) that should be solvable in zero rounds whenever \(\Pi\) is solvable in \(r\) rounds. The lower bound follows from establishing that \(\Pi''\) is not solvable in zero rounds. The key structural property underlying these arguments is that, in any \(r\)-round randomized LOCALalgorithm, the output of every node \(v\) is a random variable \(Y_v\) that can be written as a function of the random bits \(X_w\) drawn at every node \(w\) in its radius-\(r\) neighborhood, together with the view of the node \(v\) at distance \(r\) in \(G\), i.e. all the data available at the nodes at distance at most \(r\) from \(v\) (potential inputs, identifiers, etc), and structure of the subgraph induced by these nodes. Formally, for every graph \(G\), \[Y_v = f\big((X_w)_{w},\mathsf{view}_r(v,G)\big),\] where \(w\) ranges in the set of nodes with distance at most \(r\) from \(v\), and \(\mathsf{view}_r(v,G)\) is the view of node \(v\) at distance \(r\) in \(G\). This property is referred to as the block-factor property in [19]⁵. The block factor property offers an additional structural constraint beyond non-signaling and independence, and the round-elimination technique for a problem \(\Pi\) exploits this structure as follows.

Round-elimination is based on the fact that, for classical algorithms, each node may perform \(r-1\) rounds only, and then can consider all possible outcomes of the last communication round by ranging over all possible assignments of the random bits at the boundary of its radius-\(r\) neighborhood and all possible views at distance \(r\) that could be observed in the \(r\)th communication round. The corresponding set of outputs of the original algorithm defines a valid output for the related problem \(\Pi'\). For 3-coloring, Linial showed that this transformation reduces any \(r\)-round \(q\)-coloring algorithm for the cycle into a \((r-1)\)-round \(2^q\)-coloring algorithm for the cycles, eventually yielding the \(\Omega(\log^\star n)\) lower bound by iterating the argument using the fact that any zero-round algorithm must use at least \(n\) colors [15], [22]. Naor generalizes Linial’s lower bound for randomized algorithms [23]. Round elimination thus relies crucially on the block-factor structure of the output.

While a similar form of block-factor property still holds for quantum algorithms (see 10), the round-elimination technique itself does not, to our knowledge, directly generalize to the quantum setting. In particular, due to the no-cloning property in quantum computing, our weaker notion of block-factor depends only on the graph structure (including inputs, identifiers, etc), but not on the quantum state \(X_w\) or on anything computed locally by \(w\). Already in the two-party setting, round elimination in quantum communication complexity is a much more complex task with some known but limited results (see [24], [25]), and even an impossibility result whenever it is required that the outputs are systematically correct [26]. Informally, the round elimination’s simulation step requires a node to simulate every possible assignment of data at its boundary and simulate the corresponding extra round of communication. In the quantum setting, however, this direct simulation breaks down: entanglement across the boundary cannot be produced locally, since a node cannot manufacture the entangled correlations that an additional round of communication would have created, without actually performing that communication. Nevertheless, we will show that some form of round elimination can be performed to obtain a quantum lower bound for 3-coloring rooted trees.

1.2.2 Even-Size Cycles↩︎

We prove that any quantum algorithm that properly 2-colors even-size cycles with probability at least \(1-O(1/n)\) requires \(n/2-1\) rounds. This bound holds even for algorithms with pre-shared entanglement. It improves the previously known lower bound from [10] by a factor 2, and it is tight as there is a trivial deterministic algorithm for 2-coloring \(n\)-node cycles, \(n\) even, in \(n/2-1\) rounds. In other words, even pre-shared entangled quantum resources do not help saving even just a single round compared to deterministic algorithms.

Our lower bound is established in the more general non-signaling framework, but using a technique that differs from [10]. To see the differences, it is worth pointing out that the authors of [10] also provide a non-signaling distribution matching their \(n/4\) rounds lower bound. However, this distribution is designed for cycles only, and thus it does not fully respect the principle of physical causality, which should hold with no restriction on the input graph. Indeed, the output distribution of a quantum algorithm (with or without pre-shared entanglement) is a non-signaling distribution. However, even an algorithm \(\mathcal{A}\) designed specifically for \(n\)-node cycles can be used other graphs, e.g., an \((n-1)\)-node cycle plus an isolated node. The isolated node may err, but the other \(n-1\) nodes output. Since \(\mathcal{A}\) is quantum, the output of the nodes in \(C_{n-1}\) is non-signaling. It follows that the non-signaling distribution matching the \(n/4\) rounds lower bound is not a certificate that \(n/4\) is the right lower bound for quantum algorithms, as this distribution is defined over the \(n\)-node cycles only. Instead, we consider non-signaling distributions over a slightly larger class of graphs, composed of all \(n\)-node cycles \(C_n\), plus the graphs composed of \(C_{n-1}\) union one isolated node.

1.3 Related Works↩︎

1.3.0.1 Quantum Lower Bounds.

Several quantum lower bounds have recently been established in the LOCALmodel, most of them proved in the stronger non-signaling setting. General LCL problems have been considered in [3], which introduces the randomized online-LOCAL model, and proves it to be stronger than the non-signaling model, and hence stronger than quantum-LOCAL. Building on this, and using the results in [19], it is then shown that every LCL problem on bounded-degree graphs solvable in \(O(\log^\star n)\) rounds in the LOCALmodel admits a non-signaling, finitely-dependent distribution with constant locality. This generalizes the result in [19], which holds for coloring cycles, in two directions at once: from cycles to arbitrary bounded-degree graphs, and from a coloring problem to all LCL problems of locality \(O(\log^\star n)\). To generalize the coloring to every LCL problem, the authors of [3] use the reduction defined in [27]. We remark that their results do not contradict ours because our lower bound relies on a class of trees of super-constant degree, which falls outside the bounded-degree setting of LCL problems.

A related line of work studies approximate graph coloring. In particular, the problem of \(c\)-coloring a \(\chi\)-colorable graph was considered in [5]. A quantum lower bound (which is shown in general in the non-signaling model) of \(\Omega(n^{\lfloor (c-1)/(\chi-1) \rfloor})\) is established, which is tight for certain classes of bipartite graphs, and an almost-matching classical upper bound of \(\tilde{O}(n^{\lfloor (c-1)/(\chi-1) \rfloor})\) is proved, showing the existence of a deterministic algorithm for the LOCALmodel. These results rule out any super-logarithmic quantum speed-up for the problem. Restricting to unrooted trees, the authors of [5] further prove a quantum lower bound of \(\Omega(\log_c n - \log_c \log \varepsilon^{-1})\) for \(c\)-coloring with success probability at least \(\varepsilon > e^{-n}\), matching the classical upper bound [11] and thereby ruling out a quantum advantage in this setting as well. Also in this case, the lower bound is shown in general for the non-signaling model.

Beyond coloring, [4] shows that no distributed quantum advantage is possible for any linear program, while [28] obtains the first super-constant lower bounds for skinless orientation, and for LLL (i.e., the distributed computation of solutions agreeing with the Lovász Local Lemma). Notably, the latter bounds are proved in the randomized online-LOCALmodel using techniques quite different from the indistinguishability arguments that underlie most non-signaling lower bounds.

Closer to our setting, [29] give an extensive classification of LCL problems on trees, both rooted and unrooted, comparing their complexity in the LOCALmodel against the randomized online-LOCALmodel. For rooted trees, they show that any LCL problem solvable in \(o(\log n)\) rounds in randomized online-LOCALcan also be solved with locality \(O(\log^\star n)\) in the LOCALmodel. Their classification, however, is restricted to constant-degree graphs, and so leaves the case of general rooted trees open.

We refer the reader to the survey [30] for an overview of lower bounds results in this area.

1.3.0.2 Quantum Advantage.

On the other hand, a complementary line of work focuses on establishing that quantum advantage can indeed be obtained in the LOCALmodel for certain problems. A computational task requiring \(\Omega(n)\) rounds in the classical setting but only a constant number of rounds in the quantum setting was exhibited in [8]. However, the problem considered is rather artificial, and has no local description. Subsequently, [6] gave the first problem with a local description exhibiting distributed quantum advantage, called iterated GHZ, an iterated and distributed version of the quantum GHZ game. The separation is \(\Omega(\Delta)\) rounds for graphs of maximum degree \(\Delta\), which, restricted to LCL problems (hence, on bounded-degree graphs), yields only a constant-round separation. Building on this, [7] gave the first LCL problem with an \(\omega(1)\) separation, achieving a ratio of \(\Omega(\log^{0.99} \log n)\) between the classical and quantum round complexities. Despite this progress, the problems used to obtain these separations remain rather artificial, and no natural or fundamental problems in distributed computing is yet known to admit a quantum advantage.

1.3.0.3 Quantum Results in the CONGESTmodel.

The situation regarding the existence of natural or fundamental problems for which a quantum advantage can be observed is different in the CONGESTmodel, which is LOCALplus the additional constraint that messages are limited in size (typically, \(O(\log n)\) bits or qubits). In the CONGESTmodel, quantum advantages have been established for many fundamental problems. This line of work was pioneered by [31], [32]. The former established the impossibility of any quantum advantage in the CONGESTmodel for many important graph-theoretical problems, whereas the latter provided the first quantum advantage in CONGEST, for a basic and important task, namely for computing the diameter of a network. Since then, other quantum speed-ups have been discovered, in particular regarding subgraph detection (e.g., [33]–[37]). Note that these algorithms do not use any pre-shared quantum resources.

1.3.0.4 Distributed Graph Coloring.

The search for efficient algorithms for distributed graph coloring is a highly dynamic and fruitful area of research, and it would be impossible to list here all the results obtained in this domain. We however refer to [38]–[42] for recent results, and pointers to the literature.

2 Computational Models and Probabilistic Framework↩︎

In this section, we define our computational framework, that is, the LOCALmodel and its quantum counterpart, and we recall two notions at the core of our lower bound proof, namely finite-dependence and non-signaling.

2.1 LOCALand Quantum-LOCAL↩︎

This paper focuses on the standard LOCALmodel of distributed computing (see [43]). In this model, a set of \(n\) processing nodes are connected by a network modeled as an \(n\)-node undirected simple graph \(G=(V,E)\). The nodes do not initially know the graph \(G\) they belong to. They are however provided with a polynomial upper bound \(N=poly(n)\) on the number of nodes of this graph. Each node is also provided with an identifier on \(O(\log n)\) bits, which is unique in the network. Computation proceeds as a sequence of synchronous rounds. At each round, every node performs some (unbounded) local computation, then sends a message (of unbounded size) to each of its neighbors, and receives the messages sent by its neighbors. After a certain number of rounds, every node outputs a value, and terminates. The round-complexity of an algorithm is the maximum, taken over all \(n\)-node graphs \(G\), of the number of rounds required for all nodes executing the algorithm in \(G\) to terminate.

2.1.0.1 Randomized-LOCAL.

The design of randomized algorithms in the LOCALmodel assumes that every node is given a private source of random bits. For quantum algorithms it is also assumed that every node can prepare quantum states locally, and that the nodes can exchange quantum bits (qubits) along the edges of the network. In both cases, the output of a node \(v\) is a random value. We denote by \(X_v\) the random variable corresponding to the outputs of node \(v\), and we denote by \(X=(X_v)_{v\in V}\) the collection of all these random variables.

Note that, in the randomized setting, whether it be when considering classical randomized or quantum algorithms, the nodes can forge their identifiers by themselves, e.g., by picking values uniformly at random in \(\{0,\dots,N^{s+2}-1\}\) for some \(s\geq 0\), where \(N=poly(n)\) is the upper bound on the actual number of nodes \(n\) provided to the nodes, which guarantees that every identifier is unique in the network with probability at least \(1-1/n^{s+1}\). Since we are considering classical randomized, or quantum algorithms succeeding with high probability, i.e., with probability at least \(1-O(1/n)\) in \(n\)-node networks, we can assume without loss of generality that the nodes are not initially provided with distinct identifiers, but that these identifiers are picked independently at random by the nodes at the first round.

2.1.0.2 Quantum-LOCAL.

The design of quantum algorithms in the LOCALmodel assumes that every node \(v\in V\) of a graph \(G=(V,E)\) can prepare private quantum states locally, and that the nodes can exchange quantum bits (qubits) along the edges of the graph. This is the equivalent of the randomized LOCALmodel with private randomness, but where nodes can prepare private quantum states instead of using private random coins. The quantum equivalent of classical randomized algorithms with shared randomness is quantum algorithms with shared pre-entangled states.

The ability to create private quantum states (resp., to access shared pre-entangled quantum states) results in global states whose distributions go beyond the ones resulting from using private (resp., shared) randomness, which potentially extends the computing power of distributed quantum algorithms compared to classical ones. The question addressed in this paper is whether this extension really helps as far as distributed coloring is concerned.

2.2 Non-Signaling Processes↩︎

The non-signaling model [9] (also referred to as the \(\varphi\)-LOCALmodel [10]) formalizes the principle of physical causality in distributed computing, which is that, in any \(r\)-round algorithm, a node cannot be influenced by information originating more than \(r\) hops away from it. Equivalently, the output of a node \(v\) in a graph \(G\) can only depend on nodes within distance \(r\) from \(v\) in \(G\). This principle is not a restriction specific to a particular computational model, but rather a fundamental physical constraint that any realizable model of computation must respect, including the LOCALmodel, and the quantum-LOCALmodel. As a consequence, the non-signaling model is the most general model of distributed computation consistent with causality, and lower bounds proved in this model apply universally. We refer the reader to [3], [9], [10] for further discussion on the motivations for the non-signaling model. We now introduce the key objects needed to formalize non-signaling.

2.2.0.1 Views.

Given a graph \(G = (V,E)\), a node \(v \in V\), and an integer \(r \geq 0\), let the distance-\(r\) local view of \(v\), denoted by \(\mathsf{view}_r(G,v)\), be the information available to \(v\) after \(r\) communication rounds. That is, \(\mathsf{view}_r(G,v)\) contains all input of classical data of the nodes in the radius-\(r\) neighborhood of \(v\) in \(G\) (including their degrees, their port numbers if any, and their identifiers), as well as the structure of the connections between these nodes (i.e., the structure of the ball of radius \(r\) centered at \(v\) in \(G\), but the potential edges connecting two nodes at distance exactly \(r\) from \(v\)). Note that a view does not include the starting state of those nodes, which could be eventually entangled. For a set \(S \subseteq V\), we extend the notion of individual view by setting \[\mathsf{view}_r(G, S) \mathrel{\vcenter{:}}= \bigcup_{v \in S} \mathsf{view}_r(G, v).\]

2.2.0.2 Stochastic Outputs.

Let \(\mathcal{G}\) be a graph family. For each \(G \in \mathcal{G}\), we consider a stochastic process of the form \(X^G = (X_v^G)_{v \in V(G)}\). We set \(\mathcal{X} = \{X^G \mid G \in \mathcal{G}\}\), and, for any \(G \in \mathcal{G}\) and any \(S\subseteq V(G)\), we denote by \(X^G_S = (X^G_s)_{s \in S}\) the restriction of \(X^G\) to \(S\). The output of any \(r\)-round algorithm in the non-signaling model must satisfy the following natural consistency condition: the marginal distribution of the output on any set \(S \subseteq V\) depends only on the \(r\)-hop neighborhood of \(S\) in \(G\). This is captured by the following definition, which states that if two sets of nodes have the same local view, then their marginal output distributions must coincide.

Note that if \(\mathcal{X}\) is \(r\)-non-signaling, then \(\mathcal{X}\) is \(r'\)-non-signaling for all \(r'\geq r\).

2.3 Finitely-Dependent Processes↩︎

Finite dependence captures the idea that two stochastic processes as defined in the previous section are independent whenever they are indexed by sets of nodes that are sufficiently far apart. Given two random variables \(Y\) and \(Y'\), we write \(Y \perp \!\!\! \perp Y'\) to denote that \(Y\) and \(Y'\) are independent. Let \(\text{dist}_G(u,v)\) denote the distance from \(u\) to \(v\) in \(G\) (i.e., the length of a shortest path between \(u\) and \(v\) in \(G\)), and, for two sets of nodes \(S\) and \(S'\), we define \(\text{dist}_G(S,S')=\min_{(u,v)\in S\times S'}\text{dist}_G(u,v)\). The following definition of \(k\)-dependence is standard (see, e.g., [19]).

Note that if \(X\) is \(k\)-dependent, then \(X\) is \(k'\)-dependent for all \(k'\geq k\). If \(X\) is \(0\)-dependent, then, for every two non-intersecting sets of nodes \(S\) and \(S'\), we have that \(X_S\) and \(X_{S'}\) are independent.

2.4 NS-FDDistributions and their Relation to Quantum-LOCAL↩︎

The non-signaling finitely-dependent distributions were previously considered in [3]. Informally, the non-signaling finitely-dependent distributions (also called here NS-FD) are arbitrary output distributions, as long as they satisfy the non-signaling condition and induce independence between sufficiently distant parts of the network. Such distributions can be generated, for example, by algorithms in the classical LOCALand quantum-LOCALmodels.

The following proposition says that the output distribution of a \(r\)-round algorithm in the quantum-LOCALmodel are \(r\)-NS-FDdistribution. Moreover, if we consider a \(r\)-round algorithm in the quantum-LOCALmodel with pre-share entanglement, the distribution of the output is \(r\)-non-signaling.

The proposition above has been mentioned in [3], [10]. The first part is almost folklore and in particular implicit in [3]. The second part is proven explicitly in  [10] (proven in Appendix B of their full version), but for a restricted scenario where the graph structure is fixed, for instance a cycle of given length. We provide a complete explicit proof of 3 in 6, which handles the general setting of any family of \(n\)-node graphs.

3 implies that if no family of \(r\)-NS-FDdistributions over \(\mathcal{G}\) is a correct solution to a graph problem, with probability at least \(1-\varepsilon\), then no \(r\)-round LOCALalgorithm, nor any quantum-LOCALalgorithm, can produce an output that is a correct solution to this problem with probability at least \(1-\varepsilon\) on every graph in \(\mathcal{G}\). We shall use this fact for our lower bound on 3-coloring rooted trees, by proving the non-existence of \(o(\log^\star n)\)-NS-FDdistributions for 3-coloring rooted trees.

2.4.0.1 Limitations of the NS-FDApproach for Cycles.

On the other hand, 3 cannot be used for producing non-trivial lower bounds on 3-coloring the \(n\)-node cycle \(C_n\). Indeed, as observed in [3], there exists a family of 1-dependent, stationary random proper 4-coloring distributions for cycles (see [18], [19]). This implies the existence of a family of proper \(4\)-colorings of cycles that is 1-NS-FD. Consequently, one cannot obtain an \(\omega(1)\) lower bound for \(3\)-coloring cycles using NS-FDdistributions⁷.

Since [18], [19] use different notations, and even different concepts (e.g., stationarity), 7 provides more details on the constructions in [18], [19], and a rephrasing of the proof of 4 using the formalism of this paper. We remark that the result in 4 is very general, as the family of distributions \(\mathcal{X}\) is non-signaling on the all family of cycles \(\mathcal{G}\), and therefore, our technique for proving a lower bound on 2-coloring even-size cycles, described in 1.2.2, cannot be adapted to this setting to obtain an analogous lower bound for 3-coloring.

3 Lower Bounds for Rooted Trees↩︎

The aim of this section is to establish a lower bound for proper \(3\)-coloring in the finitely-dependent, non-signaling model (cf. Definition 3) on rooted trees, which, thanks to 3 provides a lower bounds for the quantum-LOCALmodel.

Our proof assumes that the nodes share a common upper bound \(N\) on \(n\), rather than being provided with distinct identifiers. This is without loss of generality: as discussed in 2.1, knowing \(N\) is sufficient for nodes to independently sample identifiers that are globally distinct with probability at least \(1-O(1/n^2)\). Therefore, any algorithm that succeeds in the distinct-identifier setting can be simulated in the anonymous setting with only a negligible loss in success probability. Consequently, the \(\Omega(\log^ \star n)\) lower bound established in the anonymous setting carries over to the distinct-identifier setting as well.

3.1 Notation and Fork Dependence↩︎

We first introduce some notation, and the concept of fork-dependence which will be used in stating and proving our main theorem. For any graph \(G=(V,E)\) and any set \(S\subseteq V\), we denote by \(G[S]\) the subgraph of \(G\) induced by the nodes in \(S\). For any \(q \in \mathbb{N}\), we denote \([q]=\{1,\dots, q\}\).

Let \(\Delta\geq 1\) be an integer. We focus on \(\Delta\)-ary rooted trees \(T=(V,E)\), i.e., rooted trees where each internal node has exactly \(\Delta\) children. For every node \(v \in V\), \(C(v)\) denotes the set of children of \(v\), and \(C^k(v)\) denotes the set of descendants of \(v\) at exactly \(k\) levels below \(v\). That is, \(C^1(v)= C(v)\), and \(C^k(v)= \bigcup_{u \in C(v)} C^{k-1}(u)\). For any set of nodes \(S\), we define \(C^k(S) = \cup_{v \in S}C^k(v)\). Finally, we denote by \(\text{depth}(v)\) the distance from the root to node \(v\).

Intuitively, \((u,v)\) is \(k\)-forked means that reaching \(v\) from \(u\) (or vice versa) requires moving up the tree for at least \(k\) level for reaching their lowest common ancestor, and then moving down at least \(k\) levels. For two sets \(S, S' \subseteq V\), we define \[\text{fork}(S,S') = \min_{u \in S, v \in S'} \text{fork}(u,v),\] and we say \(S\) and \(S'\) are \(k\)-forked if \(\text{fork}(S,S') \geq k\).

The concept of fork-dependence is strongly related to the output distributions of \(k\)-round algorithms in the LOCAL, or quantum-LOCALmodel. Specifically, every \(2k\)-dependent process on a tree is \(k\)-fork-dependent. This observation follows from the mere fact that, for every two nodes \(u\) and \(v\), \(\text{fork}(u,v) > k\) implies \(\text{dist}(u,v) > 2k\).

3.2 Main Result↩︎

The main technical result of the section is the following. Recall that the iterated logarithms are defined by \(\log_2^{(0)}x=x\), and, for any integer \(k\geq 0\), \(\log_2^{(k+1)}x=\log_2(\log_2^{(k)}x)\).

Before establishing 6, let us state important consequences. Recall that, for every \(x\geq 0\), \(\log^\star x\) is defined as the smallest integer \(k\geq 0\) such that \(\log_2^{(k)}x\leq 1\).

In particular, since every \(2k\)-dependent process on a tree is \(k\)-fork-dependent, we get 5 by merely setting \(\Delta=\Theta(\log n)\) in 1, and by using 3. The rest of the section is dedicated to the proof of 6.

3.3 Iterated Power Sets↩︎

For any set \(S\), we denote by \(\mathcal{P}(S)\) the set of all its parts, i.e., the set of all the \(2^{|S|}\) subsets of \(S\). Let \(q \geq 1\) be an integer. For every \(k \geq 0\), we define the \(k\)-fold iterated power set \(\mathcal{P}^k([q])\) recursively as follows: \[\begin{align} &\mathcal{P}^0([q]) = [q] = \{1,\dots,q\}, \\ &\mathcal{P}^k([q]) = \mathcal{P}\big(\mathcal{P}^{k-1}([q])\big) \text{ for k \geq 1}. \end{align}\] In particular, \(\mathcal{P}^k([q])\) is the set of all subsets of \(\mathcal{P}^{k-1}([q])\). For every \(q \geq 1\) and every \(k \geq 0\), we denote by \(\exp_k(q)\) the cardinality of the \(k\)-fold iterated power set, i.e., \[\exp_k(q) = |\mathcal{P}^k([q])|.\] The function \(\exp_k\) thus represents the tower of \(k\) exponentials, i.e. \(\exp_k(q) = \underbrace{2^{2^{\cdots^{2^q}}}}_{\text{k times}}\).

3.4 The Lifted Coloring↩︎

The following notion is a key tool for lifting a \(k\)-fork-dependent coloring into a \(0\)-fork-dependent coloring. Recall that \(C(v)\) denotes the set of children of \(v\).

Thus \(\varphi_0(v,x) \in [q]\), and \(\varphi_k(v,x) \in \mathcal{P}^k([q])\) is a nested multiset of depth \(k\) built from the colors of the descendants of \(v\). The following result states that given a proper coloring \(x=(x_v)_{v\in V}\) of a tree \(T\), then the lifted colorings \(\varphi_k(v,x)\) are distinct across neighboring nodes that are at distance at least \(k\) from every leaf.

The next lemma shows that, given a random \(k\)-fork-dependent \(q\)-coloring \(X=(X_v)_{v \in V}\) of a tree \(T\) which is proper with error at most \(\epsilon\), we can derive a lifted coloring \((\varphi_k(v,X))_{v \in V}\) which \(0\)-fork dependent and is also proper with probability at most \(\epsilon\) on the subtree induced by nodes at distance at least \(k\) from every leaf.

3.5 The Base Case↩︎

The following lemma forms the base case of our lower bound argument. We restrict to \(q \geq 3\), since the case \(q = 2\) (i.e., \(2\)-coloring) is already handled by the known non-signaling lower bound on cycles (which correspond to \(1\)-ary trees).

Before completing the proof of 6, let us point out that, in the case of coloring with zero-error, a stronger bound on the number on the number of colors can be obtained.

3.6 Proof of 6↩︎

We have all ingredients to prove the theorem. It suffices to apply 2 to \(X\). This yields a \(0\)-fork-dependent \(\exp_k(q)\)-coloring \(Y\) of \(T[\mathrm{inner}(T,2k)]\) that is proper with probability at least \(1-1/\Delta\), and such that \(Y_u \sim Y_v\) for all \(u, v \in \mathrm{inner}(T,2k)\). Applying then 3 to \(Y\), we get that \[\exp_k(q) \geq \log_2(\Delta).\] This gives \(q \geq \log^{(k+1)}(\Delta)\), as claimed. 0◻

4 Lower Bound for Even-Size Cycles↩︎

In this section, we push forward the lower bound proved in [10], showing that at least \(\lfloor \frac{n-2}{4}\rfloor\) rounds are needed to \(2\)-color an even-size \(n\)-node cycle by a quantum algorithm, even if nodes are equipped with pre-shared entangled states. Our proof holds in the strongest possible model when all nodes are assigned unique identifiers between 1 and \(n\). Specifically, let us fix the vertex set \(V=[n]=\{1,2,\ldots,n\}\).

We assume that the identifier of node \(i\) is also \(i\). Therefore, since those identifiers are provided in our definition of views, the condition \(\mathsf{view}_r(G, S)=\mathsf{view}_r(G, S')\) implies that \(S=S'\).

Assume for now that \(n\) is even. Since we consider pre-shared entangled states, we will rely on the second part of 3, that we will apply to two possible types of graphs with vertex set \(V=[n]\): either a Hamiltonian cycle (family \(\mathcal{C}_n\)), or an \((n-1)\)-cycle together with one extra isolated node (family \(\mathcal{C}'_{n-1}\)). 5 hereafter shows that any \(t\)-non-signaling distribution must err for properly coloring \(n\)-cycles when \(t\leq (n-4)/2\). Then the missing step leading to 7 consists in proving that any \(t\)-round quantum-LOCALalgorithm on \(\mathcal{C}_n\) leads to a \(t\)-non-signaling distribution on \(\mathcal{F}_n=\mathcal{C}_n\cup \mathcal{C}'_{n-1}\).

Then we are ready to state our main result for \(2\)-colorying \(n\)-cycles, namely that \((n-2)/2\) rounds are needed when the success probability is greater than \(1-1/(n-1)\).

5 Conclusion↩︎

In this paper, we provide the first fine-grained lower bounds for quantum-LOCAL. In particular, we prove two results:

• A lower bound of \(\Omega(\log^\star n)\) rounds for 3-coloring rooted trees by a quantum algorithm with success probability at least \(1-O(1/\log n)\), by using a form of round-reduction applicable to non-signaling finitely-dependent distributions.

• A lower bound of \(n/2-1\) rounds for 2-coloring even-length cycles by a quantum algorithm with success probability at least \(1-O(1/n)\), by exploiting the fact that quantum algorithms generate output distributions that are non-signaling in all graphs. This bound holds even for algorithms using pre-shared entanglement.

Beyond its interest from a quantitative perspective, our \(\Omega(\log^\star n)\) lower bound for 3-coloring \(n\)-node rooted trees is also interesting conceptually. While our technique does not directly generalize to cycles (due to the existence of non-signaling, finitely-dependent distributions on cycles noted above [18], [19]) it suggests a new route toward proving quantum lower bounds for 3-coloring oriented cycles. Indeed, let us consider oriented cycles, where only one-way communications are allowed (say, clockwise). From the perspective of the nodes, in a sufficiently small number of rounds, their local view is indistinguishable from the view they would have in a rooted tree with one-way communication oriented towards the leaves. In the classical LOCALmodel, this observation implies that any algorithm for 3-coloring oriented cycles can be simulated on rooted trees, with nodes receiving information from their parent and broadcasting it to their children. This reduction transfers lower bounds from trees to directed cycles in the classical LOCALmodel. Unfortunately, this argument does not carry over to the quantum-LOCALmodel, since duplicating qubits to broadcast them would violate the no-cloning theorem. Nevertheless, a suitable notion of branching, compatible with quantum communication, may still be formulated in the quantum setting, replacing the broadcast step in the classical reduction. Our lower bound for trees in the non-signaling, finitely-dependent setting suggests that such a tree-based approach could indeed be viable for establishing a quantum-LOCALlower bound on the round complexity of 3-coloring cycles.

5.0.0.1 Acknowledgments:

The second author is thankful to Adrian Kosowski for fruitful discussions on the topic of the paper, especially regarding the lower bound for even-length cycle.

6 From Distributed Quantum Algorithms to Non-Signaling Distributions↩︎

This part is devoted to the proof of 3. First we provide some technical background on density matrices and their partial traces, and then a formal description of a quantum distributed algorithms. This is probably enough to understand the flow of the proof of 3. Nonetheless, for a more complete introduction to quantum computing we refer the interested reader to the excellent book of [44].

6.1 Quantum Information Background↩︎

6.1.1 Density Matrix↩︎

The state of a quantum system can always be described by a unit-norm vector \(\ket{\psi}\) in some given Hilbert space \(\mathcal{H}\), that we usually call a pure state. When \(\mathcal{H}=\mathbb{C}^S\), for some finite set \(S\), the coordinates (amplitudes) of \(\ket{\psi}\) are the quantum analogue of probabilities for probability distribution over \(S\). We say that \(\ket{\psi}\) is a (pure) quantum state over \(\mathcal{H}\) (or over \(S\) when there is no ambiguity).

Nonetheless, this formalism has limitation when considering the state of a subsystem, such as the register of a program, or the node in a network. Then the notion of density matrix is much more suitable. In particular, the density matrix corresponding to a pure state \(\ket{\psi}\) is simply \(\rho=\ketbra{\psi}\). More generally, any probability distribution of quantum states \((\ket{\psi_i},p_i)_{i\in I})\), that we usually call a mixed state, can be represented by a density matrix \(\rho\), an operator of \(\mathcal{H}\) as \[\rho=\sum_{i\in I} p_i \ketbra{\psi_i}.\] This formalism unifies both quantum states and probability distribution of quantum states. We also say that \(\rho\) is a mixed state, or a density matrix, over \(\mathcal{H}\).

Then quantum operation and measurements can be defined similarly than for pure states. For instance, the application of a unitary map \(U\) transforms a density matrix as follows \[\rho\mapsto U\rho U^\dagger.\] Also, the measurement of \(\rho\) in an orthonormal basis \((\ket{x})_{x\in X}\) produces \(\ket{x}\) with probability \(\bra{x}\rho\ket{x}\), in other words it realizes the map \[\rho\mapsto\sum_{x\in X} \bra{x}\rho\ket{x} \ketbra{x}.\]

6.1.2 Partial Trace↩︎

The notion of a local state can be defined through the partial trace operator. Given the global state of a system, it provides a mathematical description of the corresponding local state and, consequently, characterizes the possible outcomes accessible from that local state without any additional communication with the rest of the environment.

Let us consider a bipartite system made of two components, say \(A\) and \(B\), such as two registers, the corresponding Hilbert space can be tensor decomposed as \(\mathcal{H}=\mathcal{H}_A\otimes \mathcal{H}_B\), where \(\mathcal{H}_A\) denotes the space of quantum states of component \(A\), and similarly \(\mathcal{H}_B\) for \(B\). Note that the joint state can be entangled, as joint probabilities can be dependent in the classical setting.

Then, given a density matrix \(\rho\) over \(\mathcal{H}=\mathcal{H}_A\otimes \mathcal{H}_B\), we can describe a notion of density matrix over \(\mathcal{H}_A\) (or \(\mathcal{H}_B\)) describing what locally the state is in \(\mathcal{H}_A\), as marginals do for probability distributions. We denote by \(\tr_{\mathcal{H}_B}\), or simply \(\tr_{B}\), the partial trace operator mapping matrices on \(\mathcal{H}_A\otimes \mathcal{H}_B\) to matrices on \(\mathcal{H}_A\). Formally, \[\tr_B (\rho_A\otimes \ketbra{x}{y})= \begin{cases} \rho_A&\text{ if x=y,}\\ 0&\text{ otherwise.} \end{cases}\]

When \(\rho\) represents a pure state \(\ket{\psi}\) over \(=\mathcal{H}_A\otimes \mathcal{H}_B\), we simply write \(\tr_B (\ket{\psi})\) instead of \(\tr_B (\ketbra{\psi})\). The following facts state two useful and well known properties of partial trace.

When the systeme is now multi-partite, for instance \(\mathcal{H}=\mathcal{H}_I\otimes\mathcal{H}_J\otimes\mathcal{H}_K\), then the notation \(\tr_{J,K}(\rho)\) refers to \(\tr_{\mathcal{H}_J\otimes\mathcal{H}_K}(\rho)\). With our notations, observe that \(\tr_{J,K}(\rho)\) matches \(\tr_J(\tr_K (\rho))\) and also \(\tr_K(\tr_J (\rho))\).

6.2 Framework for Quantum Distributed Computing↩︎

Formally, in a nutshell, the \(r\)-th round of computation of a quantum-LOCALdistributed algorithm is formalized as follows in two steps:

1. Each node \(v\) applies a unitary map \(U^r_v\) (we can always disregard intermediate measurements) on its own quantum memory, including some registers dedicated to communication, one for each edge;

2. For each edge, each node \(v\) exchanges the memory content of the corresponding communication register with the one of the corresponding neighbor node (this is a unitary SWAP operation).

Note that initially the system is in a starting state \(\ket{\Psi^0}\) which is either a tensor product (no pre-shared entanglement), or not (with pre-shared entanglement). Moreover, after the final round, there is formally an extra step, where nodes measure and output one of their memory register.

Observe that the local unitary map \(U^r_v\) depends on \(v\) (and \(r\)). This dependency can model identifiers, inputs, ect. When there is no such dependency than \(U^r_v=U^r_{u}\) for all vertices \(u,v\).

If \(\ket{\Psi}\) is the state of the whole network whose nodes are in \(V\), and \(S\subseteq V\) is a subset of nodes, we simply denote by \(\tr_{S} (\ket{\Psi})\) the partial trace over the registers of nodes in \(S\). In particular, the corresponding (local) state \(\rho_S\) over the registers in \(S\subseteq V\) can be written as \[\rho_S = \tr_{V\setminus S} (\ket{\Psi}).\]

Last, for any subset \(S\subseteq V\) and for any integer \(r\), let \(S^r\) be the union of all radius-\(t\) neighborhood of \(v\in S\). Denote by \(C_S\) the unitary map corresponding to all communication operations performed by the nodes in \(S\) during one round, according to the underlying communication graph \(G\). Observe that these operations include communication both within \(S\) and between \(S\) and \(S^1 \setminus S\). Then the cone of propagation of information is formalized by the following result.

6.3 Proof of 3↩︎

Before proving the proposition, we start with two preliminary results based on 10.

We can now conclude the proof of 3.

7 Holroyd and Liggett’s Result↩︎

The following theorem, proved in [19] and subsequently generalized to cycles in [18], establishes the existence of finitely-dependent, stationary proper colorings of the integer line \(\mathbb{Z}\) and of finite cycles.

We note that ?? , together with stationarity of \(X\), implies that any consecutive block of \(X^{(n)}\) of length at most \(n-k\) has the same distribution as a block of \(X\) of the same length.

The case \((k,q) = (1,4)\) of 13 is of particular interest for us. In this regime, the stationarity property ?? can be used to show that the induced family of \(4\)-coloring is \(1\)-non-signaling over the family \(\{C_n, n \geq 3\}\) of cycle graphs, as stated in 4. We provide a proof of the lemma below.

References↩︎

---

1. CNRS, Université Paris Cité, IRIF, Paris, France. Email: pierre.fraigniaud@irif.fr↩︎

2. CNRS, Université Paris Cité, IRIF, Paris, France. Email: frederic.magniez@irif.fr↩︎

3. CNRS, Université Paris Cité, IRIF, Paris, France. Email: isabella.ziccardi@irif.fr↩︎

4. Research supported in part by the French PEPR integrated project EPiQ (ANR-22-PETQ-0007), and the French ANR projects ANR-24-CE48-7768-01 (ENEDISC) and ANR-23-CE48-0010 (PREDICTIONS).↩︎

5. In [19], the proof that no \(r\)-block factor \(q\)-coloring of the infinite line exists, for any \(r\) and \(q\) (Proposition 2), actually follows the same lines as a simplified proof of Linial’s lower bound for 3-coloring [22].↩︎

6. For instance, the nodes could share some global knowledge, such as an upper bound \(N\) on the number of nodes \(n\).↩︎

7. Any lower bound for \(4\)-coloring carries over to \(3\)-coloring by adding two additional rounds: in the LOCALmodel, any proper \(4\)-coloring of a rooted tree can be transformed into a proper \(3\)-coloring in just two rounds.↩︎