Quantum algorithms cannot quickly 4-color directed cycles accurately
Impossibility of One-Way One-Round Quantum 4-Coloring via Matrix-Space Stability
Distributed, Parallel, and Cluster Computing
Summary
This paper shows that certain fast quantum algorithms cannot reliably solve the problem of coloring directed cycle graphs with four colors without conflicts. The authors prove this even if the algorithm can perform unlimited local computation and send very long quantum messages, emphasizing inherent limits of distributed quantum computing. Their approach connects the problem to advanced mathematics involving matrix spaces and combinatorics, revealing deep structural reasons why the problem is hard. This is the first such high-probability lower bound in this quantum setting, going beyond previous simpler models.
What this means in practice
- •For distributed system designers: Avoid designs that assume one-round quantum protocols can solve 4-coloring on directed cycles with high reliability.
- •For quantum algorithm developers: Guide quantum algorithm development by excluding one-way one-round approaches for high-probability 4-coloring on directed cycles.
A theory result. No direct application yet.
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.