NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability

Mančinska and Roberson [FOCS’20] showed that two graphs are quantum
isomorphic if and only if they admit the same number of homomorphisms from
any planar graph. Atserias et al. [JCTB’19] proved that quantum isomorphism
is undecidable in general, which motivates the study of its relaxations. In the
classical setting, Roberson and Seppelt [ICALP’23] characterized the feasibility
of each level of the Lasserre hierarchy of semidefinite programming relaxations
of graph isomorphism in terms of equality of homomorphism counts from an
appropriate graph class. The NPA hierarchy, a noncommutative generalization
of the Lasserre hierarchy, provides a sequence of semidefinite programming relaxations for quantum isomorphism. In the quantum setting, we show that the
feasibility of each level of the NPA hierarchy for quantum isomorphism is equivalent to equality of homomorphism counts from an appropriate class of planar graphs. Combining this characterization with the convergence of the NPA hierarchy, and noting that the union of these classes is the set of all planar graphs, we obtain a new proof of the result of Mančinska and Roberson [FOCS’20]
that avoids the use of quantum groups. Moreover, this homomorphism indistinguishability characterization also yields a randomized polynomial-time
algorithm deciding exact feasibility of each fixed level of the NPA hierarchy of
SDP relaxations for quantum isomorphism.