17 November 2020

QMATH in FOCS 2020: Planar graphs and Quantum Mechanics


On November 18,2020 Laura Mančinska from QMATH presented her joint work with David E. Roberson (DTU Compute) at one of the top two theoretical computer science conferences, FOCS.

This work shows that entanglement-assisted strategies in a certain game based on graph isomorphism admit a purely combinatorial interpretation. Specifically, whether or not the quantum players can win the (G,H)-ismomrphism game with certainty is equivalent to graphs, G and H, having the same number of homomorphisms from any planar graph. Read more here https://arxiv.org/pdf/1910.06958.pdf