Quantum Isomorphism Is Equivalent to Equality of Homomorphism Counts from Planar Graphs
Offered By: IEEE via YouTube
Course Description
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
Tags
Related Courses
An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against NatureIEEE via YouTube Computation in the Brain Tutorial - Part 2
IEEE via YouTube Computation in the Brain - Part 1
IEEE via YouTube Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
IEEE via YouTube Cookbook Lower Bounds for Statistical Inference in Distributed and Constrained Settings - Part 1
IEEE via YouTube