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:2212.02768

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

François Le Gall, Ansis Rosmanis

Published Dec 6, 2022• 8 citations
arXivHTMLPDF

Abstract

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$.

DOI
10.48550/arxiv.2212.02768

Related papers

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

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

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.

cs.DCCross-listedarXiv:2607.04852•Jul 7, 2026•3 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•2 citations

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•2 citations

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•6 citations

What Can be Observed Locally? Round-based Models for Quantum Distributed Computing

Cyril Gavoille, Adrian Kosowski, Markiewicz, Marcin

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.

arXiv:0903.1133•Mar 6, 2009•6 citations

The Quantum Message Complexity of Distributed Wake-Up with Advice

Peter Robinson, Ming Ming Tan

We consider the distributed wake-up problem with advice, where nodes are equipped with initial knowledge about the network at large. After the adversary awakens a subset of nodes, an oracle computes a bit string (``the advice'') for each node, and the goal is to wake up all sleeping nodes efficiently. We present the first upper and lower bounds on the message complexity for wake-up in the quantum routing model, introduced by Dufoulon, Magniez, and Pandurangan (PODC 2025). In more detail, we give a distributed advising scheme that, given $α$ bits of advice per node, wakes up all nodes with a message complexity of $O( \sqrt{\frac{n^3}{2^{\max\{\lfloor (α-1)/2 \rfloor},0\}}}\cdot\log n )$ with high probability. Our result breaks the $Ω( \frac{n^2}{2^α} )$ barrier known for the classical port numbering model in sufficiently dense graphs. To complement our algorithm, we give a lower bound on the message complexity for distributed quantum algorithms: By leveraging a lower bound result for the single-bit descriptor problem in the query complexity model, we show that wake-up has a quantum message complexity of $Ω( n^{3/2} )$ without advice, which holds independently of how much time we allow. In the setting where an adversary decides which nodes start the algorithm, most graph problems of interest implicitly require solving wake-up, and thus the same lower bound also holds for other fundamental problems such as single-source broadcast and spanning tree construction.

quant-pharXiv:2602.05801•Feb 6, 2026•0 citations
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.
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 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 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.
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 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.
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.
We consider the distributed wake-up problem with advice, where nodes are equipped with initial knowledge about the network at large. After the adversary awakens a subset of nodes, an oracle computes a bit string (``the advice'') for each node, and the goal is to wake up all sleeping nodes efficiently. We present the first upper and lower bounds on the message complexity for wake-up in the quantum routing model, introduced by Dufoulon, Magniez, and Pandurangan (PODC 2025). In more detail, we give a distributed advising scheme that, given ααα bits of advice per node, wakes up all nodes with a message complexity of O(n32max⁡{⌊(α−1)/2⌋,0}⋅log⁡n)O( \sqrt{\frac{n^3}{2^{\max\{\lfloor (α-1)/2 \rfloor},0\}}}\cdot\log n )O(2max{⌊(α−1)/2⌋,0}n3​​⋅logn) with high probability. Our result breaks the Ω(n22α)Ω( \frac{n^2}{2^α} )Ω(2αn2​) barrier known for the classical port numbering model in sufficiently dense graphs. To complement our algorithm, we give a lower bound on the message complexity for distributed quantum algorithms: By leveraging a lower bound result for the single-bit descriptor problem in the query complexity model, we show that wake-up has a quantum message complexity of Ω(n3/2)Ω( n^{3/2} )Ω(n3/2) without advice, which holds independently of how much time we allow. In the setting where an adversary decides which nodes start the algorithm, most graph problems of interest implicitly require solving wake-up, and thus the same lower bound also holds for other fundamental problems such as single-source broadcast and spanning tree construction.