Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

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

IEEE via YouTube

Overview

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.

Syllabus

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

Taught by

IEEE FOCS: Foundations of Computer Science

Reviews

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

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.