Distributed Quantum Advantage in Locally Checkable Labeling Problems
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913780734099456 |
|---|---|
| author | Balliu, Alkida Casagrande, Filippo d'Amore, Francesco Equi, Massimo Keller, Barbara Lievonen, Henrik Olivetti, Dennis Schmid, Gustav Suomela, Jukka |
| author_facet | Balliu, Alkida Casagrande, Filippo d'Amore, Francesco Equi, Massimo Keller, Barbara Lievonen, Henrik Olivetti, Dennis Schmid, Gustav Suomela, Jukka |
| contents | 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 $Ω(\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 $Π$, then the same problem $Π$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_05191 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Distributed Quantum Advantage in Locally Checkable Labeling Problems Balliu, Alkida Casagrande, Filippo d'Amore, Francesco Equi, Massimo Keller, Barbara Lievonen, Henrik Olivetti, Dennis Schmid, Gustav Suomela, Jukka Distributed, Parallel, and Cluster Computing Computational Complexity Quantum Physics 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 $Ω(\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 $Π$, then the same problem $Π$ 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. |
| title | Distributed Quantum Advantage in Locally Checkable Labeling Problems |
| topic | Distributed, Parallel, and Cluster Computing Computational Complexity Quantum Physics |
| url | https://arxiv.org/abs/2504.05191 |