A preprint posted to arXiv — not yet peer-reviewed — presents a distributed quantum algorithm that 3-colors cycle graphs in a constant number of communication rounds, regardless of the cycle's length. In the classical LOCAL model, the best known algorithms require O(log* n) rounds for this task, a complexity that grows (however slowly) with the network size. The quantum algorithm achieves O(1) rounds by exploiting quantum correlations during local computation steps.
The authors argue this single result has broad consequences. They show that any locally checkable labeling (LCL) problem solvable in O(log* n) classical rounds can be solved in O(1) quantum-LOCAL rounds with high probability. LCLs are a well-studied class of distributed graph problems whose solutions can be verified by inspecting small neighborhoods; the class includes canonical problems such as maximal independent set and maximal matching in bounded-degree graphs. The claimed separation is therefore not confined to a single contrived instance.
That last point is the paper's most significant framing: every prior separation between the classical LOCAL and quantum-LOCAL models relied on problems engineered specifically to expose quantum advantage, limiting their practical interpretive weight. The authors claim cycle 3-coloring and the LCL family constitute the first natural graph problems exhibiting an asymptotic distributed quantum speedup. As an unreviewed preprint, the result awaits independent scrutiny before its claims can be considered settled.