No distributed quantum advantage for approximate graph coloring

No distributed quantum advantage for approximate graph coloring

[Submitted on 18 Jul 2023 (v1), last revised 14 Nov 2023 (this version, v2)]

Download PDF

Abstract:We give an almost complete characterization of the hardness of $c$-coloring $chi$-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 $chi$-chromatic graphs in $tilde{mathcal{O}}(n^{frac{1}{alpha}})$ rounds, with $alpha = bigllfloorfrac{c-1}{chi – 1}bigrrfloor$. 2) We prove that any distributed algorithm for this problem requires $Omega(n^{frac{1}{alpha}})$ 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.

Submission history

From: Francesco D’Amore [view email]
Tue, 18 Jul 2023 17:17:27 UTC (226 KB)
Tue, 14 Nov 2023 16:37:35 UTC (1,096 KB)

Read More

Leave a Reply

Your email address will not be published. Required fields are marked *