{"id":"arxiv/2609.26788","url":"https://arxiv.org/abs/2609.26788","tags":["quant-ph","cs.DC"],"score":0,"title":"Quantum Advantage for Distributed Symmetry Breaking","domain":"quant-ph","source":"arxiv","authors":["Maxime Flin","Longcheng Li","Jukka Suomela"],"reviews":0,"subject":"quant-ph","summary":"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 round complexity $O(\\log^* n)$ in the classical LOCAL model can be solved in $O(1)$ rounds in the quantum-LOCAL model, with high probability; this includes problems such as maximal independent set and maximal matching in bounded-degree graphs. This presents the first natural examples of graph problems with an asymptotic distributed quantum advantage for the LOCAL model; all prior examples that separate LOCAL and…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-22","reactions":{}}