NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F25%3A10509189" target="_blank" >RIV/00216208:11320/25:10509189 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.4230/LIPIcs.ICALP.2025.105" target="_blank" >https://doi.org/10.4230/LIPIcs.ICALP.2025.105</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.ICALP.2025.105" target="_blank" >10.4230/LIPIcs.ICALP.2025.105</a>

Result language
angličtina
Original language name
NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability
Original language description
Mančinska and Roberson [FOCS'20] showed that two graphs are quantum isomorphic if andonly if they are homomorphism indistinguishable over the class of planar graphs. Atserias etal. [JCTB'19] proved that quantum isomorphism is undecidable in general. The NPA hierarchy givesa sequence of semidefinite programming relaxations of quantum isomorphism. Recently, Robersonand Seppelt [ICALP'23] obtained a homomorphism indistinguishability characterization of thefeasibility of each level of the Lasserre hierarchy of semidefinite programming relaxations of graphisomorphism. We prove a quantum analogue of this result by showing that each level of the NPAhierarchy of SDP relaxations for quantum isomorphism of graphs is equivalent to homomorphismindistinguishability over an appropriate class of planar graphs. By combining the convergence of theNPA hierarchy with the fact that the union of these graph classes is the set of all planar graphs, weare able to give a new proof of the result of Mančinska and Roberson [FOCS'20] that avoids the useof the theory of quantum groups. This homomorphism indistinguishability characterization alsoallows us to give a randomized polynomial-time algorithm deciding exact feasibility of each fixedlevel of the NPA hierarchy of SDP relaxations for quantum isomorphism
Czech name
—
Czech description
—

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2025
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Leibniz International Proceedings in Informatics, LIPIcs
ISBN
978-3-95977-409-3
ISSN
1868-8969
e-ISSN
1868-8969
Number of pages
19
Pages from-to
1-19
Publisher name
Schloss Dagstuhl, Leibniz-Zentrum für Informatik
Place of publication
Wadern
Event location
Aarhus, Dánsko
Event date
Jul 8, 2025
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)