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
Aplicaciones de la teoría de grafos a la vida realMiríadax Aplicaciones de la Teoría de Grafos a la vida real
Universitat Politècnica de València via UPV [X] Introduction to Computational Thinking and Data Science
Massachusetts Institute of Technology via edX Genome Sequencing (Bioinformatics II)
University of California, San Diego via Coursera Algorithmic Information Dynamics: From Networks to Cells
Santa Fe Institute via Complexity Explorer