Online Locality Meets Distributed Quantum Computing
| Autor: | Akbari, Amirreza, Coiteux-Roy, Xavier, d'Amore, Francesco, Gall, François Le, Lievonen, Henrik, Melnyk, Darya, Modanese, Augusto, Pai, Shreyas, Renou, Marc-Olivier, Rozhoň, Václav, Suomela, Jukka |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | We extend the theory of locally checkable labeling problems (LCLs) from the classical LOCAL model to a number of other models that have been studied recently, including the quantum-LOCAL model, finitely-dependent processes, non-signaling model, dynamic-LOCAL model, and online-LOCAL model [e.g. STOC 2024, ICALP 2023]. First, we demonstrate the advantage that finitely-dependent processes have over the classical LOCAL model. We show that all LCL problems solvable with locality $O(\log^\star n)$ in the LOCAL model admit a finitely-dependent distribution (with constant locality). In particular, this gives a finitely-dependent coloring for regular trees, answering an open question by Holroyd [2023]. This also introduces a new formal barrier for understanding the distributed quantum advantage: it is not possible to exclude quantum advantage for any LCL in the $\Theta(\log^\star n)$ complexity class by using non-signaling arguments. Second, we put limits on the capabilities of all of these models. To this end, we introduce a model called randomized online-LOCAL, which is strong enough to simulate e.g. SLOCAL and dynamic-LOCAL, and we show that it is also strong enough to simulate any non-signaling distribution and hence any quantum-LOCAL algorithm. We prove the following result for rooted trees: if we can solve an LCL problem with locality $o(\log \log n)$ in the randomized online-LOCAL model, we can solve it with locality $O(\log^\star n)$ in the classical deterministic LOCAL model. Put together, these results show that in rooted trees the set of LCLs that can be solved with locality $O(\log^\star n)$ is the same across all these models: classical deterministic and randomized LOCAL, quantum-LOCAL, non-signaling model, dynamic-LOCAL, and deterministic and randomized online-LOCAL. Comment: 60 pages, 10 figures. This version corrects a mistake in v1 |
| Databáze: | arXiv |
| Externí odkaz: |
|