Quantum Isomorphism Is Equivalent to Equality of Homomorphism Counts from Planar Graphs

Explore the equivalence between quantum isomorphism and equality of homomorphism counts from planar graphs in this 25-minute IEEE conference talk. Delve into the research presented by Laura Mančinska from the University of Copenhagen and David E. Roberson from the Technical University of Denmark. Learn about key concepts such as isomorphism, quantum strategies, permutation matrices, and homomorphisms. Examine the complexity of the problem and follow the proof involving bilabel graphs, homomorphism matrices, and bilevel graphs. Gain insights into this advanced topic in quantum computing and graph theory, based on the authors' work available at https://arxiv.org/abs/1910.06958.

Introduction
Definition of isomorphism
Game
Quantum strategy
Permutation matrix
Quantum isomorphism
Homomorphism
Complexity
Proof
Bilabel graphs
Homomorphism matrices
Bilevel graphs
Summary