English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We give an almost complete characterization of the hardness of $c$-coloring$\chi$-chromatic graphs with distributed algorithms, for a wide range of modelsof distributed computing. In particular, we show that these problems do notadmit any distributed quantum advantage. To do that: 1) We give a newdistributed algorithm that finds a $c$-coloring in $\chi$-chromatic graphs in$\tilde{\mathcal{O}}(n^{\frac{1}{\alpha}})$ rounds, with $\alpha =\bigl\lfloor\frac{c-1}{\chi - 1}\bigr\rfloor$. 2) We prove that any distributedalgorithm for this problem requires $\Omega(n^{\frac{1}{\alpha}})$ rounds.  Our upper bound holds in the classical, deterministic LOCAL model, while thenear-matching lower bound holds in the non-signaling model. This model,introduced by Arfaoui and Fraigniaud in 2014, captures all models ofdistributed graph algorithms that obey physical causality; this includes notonly 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 evenfor the non-signaling model, and in particular do not admit any quantumadvantage. Our lower-bound arguments are purely graph-theoretic at heart; nobackground on quantum information theory is needed to establish the proofs.

No distributed quantum advantage for approximate graph coloring