2023/07/18 by Xavier Coiteux-Roy, Francesco d'Amore, Francesco d’Amore +20 · 2 voices · 4 citations
Computer Science · #Complexity and Algorithms in Graphs #Quantum Computing Algorithms and Architecture #Distributed systems and fault tolerance
paper · pdf · doi:10.48550/arxiv.2307.09444
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^\frac1α) rounds, with α= \lfloor(c-1)/(χ- 1)\rfloor. 2) We prove that any distributed algorithm for this problem requires Ω(n^\frac1α) 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.