Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2607.04852

No Distributed Quantum Advantage for 3-Coloring Rooted Trees and 2-Coloring Even Cycles

Pierre Fraigniaud, Frédéric Magniez, Isabella Ziccardi

cs.DCquant-phSubmitted Jul 6, 2026• Announced Jul 7, 2026• 0 citations• Revised Jul 11, 2026 (v2)
v1 · Jul 6, 2026v2 · Jul 11, 2026
arXivHTMLPDF

Abstract

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^\star n)$ rounds, matching Linial's classical $Ω(\log^\star 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/\log n)}$ must perform $Ω(\log^\star 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^\star Δ)$ 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 $\lceil (n-2)/4 \rceil$ 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.

Related papers

No distributed quantum advantage for approximate graph coloring

Xavier Coiteux-Roy, Francesco d’Amore, Rishikesh R. Gajjala +7 more

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 $\tilde{\mathcal{O}}(n^{\frac{1}α})$ rounds, with $α= \bigl\lfloor\frac{c-1}{χ- 1}\bigr\rfloor$. 2) We prove that any distributed algorithm for this problem requires $Ω(n^{\frac{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.

arXiv:2307.09444•Jul 18, 2023•1 citation

Distributed Quantum Algorithms Cannot Color Cycles with Probability 1

Xavier Coiteux-Roy, Maxime Flin, Carlos de Gois +3 more

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.

arXiv:2608.11720•Aug 12, 2026•0 citations

Non-trivial lower bound for 3-coloring the ring in the quantum LOCAL model

François Le Gall, Ansis Rosmanis

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 $Θ(\log n)$. 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$.

arXiv:2212.02768•Dec 6, 2022•1 citation

Quantum Advantage for Distributed Symmetry Breaking

Maxime Flin, Longcheng Li, Jukka Suomela

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.

quant-pharXiv:2609.26788•Sep 23, 2026•0 citations

Online Locality Meets Distributed Quantum Computing

Amirreza Akbari, Xavier Coiteux-Roy, Francesco d’Amore +8 more

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^\star 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(\log \log \log n)$ in the randomized online-LOCAL model (or any of the weaker models, such as quantum-LOCAL), we can solve it with locality $O(\log^\star n)$ in the classical deterministic LOCAL model. One of many implications is that in rooted trees, $O(\log^\star n)$ locality in quantum-LOCAL is not stronger than $O(\log^\star n)$ locality in classical LOCAL.

arXiv:2403.01903•ACM Symposium on Theory of Computing (STOC)•Jun 15, 2025•6 citations

Impossibility of One-Way One-Round Quantum 4-Coloring via Matrix-Space Stability

Tom Gur, Longcheng Li

We show that one-way one-round quantum-LOCAL algorithms cannot $4$-color directed cycles with high probability. This is the first lower bound in the high-probability quantum LOCAL setting that goes beyond the non-signaling and bounded-dependence models, exploiting the structure of distributed quantum algorithms. Our proof establishes a bidirectional connection between distributed quantum computing and extremal combinatorics. We obtain our lower bound by proving a Mantel-type stability theorem for weighted matrix spaces.

quant-pharXiv:2609.09091•Sep 9, 2026•0 citations
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-Royetal.~(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 nnn-node trees in O(log⁡⋆n)O(\log^\star n)O(log⋆n) rounds, matching Linial's classical Ω(log⁡⋆n)Ω(\log^\star n)Ω(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 nnn-node rooted trees with probability at least 1−O(1/log⁡n){1-O(1/\log n)}1−O(1/logn) must perform Ω(log⁡⋆n)Ω(\log^\star n)Ω(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⁡⋆Δ)Ω(\log^\star Δ)Ω(log⋆Δ) for 3-coloring any ΔΔΔ-ary tree with success probability at least 1−1/Δ1-1/Δ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 nnn-node cycles with probability 1−O(1/n)1-O(1/n)1−O(1/n) requires n/2−1n/2-1n/2−1 rounds in the quantum-LOCAL model, even with pre-shared entangled states. This improves the previously known ⌈(n−2)/4⌉\lceil (n-2)/4 \rceil⌈(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 give an almost complete characterization of the hardness of ccc-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 ccc-coloring in χχχ-chromatic graphs in O~(n1α)\tilde{\mathcal{O}}(n^{\frac{1}α})O~(nα1​) rounds, with α=⌊c−1χ−1⌋α= \bigl\lfloor\frac{c-1}{χ- 1}\bigr\rfloorα=⌊χ−1c−1​⌋. 2) We prove that any distributed algorithm for this problem requires Ω(n1α)Ω(n^{\frac{1}α})Ω(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 ccc-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 prove that any distributed quantum algorithm that finds a 333-coloring with probability 111 in a cycle of anonymous identical computers has to be global, that is, it needs Ω(n)Ω(n)Ω(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 333-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 111-round quantum algorithms cannot break symmetry with probability 111. Second, we present a wishful teleportation strategy that can be used to turn TTT-round quantum 3-coloring algorithms into 111-round quantum algorithms breaking symmetry, while preserving success probability 111. 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 nnn-node ring is Θ(log⁡∗ ⁣n)Θ(\log^*\!n)Θ(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)Θ(n)Θ(n), when there is no communication, to Θ(log⁡n)Θ(\log n)Θ(logn). In this work, we show that the probability of any quantum single-round one-way distributed algorithm to output a proper 333-coloring is exponentially small in nnn.
We present a distributed quantum algorithm that 333-colors cycles in O(1)O(1)O(1) rounds, with high probability. It follows that all locally checkable labeling problems (LCLs) that have round complexity O(log⁡∗n)O(\log^* n)O(log∗n) in the classical LOCAL model can be solved in O(1)O(1)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 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)O(\log^\star n)O(log⋆n) in the classical deterministic LOCAL model admit a finitely-dependent distribution with locality O(1)O(1)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(log⁡log⁡log⁡n)o(\log \log \log n)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)O(\log^\star n)O(log⋆n) in the classical deterministic LOCAL model. One of many implications is that in rooted trees, O(log⁡⋆n)O(\log^\star n)O(log⋆n) locality in quantum-LOCAL is not stronger than O(log⁡⋆n)O(\log^\star n)O(log⋆n) locality in classical LOCAL.
We show that one-way one-round quantum-LOCAL algorithms cannot 444-color directed cycles with high probability. This is the first lower bound in the high-probability quantum LOCAL setting that goes beyond the non-signaling and bounded-dependence models, exploiting the structure of distributed quantum algorithms. Our proof establishes a bidirectional connection between distributed quantum computing and extremal combinatorics. We obtain our lower bound by proving a Mantel-type stability theorem for weighted matrix spaces.