PreprintCC BY 4.0arXiv
Impossibility of One-Way One-Round Quantum 4-Coloring via Matrix-Space Stability
Abstract
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.
Related
- Quantum n-coloring is undecidable for every n ≥ 3
- Solving Graph Coloring Problems Using Feedback-Based Algorithm for Quantum Optimization
- Constant-round quantum advantage in communication complexity for total functions
- A Quantum Framework for K Coloring of Graphs
- Unconditional quantum advantage from a two-round CHSH problem in one dimension
BibTeX
@misc{gur2026impossibility,
title = {{Impossibility of One-Way One-Round Quantum 4-Coloring via Matrix-Space Stability}},
author = {Tom Gur and Longcheng Li},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.09091},
eprint = {2609.09091},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.09091},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Impossibility of One-Way One-Round Quantum 4-Coloring via Matrix-Space Stability
AU - Tom Gur
AU - Longcheng Li
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2609.09091
UR - https://arxiv.org/abs/2609.09091
AB - 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.
ER -