Online Locality Meets Distributed Quantum Computing
<|reference_start|>Online Locality Meets Distributed Quantum Computing: 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.<|reference_end|>
@article{akbari2024online,
    title={Online Locality Meets Distributed Quantum Computing},
    author={Amirreza Akbari, Xavier Coiteux-Roy, Francesco d'Amore, Franc{c}ois
  Le Gall, Henrik Lievonen, Darya Melnyk, Augusto Modanese, Shreyas Pai,
  Marc-Olivier Renou, V'aclav Rozhov{n}, Jukka Suomela},
    journal={arXiv preprint arXiv:2403.01903},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.01903},
    primaryClass={cs.DC cs.CC math.PR quant-ph}
}