{"id":"arxiv/2609.09091","url":"https://arxiv.org/abs/2609.09091","tags":["quant-ph","cs.DC"],"score":0,"title":"Impossibility of One-Way One-Round Quantum 4-Coloring via Matrix-Space Stability","domain":"quant-ph","source":"arxiv","authors":["Tom Gur","Longcheng Li"],"reviews":0,"subject":"quant-ph","summary":"We show that one-way one-round quantum-LOCAL algorithms cannot $4$-color directed cycles with high probability. 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 establishes a bidirectional connection between distributed quantum computing and extremal combinatorics. We obtain our lower bound by proving a Mantel-type stability theorem for weighted matrix spaces.","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-08","reactions":{}}