No distributed quantum advantage for approximate graph coloring

View PDF HTML (experimental)

We give an almost complete characterization of the hardness of c-coloring \chi-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 \chi-chromatic graphs in \tilde{\mathcal{O}}(n^{\frac{1}{\alpha}}) rounds, with \alpha = \bigl\lfloor\frac{c-1}{\chi - 1}\bigr\rfloor. 2) We prove that any distributed algorithm for this problem requires \Omega(n^{\frac{1}{\alpha}}) 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.