Abstract: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. 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.
From: Filippo Casagrande [view email]
[v1]
Mon, 7 Apr 2025 15:42:05 UTC (211 KB)
[v2]
Mon, 17 Aug 2026 08:42:45 UTC (203 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。