2022/12/06 by François Le Gall, Gall, François Le, Ansis Rosmanis +1 · 2 citations
Computer Science · #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #FOS: Physical sciences #Parallel #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Stochastic Gradient Optimization Techniques #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2212.02768
openalex publication_date 2022/12/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the LOCAL model of distributed computing, where in a single round of communication each node can send to each of its neighbors a message of an arbitrary size. It is know that, classically, the round complexity of 3-coloring an n-node ring is Θ(log^* n). In the case where communication is quantum, only trivial bounds were known: at least some communication must take place. We study distributed algorithms for coloring the ring that perform only a single round of one-way communication. Classically, such limited communication is already known to reduce the number of required colors from Θ(n), when there is no communication, to Θ(log n). In this work, we show that the probability of any quantum single-round one-way distributed algorithm to output a proper 3-coloring is exponentially small in n.