Online Locality Meets Distributed Quantum Computing

我们将局部可检标记问题（LCL）的理论从经典LOCAL模型扩展到了其他一些最近被研究的模型，包括量子LOCAL模型、有限依赖过程、非信号模型、动态LOCAL模型和在线LOCAL模型（例如STOC 2024，ICALP 2023）。 首先，我们展示了有限依赖过程相对于经典LOCAL模型的优势。我们证明了所有在LOCAL模型中局部性为$O(\log^* n)$可解的LCL问题都具有有限依赖分布（局部性为常数）。特别地，这为正则树提供了有限依赖着色方案，回答了Holroyd [2023]的一个开放问题。这也为理解分布式量子优势提供了一个新的形式障碍：通过使用非信号论证，不可能排除任何LCL在$\Theta(\log^* n)$复杂度类中具有量子优势。 其次，我们对所有这些模型的能力进行了限制。为此，我们引入了一个称为随机在线LOCAL的模型，它足够强大，可以模拟SLOCAL和动态LOCAL，并且我们证明它也足够强大，可以模拟任何非信号分布，因此可以模拟任何量子LOCAL算法。我们对树的情况证明了以下结果：如果我们可以在随机在线LOCAL模型中以局部性$o(\log^{(5)} n)$解决LCL问题，则我们可以在经典确定性LOCAL模型中以局部性$O(\log^* n)$解决它。 综上所述，这些结果表明，在树中，可以使用局部性$O(\log^* n)$在所有这些模型中解决的LCL集是相同的：量子LOCAL模型、非信号模型、动态LOCAL模型或在线LOCAL模型中的局部性$O(\log^* n)$并不比经典确定性LOCAL模型中的局部性$O(\log^* n)$更强。

本论文旨在将局部可检标记问题（LCLs）的理论从经典LOCAL模型扩展到其他模型，包括量子-LOCAL模型、有限依赖过程、非信号模型、动态-LOCAL模型和在线-LOCAL模型。

论文展示了有限依赖过程在经典LOCAL模型中的优势，并提出了一个新的形式障碍，限制了量子优势的可能性。此外，论文还引入了随机在线-LOCAL模型，并证明了在树形结构中，如果能够在随机在线-LOCAL模型中以$O(log^{(5)}n)$的局部性解决LCL问题，则可以在经典确定性LOCAL模型中以$O(log^*n)$的局部性解决该问题。

本文回答了Holroyd [2023]提出的有关正则树的有限依赖着色问题的开放性问题。此外，论文提出的随机在线-LOCAL模型可以模拟其他模型，同时限制了量子优势的可能性。

该领域的其他相关研究包括STOC 2024和ICALP 2023等会议上的研究。