Quantum algorithm colors cycle graphs in constant time
Quantum Advantage for Distributed Symmetry Breaking
Distributed, Parallel, and Cluster Computing
Summary
Some network problems require nodes to pick colors or labels without conflicts, which can be slow on classical computers. The authors show that quantum computing can solve these problems much faster in a distributed setting, specifically coloring cycle graphs with three colors in constant time. This speed-up works for many related problems where classical methods take longer, marking the first natural instance where quantum networks outperform classical ones. This suggests quantum communication can fundamentally improve distributed coordination tasks.
What this means in practice
- •For network algorithm designers: Design faster distributed protocols for breaking symmetry in networked systems using quantum communication.
- •For quantum network engineers: Build quantum-enabled distributed systems that achieve constant-time solutions for key graph problems like 3-coloring cycles.
A theory result. No direct application yet.
Authors
Maxime Flin, Longcheng Li, Jukka Suomela
Abstract
We present a distributed quantum algorithm that $3$-colors cycles in $O(1)$ rounds, with high probability. It follows that all locally checkable labeling problems (LCLs) that have round complexity $O(\log^* n)$ in the classical LOCAL model can be solved in $O(1)$ rounds in the quantum-LOCAL model, with high probability; this includes problems such as maximal independent set and maximal matching in bounded-degree graphs. This presents the first natural examples of graph problems with an asymptotic distributed quantum advantage for the LOCAL model; all prior examples that separate LOCAL and quantum-LOCAL are artificial problems constructed merely for the sake of demonstrating quantum advantage.