Quantum Advantage for Distributed Symmetry Breaking

Maxime Flin, Longcheng Li, Jukka Suomela

We present a distributed quantum algorithm that $3$-colors cycles in $O(1)$ rounds, with high probability. It follows that all locally checkable labeling problems (LCLs) that have…