Quantum algorithms cannot quickly color directed cycles in networks
Impossibility of One-Way One-Round Quantum 4-Coloring via Matrix-Space Stability
Distributed, Parallel, and Cluster Computing
Summary
The researchers found that certain quantum algorithms cannot reliably assign 4 colors to nodes arranged in a circle where each connection has a direction, even if the quantum computers can do unlimited calculations and send long messages. This shows a fundamental limit on how fast these quantum methods can solve such coloring problems in distributed networks. They used a new mathematical approach that links ideas from quantum computing with advanced math about matrices to prove this limit. This work goes beyond earlier results by deeply exploring how quantum information behaves locally in these systems.
quantum LOCAL modelgraph coloringdirected cyclesdistributed algorithmsquantum communicationnoncommutative combinatoricsmatrix-space decompositionsmultiplicative energystability theoremMantel's theorem
Authors
Tom Gur, Longcheng Li
Abstract
We show that one-way one-round quantum LOCAL algorithms cannot $4$-color directed cycles with high probability, even with unbounded local computation and quantum message length. This is the first lower bound in the high-probability quantum LOCAL setting that goes beyond the non-signaling and bounded-dependence models, exploiting the structure of distributed quantum algorithms. Our proof connects distributed quantum computing with noncommutative extremal combinatorics by identifying local collision probabilities with the weighted multiplicative energy of matrix-space decompositions. We obtain our lower bound by proving a dimension-independent weighted stability theorem for a directed noncommutative analogue of Mantel's theorem.