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 · 2024
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: