{"id":"arxiv/2607.04852","url":"https://arxiv.org/abs/2607.04852","tags":["cs.DC","quant-ph"],"score":0,"title":"No Distributed Quantum Advantage for 3-Coloring Rooted Trees and 2-Coloring Even Cycles","domain":"cs.DC","source":"arxiv","authors":["Pierre Fraigniaud","Frédéric Magniez","Isabella Ziccardi"],"reviews":0,"subject":"cs.DC","summary":"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,…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-06","reactions":{}}