Distributed Quantum Advantage in Locally Checkable Labeling Problems

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 Ω(log n • 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 Õ( nT (n)) rounds in the classical randomized-LOCAL model. In particular, an LCL 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 Π, then the same problem Π can also be solved in Õ( √ n) rounds in the classical randomized-LOCAL and deterministic-LOCAL models. That is, finitely dependent distributions cannot exist for global LCL problems.