Search papers, labs, and topics across Lattice.
This paper establishes that quantum resources do not confer any advantage in the distributed 3-coloring of rooted trees, demonstrating that algorithms in the quantum-LOCAL model must still operate within a lower bound of $\Omega(\log^\star n)$ rounds. The authors also improve the lower bound for 2-coloring even-length cycles, showing that it requires $n/2-1$ rounds, which is a significant enhancement over previous results. These findings reinforce the limitations of quantum computing in overcoming locality constraints in distributed settings, particularly for specific graph structures.
Quantum algorithms can't outperform classical methods in 3-coloring rooted trees and 2-coloring even cycles, challenging assumptions about quantum advantages in distributed computing.
Significant effort has been devoted over the past decade to understanding whether quantum resources can provide advantages in distributed computing, and in particular whether they can help overcome locality constraints in networks, typically in Linial's LOCAL model. Recently, Coiteux-Roy~et~al.~(STOC 2024) showed that quantum resources do not help for 3-coloring \textit{unrooted} trees: in particular, their lower bound holds in the stronger \textit{non-signaling} model, which formalizes the principle of physical causality in distributed computing. The case of \textit{rooted} trees, however, was left open by their work. For rooted trees, the deterministic Cole-Vishkin algorithm 3-colors $n$-node trees in $O(\log^\star n)$ rounds, matching Linial's classical $\Omega(\log^\star n)$ lower bound (FOCS 1987). In this paper, we show that any algorithm in quantum-LOCAL (without pre-shared entanglement) that properly 3-colors $n$-node rooted trees with probability at least ${1-O(1/\log n)}$ must perform $\Omega(\log^\star n)$ rounds. That is, quantum resources provide no advantage for 3-coloring rooted trees. To get this result, we show a lower bound of $\Omega(\log^\star \Delta)$ for 3-coloring any $\Delta$-ary tree with success probability at least $1-1/\Delta$. The proof uses a \textit{color lifting} technique that bears similarity to Linial's original argument. We also show, as a separate result, that 2-coloring even-length $n$-node cycles with probability $1-O(1/n)$ requires $n/2-1$ rounds in the quantum-LOCAL model, even with pre-shared entangled states. This improves the previously known $\lceil (n-2)/4 \rceil$ lower bound of Gavoille, Kosowski, and Markiewicz (DISC 2009) by a factor of two, and shows that quantum algorithms cannot save even a single round over classical deterministic algorithms for 2-coloring even-length cycles.
