Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Documents

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.
Original languageEnglish
Title of host publication2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)
PublisherIEEE
Publication date2020
Pages661-672
DOIs
Publication statusPublished - 2020
Event61st Annual Symposium on Foundations of Computer Science (FOCS), 2020 IEEE
- Durham, NC, United States
Duration: 16 Nov 202019 Nov 2020

Conference

Conference61st Annual Symposium on Foundations of Computer Science (FOCS), 2020 IEEE
LandUnited States
ByDurham, NC
Periode16/11/202019/11/2020

Number of downloads are based on statistics from Google Scholar and www.ku.dk


No data available

ID: 256583934