← 研踪 PaperTrailarXiv:2609.09091 · v3
Impossibility of One-Way One-Round Quantum 4-Coloring via Matrix-Space Stability
首次提交 2026-09-09 01:35
版本更新 2026-11-03 21:52
雷达观测 2026-11-04 23:39
摘要
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.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v3 · 2026-11-03 21:52 · 最新观测版本
Impossibility of One-Way One-Round Quantum 4-Coloring via Matrix-Space Stability
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.
查看此版本解读 →查看此版本原文 ↗