Online Locality Meets Distributed Quantum Computing

We connect three distinct lines of research that have recently explored extensions of the classical LOCAL model of distributed computing: A. distributed quantum computing and non-signaling distributions [e.g. STOC 2024], B. finitely-dependent processes [e.g. Forum Math. Pi 2016], and C. locality in online graph algorithms and dynamic graph algorithms [e.g. ICALP 2023]. We prove new results on the capabilities and limitations of all of these models of computing, for locally checkable labeling problems (LCLs). We show that all these settings can be sandwiched between the classical LOCAL model and what we call the randomized online-LOCAL model. Our work implies limitations on the quantum advantage in the distributed setting, and we also exhibit a new barrier for proving tighter bounds. Our main technical results are these: (1) All LCL problems solvable with locality O (log ⋆ n ) in the classical deterministic LOCAL model admit a finitely-dependent distribution with locality O (1). This answers an open question by Holroyd [2024], and also presents a new barrier for proving bounds on distributed quantum advantage using causality-based arguments. (2) In rooted trees, if we can solve an LCL problem with locality o (logloglog n ) in the randomized online-LOCAL model (or any of the weaker models, such as quantum-LOCAL), we can solve it with locality O (log ⋆ n ) in the classical deterministic LOCAL model. One of many implications is that in rooted trees, O (log ⋆ n ) locality in quantum-LOCAL is not stronger than O (log ⋆ n ) locality in classical LOCAL.

Authors

• Amirreza Akbari
• Xavier Coiteux-Roy
• Francesco d'Amore 0001
• François Le Gall
• Henrik Lievonen
• Darya Melnyk
• Augusto Modanese
• Shreyas Pai
• Marc-Olivier Renou
• Václav Rozhon
• Jukka Suomela

Keywords

• distributed computing
• locally checkable labeling problems
• quantum advantage