Impossibility of One-Way One-Round Quantum 4-Coloring via Matrix-Space Stability
This paper proves that one-way one-round quantum local algorithms cannot 4-color directed cycles with high probability. By connecting coloring to noncommutative extremal combinatorics, it establishes a universal positive lower bound on the collision probability for any such algorithm, showing that the required energy for four color classes is too high to be achieved by a single round of local computation.