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

Laura Mancinska, David E. Roberson

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

17 Downloads (Pure)

Abstract

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 publicationProceedings of IEEE 61st Annual Symposium on Foundations of Computer Science
PublisherIEEE Computer Society Press
Publication dateNov 2020
Pages661-672
Article number9317964
ISBN (Electronic)9781728196213
DOIs
Publication statusPublished - Nov 2020
Event61st IEEE Annual Symposium on Foundations of Computer Science - Virtual event, Durham, United States
Duration: 16 Nov 202019 Nov 2020

Conference

Conference61st IEEE Annual Symposium on Foundations of Computer Science
LocationVirtual event
Country/TerritoryUnited States
CityDurham
Period16/11/202019/11/2020
SponsorIEEE
SeriesProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2020-November
ISSN0272-5428

Keywords

  • Graphs
  • Homomorphism counting
  • Quantum groups
  • Quantum information

Fingerprint

Dive into the research topics of 'Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs'. Together they form a unique fingerprint.

Cite this