License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2023.33
URN: urn:nbn:de:0030-drops-180851
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18085/
Cai, Jin-Yi ;
Young, Ben
Planar #CSP Equality Corresponds to Quantum Isomorphism - A Holant Viewpoint
Abstract
Recently, Mančinska and Roberson proved [Mančinska and Roberson, 2020] that two graphs G and G' are quantum isomorphic if and only if they admit the same number of homomorphisms from all planar graphs. We extend this result to planar #CSP with any pair of sets ℱ and ℱ' of real-valued, arbitrary-arity constraint functions. Graph homomorphism is the special case where each of ℱ and ℱ' contains a single symmetric 0-1-valued binary constraint function. Our treatment uses the framework of planar Holant problems. To prove that quantum isomorphic constraint function sets give the same value on any planar #CSP instance, we apply a novel form of holographic transformation of Valiant [Valiant, 2008], using the quantum permutation matrix ? defining the quantum isomorphism. Due to the noncommutativity of ?’s entries, it turns out that this form of holographic transformation is only applicable to planar Holant. To prove the converse, we introduce the quantum automorphism group Qut(ℱ) of a set of constraint functions/tensors ℱ, and characterize the intertwiners of Qut(ℱ) as the signature matrices of planar Holant(ℱ | EQ) quantum gadgets. Then we define a new notion of (projective) connectivity for constraint functions and reduce arity while preserving the quantum automorphism group. Finally, to address the challenges posed by generalizing from 0-1 valued to real-valued constraint functions, we adapt a technique of Lovász [László Lovász, 1967] in the classical setting for isomorphisms of real-weighted graphs to the setting of quantum isomorphisms.
BibTeX - Entry
@InProceedings{cai_et_al:LIPIcs.ICALP.2023.33,
author = {Cai, Jin-Yi and Young, Ben},
title = {{Planar #CSP Equality Corresponds to Quantum Isomorphism - A Holant Viewpoint}},
booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
pages = {33:1--33:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-278-5},
ISSN = {1868-8969},
year = {2023},
volume = {261},
editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18085},
URN = {urn:nbn:de:0030-drops-180851},
doi = {10.4230/LIPIcs.ICALP.2023.33},
annote = {Keywords: #CSP, Quantum isomorphism, Holant, Gadget, Intertwiners, Planar graphs}
}
|
Keywords: |
|
#CSP, Quantum isomorphism, Holant, Gadget, Intertwiners, Planar graphs |
|
Collection: |
|
50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
05.07.2023 |
