{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:02:32Z","timestamp":1750309352746,"version":"3.41.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,9,10]],"date-time":"2024-09-10T00:00:00Z","timestamp":1725926400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2024,9,30]]},"abstract":"\n Recently, Man\u010dinska and Roberson proved that two graphs\n G<\/jats:italic>\n and\n \n \\(G^{\\prime }\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n are\n quantum isomorphic<\/jats:italic>\n if and only if they admit the same number of homomorphisms from all\n planar<\/jats:italic>\n graphs. We extend this result to planar #CSP with any pair of sets\n \n \\(\\mathcal {F}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and\n \n \\(\\mathcal {F}^{\\prime }\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n of real-valued, arbitrary-arity constraint functions. Graph homomorphism is the special case, in which each of\n \n \\(\\mathcal {F}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and\n \n \\(\\mathcal {F}^{\\prime }\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n 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\n holographic transformation<\/jats:italic>\n of Valiant, using the quantum permutation matrix\n \n \\(\\mathcal {U}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n defining the quantum isomorphism. Due to the noncommutativity of\n \n \\(\\mathcal {U}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n \u2019s 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\n \n \\(Qut(\\mathcal {F})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n of a set\n \n \\(\\mathcal {F}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n of constraint functions\/tensors and characterize the intertwiners of\n \n \\(Qut(\\mathcal {F})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n as the signature matrices of planar\n \n \\(\\text{Holant}{\\mathcal {F}\\,|\\,\\mathcal {EQ})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n quantum gadgets. Then, we define a new notion of (projective) connectivity for constraint functions and reduce their arity while preserving their inclusion in the original intertwiner space. Finally, to address the challenges posed by generalizing from 0-1 valued to real-valued constraint functions, we adapt a technique of Lov\u00e1sz in the classical setting for isomorphisms of real-weighted graphs to the setting of quantum isomorphisms.\n <\/jats:p>","DOI":"10.1145\/3689486","type":"journal-article","created":{"date-parts":[[2024,8,23]],"date-time":"2024-08-23T12:25:27Z","timestamp":1724415927000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Planar #CSP Equality Corresponds to Quantum Isomorphism \u2013 A Holant Viewpoint"],"prefix":"10.1145","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-0675-6060","authenticated-orcid":false,"given":"Jin-Yi","family":"Cai","sequence":"first","affiliation":[{"name":"Computer Sciences, University of Wisconsin-Madison, Madison, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1921-7253","authenticated-orcid":false,"given":"Ben","family":"Young","sequence":"additional","affiliation":[{"name":"Computer Sciences, University of Wisconsin-Madison, Madison, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,9,10]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","unstructured":"Samson Abramsky. 2009. Temperley-Lieb Algebra: From Knot Theory to Logic and Computation via Quantum Mechanics. (2009). DOI:10.48550\/ARXIV.0910.2737","DOI":"10.48550\/ARXIV.0910.2737"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-6371-5"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2018.11.002"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jfa.2004.11.002"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2009.06.009"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/2528400"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1032314"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548321000286"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781107477063.002"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/2822891"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3448641"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2023.33"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","unstructured":"Arthur Chassaniol. 2019. Study of Quantum Symmetries for Vertex-transitive Graphs using Intertwiner Spaces. (2019). DOI:10.48550\/ARXIV.1904.00455","DOI":"10.48550\/ARXIV.1904.00455"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.09.005"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/100811258"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-06-00529-7"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","unstructured":"Daniel Gromada. 2021. Quantum Symmetries of Cayley Graphs of Abelian Groups. (2021). DOI:10.48550\/ARXIV.2106.08787","DOI":"10.48550\/ARXIV.2106.08787"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2019.07.005"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(87)90326-0"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02280291"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2005.04.012"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jfa.2020.108592"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00067"},{"key":"e_1_3_3_25_2","unstructured":"J. P. McCarthy. 2023. Tracing the Orbitals of the Quantum Permutation Group. (2023). arxiv:math.QA\/2302.05902"},{"key":"e_1_3_3_26_2","article-title":"Applications of quasigroups in cryptography","author":"Petrescu Adrian","year":"2007","unstructured":"Adrian Petrescu. 2007. Applications of quasigroups in cryptography. Interdisciplinarity in Engineering Scientific International Conference (092007).","journal-title":"Interdisciplinarity in Engineering Scientific International Conference"},{"key":"e_1_3_3_27_2","volume-title":"Private communication","author":"Roberson David","year":"2023","unstructured":"David Roberson. 2023. Private communication. (2023)."},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.10.003"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12821-9_4"},{"issue":"5","key":"e_1_3_3_30_2","doi-asserted-by":"crossref","first-page":"1565","DOI":"10.1137\/070682575","article-title":"Holographic algorithms","author":"Valiant Leslie G.","year":"2008","unstructured":"Leslie G. Valiant. 2008. Holographic algorithms. SIAM J. Comput.5 (2008), 1565\u20131594.","journal-title":"SIAM J. Comput."},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02101540"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/s002200050385"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01219077"},{"issue":"1","key":"e_1_3_3_34_2","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/BF01393687","article-title":"Tannaka-Krein duality for compact matrix pseudogroups. TwistedSU(N) groups","volume":"93","author":"Woronowicz S. L.","year":"1988","unstructured":"S. L. Woronowicz. 1988. Tannaka-Krein duality for compact matrix pseudogroups. TwistedSU(N) groups. Inventiones mathematicae 93, 1 (Feb.1988), 35\u201376.","journal-title":"Inventiones mathematicae"},{"key":"e_1_3_3_35_2","unstructured":"Ben Young. 2022. Equality on All #CSP Instances Yields Constraint Function Isomorphism via Interpolation and Intertwiners. (2022). arxiv:cs.DM\/2211.13688"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3689486","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3689486","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:05:46Z","timestamp":1750291546000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3689486"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,10]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,9,30]]}},"alternative-id":["10.1145\/3689486"],"URL":"https:\/\/doi.org\/10.1145\/3689486","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2024,9,10]]},"assertion":[{"value":"2023-10-26","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-08-07","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-10","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}