IQC Math and CS seminar featuring Prem Nigam Kar

NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability

Prem Nigam Kar | Technical University of Denmark

Mančinska and Roberson connected the seemingly unrelated fields of nonlocal games and homomorphism indistinguishability by showing that there is a perfect quantum commuting strategy for the graph isomorphism game between two graphs if and only if they admit the same number of homomorphisms from all planar graphs.

In this talk, we shall see that relaxations of quantum isomorphism of graphs arising from the NPA hierarchy can be characterized as homomorphism indistinguishability relations over an appropriate class of planar graphs. By combining this result with the convergence of the NPA hierarchy, we are able to obtain an alternative proof of the homomorphism indistinguishability characterization of quantum isomorphism avoiding the use of quantum groups.

Another consequence of our main result is the existence of a randomized polynomial time algorithm deciding exact feasibility of each level of the NPA hierarchy for quantum isomorphism.

Location

• QNC 1201

• Online on Zoom

  • Meeting ID: 976 6127 0572

  • Passcode: 498117