No Distributed Quantum Advantage for Approximate Graph Coloring
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
2024-06-10
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
10
Series
STOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pp. 1901-1910
Abstract
We give an almost complete characterization of the hardness of c-coloring χ-chromatic graphs with distributed algorithms, for a wide range of models of distributed computing. In particular, we show that these problems do not admit any distributed quantum advantage. To do that: We give a new distributed algorithm that finds a c-coloring in χ-chromatic graphs in Õ(n1/α) rounds, with α = ⌊c-1/χ - 1⌋. We prove that any distributed algorithm for this problem requires ω(n1/α) rounds. Our upper bound holds in the classical, deterministic LOCAL model, while the near-matching lower bound holds in the non-signaling model. This model, introduced by Arfaoui and Fraigniaud in 2014, captures all models of distributed graph algorithms that obey physical causality; this includes not only classical deterministic LOCAL and randomized LOCAL but also quantum-LOCAL, even with a pre-shared quantum state. We also show that similar arguments can be used to prove that, e.g., 3-coloring 2-dimensional grids or c-coloring trees remain hard problems even for the non-signaling model, and in particular do not admit any quantum advantage. Our lower-bound arguments are purely graph-theoretic at heart; no background on quantum information theory is needed to establish the proofs.Description
Publisher Copyright: © 2024 Owner/Author.
Keywords
distributed computing, graph coloring, non-signaling model, quantum advantage
Other note
Citation
Coiteux-Roy, X, D'Amore, F, Gajjala, R, Kuhn, F, Le Gall, F, Lievonen, H, Modanese, A, Renou, M O, Schmid, G & Suomela, J 2024, No Distributed Quantum Advantage for Approximate Graph Coloring . in B Mohar, I Shinkar & R O' Donnell (eds), STOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing . ACM, pp. 1901-1910, ACM Symposium on Theory of Computing, Vancouver, British Columbia, Canada, 24/06/2024 . https://doi.org/10.1145/3618260.3649679