Abstract
This paper resolves a major open question in distributed computing by presenting the first Locally Checkable Labeling (LCL) problem that is asymptotically faster to solve on a quantum network than on a classical one. While establishing this quantum advantage, we also prove its strict theoretical limits: any LCL problem solvable in $T(n)$ quantum rounds can be simulated classically in $\tilde{O}(\sqrt{n T(n)})$ rounds. This suggests that while quantum communication provides a measurable speedup, it cannot transform fundamentally global problems into purely local ones.
Introduction
In the theory of distributed graph algorithms, the LOCAL model is the standard framework for analyzing network computation. In this model, each node represents a processor, and each edge is a communication link. A central focus of research is the class of Locally Checkable Labeling (LCL) problems—tasks such as graph coloring or maximal independent set where a solution's validity can be verified by each node checking its immediate, constant-radius neighborhood.
While the complexity of LCLs is well-understood in classical computing, researchers have long questioned if upgrading to a quantum-LOCAL model—allowing quantum computation and communication—could provide asymptotic speedups. While quantum advantages were known for certain artificial global problems, it remained unknown whether quantum mechanics could improve the performance of the highly structured LCL family.
Methodology
To prove the existence of a quantum advantage, the authors engineered a specific LCL problem based on the "iterated GHZ game." In this scenario, players sharing quantum entanglement can achieve winning outcomes without communication that are impossible for classical players. Adapting this to the strict requirements of LCLs required several technical innovations.
Linearization and Gadgets
LCL problems must be defined on graphs with bounded degrees. However, the underlying quantum games often involve high-degree interactions. The authors developed a "linearization" technique to replace high-degree nodes representing players or games with complex "tree-like" and "octopus" gadgets, maintaining the constant-degree requirement of the LOCAL model.
Padding and Entanglement
To create a mathematical separation in runtimes, the authors "padded" the edges between players and games with trees of height $O(\log n)$. In a classical network, information must physically traverse these paths, imposing a logarithmic lower bound on rounds. Quantum algorithms, however, can utilize pre-shared entanglement to bypass this padding in $O(1)$ rounds (plus the cost of gadget simulation), leading to a provable speedup.
Limits of Quantum Advantage
To establish the limits of this advantage, the authors analyzed quantum outputs as bounded-dependence distributions. In the quantum-LOCAL model, a node's output can only depend on operations within its $T$-hop neighborhood, meaning nodes separated by more than $2T$ hops produce statistically independent outputs.
The authors developed a classical simulation strategy that exploits this property. By using a clustering algorithm to partition the graph into well-separated components, they classically sampled the boundaries of these clusters. Because LCL problems only require local consistency, they could then use brute-force computation to fill in valid labels within each cluster independently. This approach yielded a proof that any $T(n)$-round quantum LCL algorithm can be simulated classically in $\tilde{O}(\sqrt{n T(n)})$ rounds.
Key Results
The study yields two primary results that define the current understanding of quantum distributed complexity:
- The Separation: The authors successfully constructed an LCL problem solvable in $O(\log n)$ rounds in the quantum-LOCAL model, but requiring $\Omega(\log n \cdot \log^{0.99} \log n)$ rounds in the classical randomized-LOCAL model. While the gap is small (a doubly-logarithmic factor), it is the first proven asymptotic separation for LCLs.
- The Limit: Any LCL problem solvable in $T(n)$ rounds in quantum-LOCAL can be solved in $\tilde{O}(\sqrt{n T(n)})$ rounds classically. A significant corollary is that if a problem requires $\Omega(n)$ rounds classically (meaning it is strictly global), it will still require at least $\tilde{\Omega}(n)$ rounds on a quantum network.
Conclusion
This work provides the first definitive proof of quantum advantage for LCL problems, necessitating a re-evaluation of classical LCL classification theorems in the quantum domain. While the current separation is small, the "linearization" and "padding" framework introduced here provides a robust toolkit for further exploring the boundaries between classical and quantum distributed complexity. Future research will focus on whether a larger polynomial gap exists or if the classical upper bound can be tightened further.