Distributed Quantum Algorithms Cannot Color Cycles with Probability 1

Xavier Coiteux-Roy, Maxime Flin, Carlos de Gois +3

We prove that any distributed quantum algorithm that finds a $3$-coloring with probability $1$ in a cycle of anonymous identical computers has to be global, that is, it needs $Ω(n)…