We prove that any distributed quantum algorithm that finds a
3-coloring with probability
1 in a cycle of anonymous identical computers has to be global, that is, it needs
Ω(n) communication rounds. It follows that quantum computation and communication does not help with this problem. All prior lower bounds on quantum advantage in distributed graph algorithms use arguments related to physical causality. However, it is known that such arguments cannot rule out fast quantum advantage for
3-coloring cycles. In particular, any causality-based argument would rule out the existence of finitely dependent coloring, but Holroyd and Liggett (2016) showed that such colorings do exist. Hence to tackle this problem, we need a ``genuinely quantum'' lower-bound technique that can distinguish between (1) distributions that do not violate physical causality vs. (2) distributions that can be realized with a quantum strategy. We present the first such lower-bound technique in this context. First, we show that
1-round quantum algorithms cannot break symmetry with probability
1. Second, we present a wishful teleportation strategy that can be used to turn
T-round quantum 3-coloring algorithms into
1-round quantum algorithms breaking symmetry, while preserving success probability
1. Put together, the lower bound follows.
We consider the LOCAL model of distributed computing, where in a single round of communication each node can send to each of its neighbors a message of an arbitrary size. It is know that, classically, the round complexity of 3-coloring an
n-node ring is
Θ(log∗n). In the case where communication is quantum, only trivial bounds were known: at least some communication must take place. We study distributed algorithms for coloring the ring that perform only a single round of one-way communication. Classically, such limited communication is already known to reduce the number of required colors from
Θ(n), when there is no communication, to
Θ(logn). In this work, we show that the probability of any quantum single-round one-way distributed algorithm to output a proper
3-coloring is exponentially small in
n.
Significant effort has been devoted over the past decade to understanding whether quantum resources can provide advantages in distributed computing, and in particular whether they can help overcome locality constraints in networks, typically in Linial's LOCAL model. Recently, Coiteux-Roy~et~al.~(STOC 2024) showed that quantum resources do not help for 3-coloring \textit{unrooted} trees: in particular, their lower bound holds in the stronger \textit{non-signaling} model, which formalizes the principle of physical causality in distributed computing. The case of \textit{rooted} trees, however, was left open by their work.
For rooted trees, the deterministic Cole-Vishkin algorithm 3-colors
n-node trees in
O(log⋆n) rounds, matching Linial's classical
Ω(log⋆n) lower bound (FOCS 1987). In this paper, we show that any algorithm in quantum-LOCAL (without pre-shared entanglement) that properly 3-colors
n-node rooted trees with probability at least
1−O(1/logn) must perform
Ω(log⋆n) rounds. That is, quantum resources provide no advantage for 3-coloring rooted trees. To get this result, we show a lower bound of
Ω(log⋆Δ) for 3-coloring any
Δ-ary tree with success probability at least
1−1/Δ. The proof uses a \textit{color lifting} technique that bears similarity to Linial's original argument.
We also show, as a separate result, that 2-coloring even-length
n-node cycles with probability
1−O(1/n) requires
n/2−1 rounds in the quantum-LOCAL model, even with pre-shared entangled states. This improves the previously known
⌈(n−2)/4⌉ lower bound of Gavoille, Kosowski, and Markiewicz (DISC 2009) by a factor of two, and shows that quantum algorithms cannot save even a single round over classical deterministic algorithms for 2-coloring even-length cycles.
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.
We give an almost complete characterization of the hardness of
c-coloring
χ-chromatic graphs with distributed algorithms, for a wide range of models of distributed computing. In particular, we show that these problems do not admit any distributed quantum advantage. To do that: 1) We give a new distributed algorithm that finds a
c-coloring in
χ-chromatic graphs in
O~(nα1) rounds, with
α=⌊χ−1c−1⌋. 2) We prove that any distributed algorithm for this problem requires
Ω(nα1) rounds. Our upper bound holds in the classical, deterministic LOCAL model, while the near-matching lower bound holds in the non-signaling model. This model, introduced by Arfaoui and Fraigniaud in 2014, captures all models of distributed graph algorithms that obey physical causality; this includes not only classical deterministic LOCAL and randomized LOCAL but also quantum-LOCAL, even with a pre-shared quantum state. We also show that similar arguments can be used to prove that, e.g., 3-coloring 2-dimensional grids or
c-coloring trees remain hard problems even for the non-signaling model, and in particular do not admit any quantum advantage. Our lower-bound arguments are purely graph-theoretic at heart; no background on quantum information theory is needed to establish the proofs.
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. Source: http://arxiv.org/abs/2609.26788v1 (arXiv:2609.26788v1) Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com