No Distributed Quantum Advantage for 3-Coloring Rooted Trees and 2-Coloring Even Cycles
2026-07-06 • Distributed, Parallel, and Cluster Computing
Distributed, Parallel, and Cluster Computing
AI summaryⓘ
The authors investigate whether quantum computing helps speed up certain coloring tasks in network trees and cycles. They show that for 3-coloring rooted trees, quantum resources do not reduce the rounds needed compared to classical methods. They prove this using a technique similar to classical approaches and extend it to trees with any fixed branching factor. Additionally, for 2-coloring even-length cycles, they demonstrate quantum algorithms require almost as many rounds as classical ones, improving previous lower bounds. Overall, the work suggests quantum advantages do not exist for these specific distributed coloring problems.
Quantum-LOCAL modelDistributed computingGraph coloring3-coloring2-coloringRooted treesEven-length cyclesRounds complexityCole-Vishkin algorithmLinial's LOCAL model
Authors
Pierre Fraigniaud, Frédéric Magniez, Isabella Ziccardi
Abstract
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 $Ω(\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 $Ω(\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 $Ω(\log^\star Δ)$ for 3-coloring any $Δ$-ary tree with success probability at least $1-1/Δ$. 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.