arXiv:2609.26788
Quantum Advantage for Distributed Symmetry Breaking
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.
AI Summary
The paper asks whether natural graph symmetry-breaking problems admit an asymptotic quantum advantage in the LOCAL model, where classical messages and local computation are unrestricted. It gives quantum-LOCAL algorithms reducing the classical $\Theta(\log^* n)$ round complexity of several bounded-degree problems to $O(1)$ rounds, with high probability. The central construction is a one-way, one-round anonymous quantum algorithm for directed cycles using $20{,}000$ colors, with monochromatic-edge probability at most any prescribed $\epsilon>0$. Each node sends $O(\log(1/\epsilon))$ qubits; a matching $\Omega(\log(1/\epsilon))$ lower bound holds for fixed-color one-way, one-round anonymous algorithms. Knowing an upper bound $n$ on network size permits inverse-polynomial local error and hence global high-probability correctness. Classical color reduction then gives a four-round $3$-coloring algorithm for cycles and paths. Further reductions yield constant-round coloring, maximal independent set, and maximal matching on bounded-degree graphs, and collapse every classically $O(\log^* n)$-round LCL to quantum $O(1)$ rounds. Rooted trees of maximum degree $\Delta$ admit tight $O(\log^*\Delta)$-round $3$-coloring. The proof constructs operators over an infinite group algebra, uses weighted-norm contraction and polynomial square-root approximation to enforce positivity, and evaluates them through finite-dimensional representations. Normalizing the resulting zero-energy operators produces POVMs with arbitrarily small collision probability. Entanglement is created during communication, not supplied initially. The quantum ingredient addresses only directed-cycle coloring; broader consequences use classical reductions. The approach does not improve the degree dependence beyond those reductions, the smallest feasible one-round color count remains open, and finite-dimensional one-round correctness is approximate rather than exact.
Our main result was discovered using OpenAI GPT-6 in Codex.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.