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

ACM Symposium on Theory of Computing (STOC)

No Distributed Quantum Advantage for Approximate Graph Coloring

Xavier Coiteux-Roy, Francesco d’Amore, Rishikesh R. Gajjala, Fabian Kühn, François Le Gall, Henrik Lievonen, Augusto Modanese, Marc-Olivier Renou, Gustav Schmid, Jukka Suomela

Published Jun 10, 2024• 7 citations
Publisher

Abstract

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:
DOI
10.1145/3618260.3649679

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

Investigating Quantum Approximation Techniques for Tackling NP-Hard Problems in Distributed Systems

Chandra Yogatama, Randi Dwi Wibisono

The resolution of NP-hard problems, including the traveling salesman problem and graph coloring, continues to be a major hurdle in computational science. While traditional algorithms are effective for smaller problems, they often require excessive computational resources for larger instances. Distributed systems present a potential remedy by harnessing parallelism, but they encounter inherent obstacles such as latency and synchronization overhead. Quantum computing emerges as a promising alternative with its potential for exponential speedups, yet it faces practical constraints like noise and scalability issues. This research investigates quantum approximation algorithms for tackling NP-hard problems in distributed systems, with an emphasis on hybrid quantum-classical methodologies. By crafting approximation techniques specifically for distributed environments and suggesting innovative approaches to incorporate quantum nodes into a distributed system, this study aims to surmount current limitations and lay the groundwork for scalable quantum-assisted problem-solving. The proposed methods undergo evaluation through theoretical analysis and experimental simulations, showcasing their capacity to address computational bottlenecks in distributed systems.

ALCOM Journal of Algorithm and Computing•Feb 10, 2025•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

Locality in distributed quantum and online graph algorithms

Henrik Lievonen

In this thesis, I study how quantum computation and quantum communication can help large networks of computers to solve computational problems faster. I also connect the notion of locality between various models, including distributed quantum algorithms and online graph algorithms, and show that locality in online graph algorithms can be used to provide bounds for distributed quantum advantage. Towards proving distributed quantum advantage, I present the first family of LCL problems which shows a quantum advantage for distributed graph algorithms. Here LCLs, or Locally Checkable Labeling problems, are a family of graph problems described by a finite set of local constraints, and I mainly focus on them in this thesis. The models of distributed computing which this result separates are the classical LOCAL model and the quantum-LOCAL model. In both of these models, a network of computers exchanges messages in synchronous rounds, and the running time of the algorithm directly corresponds with locality, that is, how far the computers see in the network. In this thesis, I also introduce new models of computing that capture locality in stronger settings. Most notably, I introduce the online-LOCAL model which captures the locality of online graph algorithms, and show that it is, asymptotically, roughly as strong as the classical LOCAL model for solving LCL problems on rooted regular trees. I provide an online-LOCAL algorithm for finding a 3-coloring of a bipartite graph with lower locality than is possible in the classical LOCAL model, and show that the algorithm is tight. To draw things together, I show that quantum-LOCAL and online-LOCAL are indeed related to each other: any quantum-LOCAL algorithm can be simulated in the randomized online-LOCAL model. The converse does not hold in general, but an online-LOCAL algorithm solving an LCL problem in rooted, possibly non-regular, trees can be simulated in the classical LOCAL model—and thus in the quantum-LOCAL model—with an exponential cost in locality, putting indirectly a bound on the maximum possible attainable quantum advantage. Finally, I consider the sinkless orientation problem, which holds a central role in our understanding of the locality of LCL problems in the classical LOCAL model, and provide a simpler and more direct proof for its hardness using the supported LOCAL model. I also provide a simpler algorithm solving sinkless orientation in the SLOCAL model, which is a sequential version of the LOCAL model.

•Jan 1, 2026•0 citations

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

Hierarchical quantum approximation optimization algorithm for solving graph-coloring problems

刘冬梅 Liu Dongmei, Jian Li, XIUBO CHEN +3 more

Physical Review A•Jan 26, 2026•0 citations
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.
The resolution of NP-hard problems, including the traveling salesman problem and graph coloring, continues to be a major hurdle in computational science. While traditional algorithms are effective for smaller problems, they often require excessive computational resources for larger instances. Distributed systems present a potential remedy by harnessing parallelism, but they encounter inherent obstacles such as latency and synchronization overhead. Quantum computing emerges as a promising alternative with its potential for exponential speedups, yet it faces practical constraints like noise and scalability issues. This research investigates quantum approximation algorithms for tackling NP-hard problems in distributed systems, with an emphasis on hybrid quantum-classical methodologies. By crafting approximation techniques specifically for distributed environments and suggesting innovative approaches to incorporate quantum nodes into a distributed system, this study aims to surmount current limitations and lay the groundwork for scalable quantum-assisted problem-solving. The proposed methods undergo evaluation through theoretical analysis and experimental simulations, showcasing their capacity to address computational bottlenecks in distributed systems.
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.
In this thesis, I study how quantum computation and quantum communication can help large networks of computers to solve computational problems faster. I also connect the notion of locality between various models, including distributed quantum algorithms and online graph algorithms, and show that locality in online graph algorithms can be used to provide bounds for distributed quantum advantage. Towards proving distributed quantum advantage, I present the first family of LCL problems which shows a quantum advantage for distributed graph algorithms. Here LCLs, or Locally Checkable Labeling problems, are a family of graph problems described by a finite set of local constraints, and I mainly focus on them in this thesis. The models of distributed computing which this result separates are the classical LOCAL model and the quantum-LOCAL model. In both of these models, a network of computers exchanges messages in synchronous rounds, and the running time of the algorithm directly corresponds with locality, that is, how far the computers see in the network. In this thesis, I also introduce new models of computing that capture locality in stronger settings. Most notably, I introduce the online-LOCAL model which captures the locality of online graph algorithms, and show that it is, asymptotically, roughly as strong as the classical LOCAL model for solving LCL problems on rooted regular trees. I provide an online-LOCAL algorithm for finding a 3-coloring of a bipartite graph with lower locality than is possible in the classical LOCAL model, and show that the algorithm is tight. To draw things together, I show that quantum-LOCAL and online-LOCAL are indeed related to each other: any quantum-LOCAL algorithm can be simulated in the randomized online-LOCAL model. The converse does not hold in general, but an online-LOCAL algorithm solving an LCL problem in rooted, possibly non-regular, trees can be simulated in the classical LOCAL model—and thus in the quantum-LOCAL model—with an exponential cost in locality, putting indirectly a bound on the maximum possible attainable quantum advantage. Finally, I consider the sinkless orientation problem, which holds a central role in our understanding of the locality of LCL problems in the classical LOCAL model, and provide a simpler and more direct proof for its hardness using the supported LOCAL model. I also provide a simpler algorithm solving sinkless orientation in the SLOCAL model, which is a sequential version of the LOCAL model.
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.