In this paper, we present the first known example of a locally checkable labeling problem (LCL) that admits asymptotic distributed quantum advantage in the LOCAL model of distributed computing: our problem can be solved in $O(\log n)$ communication rounds in the quantum-LOCAL model, but it requires $\Omega(\log n \cdot \log^{0.99} \log n)$ communication rounds in the classical randomized-LOCAL model.

We also show that distributed quantum advantage cannot be arbitrarily large: if an LCL problem can be solved in $T(n)$ rounds in the quantum-LOCAL model, it can also be solved in $\tilde O(\sqrt{n T(n)})$ rounds in the classical randomized-LOCAL model. In particular, a problem that is strictly global classically is also almost-global in quantum-LOCAL.

This solves a major open question at the intersection of distributed graph algorithms and quantum computing. LCL problems [Naor and Stockmeyer, STOC 1993] have been extensively studied in the past decade and they are by now very well-understood in the classical LOCAL model, yet whether any of them admits a genuine quantum advantage has remained open. Coiteux-Roy et al. [STOC 2024] showed that for some specific LCL problems, if quantum helps, it cannot help by much. Akbari et al. [STOC 2025] showed that, for some LCLs, in rooted trees, quantum-LOCAL and randomized-LOCAL have the same power. Balliu et al. [STOC 2025] showed that quantum helps in solving locally checkable problems faster when the maximum degree of the graph is super-constant; however, this does not give any asymptotic quantum advantage for LCLs. The above-mentioned works repeatedly asked the key question of whether quantum helps for LCLs. We solve this open question by giving the first example of an LCL problem that admits a super-constant distributed quantum advantage, and by also giving the first result that puts limits on distributed quantum advantage for LCLs in general graphs.

Our second result also holds for $T(n)$-dependent probability distributions. As a corollary, if there exists a finitely dependent distribution over valid labelings of some LCL problem $\Pi$, then the same problem $\Pi$ can also be solved in $\tilde O(\sqrt{n})$ rounds in the classical randomized-LOCAL and deterministic-LOCAL models. That is, finitely dependent distributions cannot exist for global LCL problems.