NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability
Identifikátory výsledku
Kód výsledku v 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>
Výsledek na webu
<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>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability
Popis výsledku v původním jazyce
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
Název v anglickém jazyce
NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability
Popis výsledku anglicky
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
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
—
OECD FORD obor
10101 - Pure mathematics
Návaznosti výsledku
Projekt
—
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2025
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
Leibniz International Proceedings in Informatics, LIPIcs
ISBN
978-3-95977-409-3
ISSN
1868-8969
e-ISSN
1868-8969
Počet stran výsledku
19
Strana od-do
1-19
Název nakladatele
Schloss Dagstuhl, Leibniz-Zentrum für Informatik
Místo vydání
Wadern
Místo konání akce
Aarhus, Dánsko
Datum konání akce
8. 7. 2025
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—