No distributed quantum advantage for approximate graph coloring
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913277245652992 |
|---|---|
| author | Coiteux-Roy, Xavier d'Amore, Francesco Gajjala, Rishikesh Kuhn, Fabian Gall, François Le Lievonen, Henrik Modanese, Augusto Renou, Marc-Olivier Schmid, Gustav Suomela, Jukka |
| author_facet | Coiteux-Roy, Xavier d'Amore, Francesco Gajjala, Rishikesh Kuhn, Fabian Gall, François Le Lievonen, Henrik Modanese, Augusto Renou, Marc-Olivier Schmid, Gustav Suomela, Jukka |
| contents | 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: 1) We give a new distributed algorithm that finds a $c$-coloring in $χ$-chromatic graphs in $\tilde{\mathcal{O}}(n^{\frac{1}α})$ rounds, with $α= \bigl\lfloor\frac{c-1}{χ- 1}\bigr\rfloor$. 2) We prove that any distributed algorithm for this problem requires $Ω(n^{\frac{1}α})$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_09444 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | No distributed quantum advantage for approximate graph coloring Coiteux-Roy, Xavier d'Amore, Francesco Gajjala, Rishikesh Kuhn, Fabian Gall, François Le Lievonen, Henrik Modanese, Augusto Renou, Marc-Olivier Schmid, Gustav Suomela, Jukka Distributed, Parallel, and Cluster Computing Computational Complexity Discrete Mathematics Emerging Technologies Quantum Physics 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: 1) We give a new distributed algorithm that finds a $c$-coloring in $χ$-chromatic graphs in $\tilde{\mathcal{O}}(n^{\frac{1}α})$ rounds, with $α= \bigl\lfloor\frac{c-1}{χ- 1}\bigr\rfloor$. 2) We prove that any distributed algorithm for this problem requires $Ω(n^{\frac{1}α})$ 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. |
| title | No distributed quantum advantage for approximate graph coloring |
| topic | Distributed, Parallel, and Cluster Computing Computational Complexity Discrete Mathematics Emerging Technologies Quantum Physics |
| url | https://arxiv.org/abs/2307.09444 |