No distributed quantum advantage for approximate graph coloring

Xavier Coiteux-Roy, Francesco d'Amore, Rishikesh Gajjala +7

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. I…