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

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

Tom Gur, Longcheng Li

quant-phcs.DCSubmitted Sep 8, 2026• Announced Sep 9, 2026• 0 citations
v1 · Sep 8, 2026v2 · Oct 1, 2026
arXivHTMLPDF

Abstract

We show that one-way one-round quantum LOCAL algorithms cannot $4$-color directed cycles with high probability, even with unbounded local computation and quantum message length. 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 connects distributed quantum computing with noncommutative extremal combinatorics by identifying local collision probabilities with the weighted multiplicative energy of matrix-space decompositions. We obtain our lower bound by proving a dimension-independent weighted stability theorem for a directed noncommutative analogue of Mantel's theorem.

Related papers

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

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

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

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

New Limits on Distributed Quantum Advantage: Dequantizing Linear Programs

Alkida Balliu, Corinna Coupette, Antonio Cruciani +6 more

In this work, we give two results that put new limits on distributed quantum advantage in the context of the LOCAL model of distributed computing: 1) We show that there is no distributed quantum advantage for any linear program. Put otherwise, if there is a quantum-LOCAL algorithm 𝒜 that finds an α-approximation of some linear optimization problem Π in T communication rounds, we can construct a classical, deterministic LOCAL algorithm 𝒜' that finds an α-approximation of Π in T rounds. As a corollary, all classical lower bounds for linear programs, including the KMW bound, hold verbatim in quantum-LOCAL. 2) Using the above result, we show that there exists a locally checkable labeling problem (LCL) for which quantum-LOCAL is strictly weaker than the classical deterministic SLOCAL model. Our results extend from quantum-LOCAL to finitely dependent and non-signaling distributions, and one of the corollaries of our work is that the non-signaling model and the SLOCAL model are incomparable in the context of LCL problems: By prior work, there exists an LCL problem for which SLOCAL is strictly weaker than the non-signaling model, and our work provides a separation in the opposite direction.

arXiv:2506.07574•Leibniz international proceedings in informatics•Jan 1, 2025•0 citations
We show that one-way one-round quantum LOCAL algorithms cannot 444-color directed cycles with high probability, even with unbounded local computation and quantum message length. 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 connects distributed quantum computing with noncommutative extremal combinatorics by identifying local collision probabilities with the weighted multiplicative energy of matrix-space decompositions. We obtain our lower bound by proving a dimension-independent weighted stability theorem for a directed noncommutative analogue of Mantel's theorem.
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.
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 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 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.
In this work, we give two results that put new limits on distributed quantum advantage in the context of the LOCAL model of distributed computing: 1) We show that there is no distributed quantum advantage for any linear program. Put otherwise, if there is a quantum-LOCAL algorithm 𝒜 that finds an α-approximation of some linear optimization problem Π in T communication rounds, we can construct a classical, deterministic LOCAL algorithm 𝒜' that finds an α-approximation of Π in T rounds. As a corollary, all classical lower bounds for linear programs, including the KMW bound, hold verbatim in quantum-LOCAL. 2) Using the above result, we show that there exists a locally checkable labeling problem (LCL) for which quantum-LOCAL is strictly weaker than the classical deterministic SLOCAL model. Our results extend from quantum-LOCAL to finitely dependent and non-signaling distributions, and one of the corollaries of our work is that the non-signaling model and the SLOCAL model are incomparable in the context of LCL problems: By prior work, there exists an LCL problem for which SLOCAL is strictly weaker than the non-signaling model, and our work provides a separation in the opposite direction.