Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs
Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs
复制标题
DOI：
10.1109/focs46700.2020.00067
复制
发表时间：
2019-10
期刊：
影响因子：
--
通讯作者：
L. Mančinska;David E. Roberson
中科院分区：
文献类型：
--
作者：
L. Mančinska;David E. Roberson
50多年前，Lovász证明了两个图是同构的当且仅当它们从任何图中接受相同数量的同态。图上的其他等价关系，如共谱性或分数同构，可以通过适当选择的一类图的同态计数相等来表征。Dvotelák [J. Graph Theory 2010]表明，将这类图作为树宽最多为$k$的图，产生了一个易于处理的图同构松弛，称为$k$维Weisfeiler-Leman等价。再加上蔡，Fürer和Immerman [FOCS 1989]的一个著名结果，这表明有界树宽的图的同态数不确定同构的图。Dell，Grohe和Rynn [ICALP 2018]提出了平面图的同态计数是否决定了同构的图，以及所得关系的复杂性。我们通过证明所得关系等价于所谓的量子同构来否定前者[Mančinska et al，ICALP 2017]。使用这种等价性，我们进一步解决后一个问题，测试是否有两个图从任何平面图相同数量的同态是，令人惊讶的是，一个不可判定的问题，而且是完整的类核心（递归可判定问题的补充）。量子同构定义在一个单轮，两个证明者交互式证明系统中，量子证明者，谁被允许共享纠缠，试图说服验证者，图形是同构的。我们的组合证明利用了图的量子自同构群，这是一个来自非交换数学的概念。
Over 50 years ago, Lovász proved that two graphs are isomorphic if and only if they admit the same number of homomorphisms from any graph. Other equivalence relations on graphs, such as cospectrality or fractional isomorphism, can be characterized by equality of homomorphism counts from an appropriately chosen class of graphs. Dvořák [J. Graph Theory 2010] showed that taking this class to be the graphs of treewidth at most $k$ yields a tractable relaxation of graph isomorphism known as $k$-dimensional Weisfeiler-Leman equivalence. Together with a famous result of Cai, Fürer, and Immerman [FOCS 1989], this shows that homomorphism counts from graphs of bounded treewidth do not determine a graph up to isomorphism. Dell, Grohe, and Rattan [ICALP 2018] raised the questions of whether homomorphism counts from planar graphs determine a graph up to isomorphism, and what is the complexity of the resulting relation. We answer the former in the negative by showing that the resulting relation is equivalent to the so-called quantum isomorphism [Mančinska et al, ICALP 2017]. Using this equivalence, we further resolve the latter question, showing that testing whether two graphs have the same number of homomorphisms from any planar graph is, surprisingly, an undecidable problem, and moreover is complete for the class coRE (the complement of recursively enumerable problems). Quantum isomorphism is defined in terms of a one-round, two-prover interactive proof system in which quantum provers, who are allowed to share entanglement, attempt to convince the verifier that the graphs are isomorphic. Our combinatorial proof leverages the quantum automorphism group of a graph, a notion from noncommutative mathematics.