{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T23:20:36Z","timestamp":1769642436579,"version":"3.49.0"},"reference-count":32,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T00:00:00Z","timestamp":1769558400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"ERC","award":["101071674"],"award-info":[{"award-number":["101071674"]}]},{"name":"ERC","award":["101077083"],"award-info":[{"award-number":["101077083"]}]},{"name":"ERC","award":["101054974"],"award-info":[{"award-number":["101054974"]}]},{"name":"DFG","award":["2236\/2"],"award-info":[{"award-number":["2236\/2"]}]},{"name":"Carlsberg Semper Ardens Accelerate","award":["CF21-0682"],"award-info":[{"award-number":["CF21-0682"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"Man\u010dinska and Roberson [FOCS&apos;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&apos;19] proved that quantum isomorphism is undecidable in general, which motivates the study of its relaxations. In the classical setting, Roberson and Seppelt [ICALP&apos;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\u010dinska and Roberson [FOCS&apos;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.<\/jats:p>","DOI":"10.22331\/q-2026-01-28-1989","type":"journal-article","created":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T10:27:43Z","timestamp":1769596063000},"page":"1989","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":0,"title":["NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability"],"prefix":"10.22331","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-8235-9233","authenticated-orcid":false,"given":"Prem Nigam","family":"Kar","sequence":"first","affiliation":[{"name":"Technical University of Denmark"},{"name":"Instytut Matematyczny Polskiej Akademii Nauk"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4463-8095","authenticated-orcid":false,"given":"David E.","family":"Roberson","sequence":"additional","affiliation":[{"name":"Technical University of Denmark"},{"name":"QMATH, University of Copenhagen"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6447-0568","authenticated-orcid":false,"given":"Tim","family":"Seppelt","sequence":"additional","affiliation":[{"name":"IT-Universitetet i K\u00f8benhavn"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0071-9149","authenticated-orcid":false,"given":"Peter","family":"Zeman","sequence":"additional","affiliation":[{"name":"Department of Algebra, Faculty of Mathematics and Physics, Charles University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9598","published-online":{"date-parts":[[2026,1,28]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz. ``Operations with structures''. Acta Mathematica Academiae Scientiarum Hungarica 18, 321\u2013328 (1967).","DOI":"10.1007\/BF02280291"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Zden\u011bk Dvo\u0159\u00e1k. ``On recognizing graphs by numbers of homomorphisms''. Journal of Graph Theory 64, 330\u2013342 (2010).","DOI":"10.1002\/jgt.20461"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Martin Grohe. ``Counting bounded tree depth homomorphisms''. In Proceedings of the 35th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS). Pages 507\u2013520. (2020).","DOI":"10.1145\/3373718.3394739"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Eva Fluck, Tim Seppelt, and Gian Luca Spitzer. ``Going Deep and Going Wide: Counting Logic and Homomorphism Indistinguishability over Graphs of Bounded Treedepth and Treewidth''. In 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024). Volume 288, pages 27:1\u201327:17. (2024).","DOI":"10.4230\/LIPIcs.CSL.2024.27"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Holger Dell, Martin Grohe, and Gaurav Rattan. ``Lov\u00e1sz Meets Weisfeiler and Leman''. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Volume 107, pages 40:1\u201340:14. (2018).","DOI":"10.4230\/LIPIcs.ICALP.2018.40"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Martin Grohe, Gaurav Rattan, and Tim Seppelt. ``Homomorphism Tensors and Linear Equations''. Advances in Combinatorics (2025).","DOI":"10.19086\/aic.2025.4"},{"key":"6","doi-asserted-by":"publisher","unstructured":"David E. Roberson and Tim Seppelt. ``Lasserre hierarchy for graph isomorphism and homomorphism indistinguishability''. TheoretiCS (2024).","DOI":"10.46298\/theoretics.24.20"},{"key":"7","unstructured":"Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. ``How Powerful are Graph Neural Networks?''. In International Conference on Learning Representations. (2018). url: https:\/\/openreview.net\/forum?id=ryGs6iA5Km."},{"key":"8","doi-asserted-by":"publisher","unstructured":"Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. ``Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks''. Proceedings of the AAAI Conference on Artificial Intelligence 33, 4602\u20134609 (2019).","DOI":"10.1609\/aaai.v33i01.33014602"},{"key":"9","unstructured":"Bohang Zhang, Jingchu Gai, Yiheng Du, Qiwei Ye, Di He, and Liwei Wang. ``Beyond Weisfeiler\u2013Lehman: A Quantitative Framework for GNN Expressiveness''. In The Twelfth International Conference on Learning Representations. (2024). url: https:\/\/openreview.net\/forum?id=HSKaGOi7Ar."},{"key":"10","doi-asserted-by":"publisher","unstructured":"Anuj Dawar, Tom\u00e1\u0161 Jakl, and Luca Reggio. ``Lov\u00e1sz-Type Theorems and Game Comonads''. In 36th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2021, Rome, Italy, June 29 - July 2, 2021. Pages 1\u201313. IEEE (2021).","DOI":"10.1109\/LICS52264.2021.9470609"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Samson Abramsky, Tom\u00e1\u0161 Jakl, and Thomas Paine. ``Discrete Density Comonads and Graph Parameters''. In Helle Hvid Hansen and Fabio Zanasi, editors, Coalgebraic Methods in Computer Science. Pages 23\u201344. Cham (2022). Springer International Publishing.","DOI":"10.1007\/978-3-031-10736-8_2"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Yo\u00e0v Montacute and Nihil Shah. ``The Pebble-Relation Comonad in Finite Model Theory''. In Christel Baier and Dana Fisman, editors, LICS '22: 37th Annual ACM\/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2 - 5, 2022. Pages 13:1\u201313:11. ACM (2022).","DOI":"10.1145\/3531130.3533335"},{"key":"13","unstructured":"David E. Roberson. ``Oddomorphisms and homomorphism indistinguishability over graphs of bounded degree'' (2022). arXiv:2206.10321v1."},{"key":"14","doi-asserted-by":"publisher","unstructured":"Tim Seppelt. ``Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors''. In J\u00e9r\u00f4me Leroux, Sylvain Lombardy, and David Peleg, editors, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Volume 272 of Leibniz International Proceedings in Informatics (LIPIcs), pages 82:1\u201382:15. Dagstuhl, Germany (2023). Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik.","DOI":"10.4230\/LIPIcs.MFCS.2023.82"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Daniel Neuen. ``Homomorphism-Distinguishing Closedness for Graphs of Bounded Tree-Width''. In Olaf Beyersdorff, Mamadou Moustapha Kant\u00e9, Orna Kupferman, and Daniel Lokshtanov, editors, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Volume 289 of Leibniz International Proceedings in Informatics (LIPIcs), pages 53:1\u201353:12. Dagstuhl, Germany (2024). Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik.","DOI":"10.4230\/LIPIcs.STACS.2024.53"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Tim Seppelt. ``An Algorithmic Meta Theorem for Homomorphism Indistinguishability''. In Rastislav Kr\u00e1lovi\u010d and Anton\u00edn Ku\u010dera, editors, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Volume 306 of Leibniz International Proceedings in Informatics (LIPIcs), pages 82:1\u201382:19. Dagstuhl, Germany (2024). Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik.","DOI":"10.4230\/LIPIcs.MFCS.2024.82"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Tim Seppelt. ``Homomorphism Indistinguishability''. Dissertation. RWTH Aachen University. Aachen (2024).","DOI":"10.18154\/RWTH-2024-11629"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Laura Man\u010dinska and David E. Roberson. ``Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs''. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). Pages 661\u2013672. (2020).","DOI":"10.1109\/FOCS46700.2020.00067"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Albert Atserias, Laura Man\u010dinska, David E. Roberson, Robert \u0160\u00e1mal, Simone Severini, and Antonios Varvitsiotis. ``Quantum and non-signalling graph isomorphisms''. Journal of Combinatorial Theory, Series B 136, 289\u2013328 (2019).","DOI":"10.1016\/j.jctb.2018.11.002"},{"key":"20","doi-asserted-by":"publisher","unstructured":"L\u00e1szl\u00f3 Babai. ``Graph isomorphism in quasipolynomial time [extended abstract]''. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016. Pages 684\u2013697. ACM (2016).","DOI":"10.1145\/2897518.2897542"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Miguel Navascu\u00e9s, Stefano Pironio, and Antonio Ac\u00edn. ``A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations''. New Journal of Physics 10, 073013 (2008).","DOI":"10.1088\/1367-2630\/10\/7\/073013"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Gaurav Rattan and Tim Seppelt. ``Weisfeiler\u2013Leman and Graph Spectra''. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Pages 2268\u20132285. Society for Industrial and Applied Mathematics (2023).","DOI":"10.1137\/1.9781611977554.ch87"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Michael A. Nielsen and Isaac L. Chuang. ``Quantum computation and quantum information: 10th anniversary edition''. Cambridge University Press. (2010).","DOI":"10.1017\/CBO9780511976667"},{"key":"24","doi-asserted-by":"publisher","unstructured":"Laura Man\u010dinska, David E. Roberson, and Antonios Varvitsiotis. ``Graph isomorphism: physical resources, optimization models, and algebraic characterizations''. Math. Program. 205, 617\u2013660 (2024).","DOI":"10.1007\/s10107-023-01989-7"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Neil Robertson and Paul D. Seymour. ``Graph minors. iii. planar tree-width''. Journal of Combinatorial Theory, Series B 36, 49\u201364 (1984).","DOI":"10.1016\/0095-8956(84)90013-3"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. ``PRIMES is in P''. Annals of Mathematics 160, 781\u2013793 (2004).","DOI":"10.4007\/annals.2004.160.781"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Man-Duen Choi. ``Completely positive linear maps on complex matrices''. Linear Algebra and its Applications 10, 285\u2013290 (1975).","DOI":"10.1016\/0024-3795(75)90075-0"},{"key":"28","unstructured":"John Watrous. ``Advanced topics in quantum information theory'' (2020)."},{"key":"29","doi-asserted-by":"publisher","unstructured":"Travis B. Russell. ``A synchronous NPA hierarchy with applications''. Operators and Matrices 17, 901\u2013924 (2023).","DOI":"10.7153\/oam-2023-17-60"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Miguel Navascu\u00e9s, Stefano Pironio, and Antonio Ac\u00edn. ``Sdp relaxations for non-commutative polynomial optimization''. Pages 601\u2013634. Springer US. New York, NY (2012).","DOI":"10.1007\/978-1-4614-0769-0_21"},{"key":"31","unstructured":"Gereon Ko\u00dfmann, Ren\u00e9 Schwonnek, and Jonathan Steinberg. ``Hierarchies for Semidefinite Optimization in $C^\\star$-Algebras'' (2023). url: http:\/\/arxiv.org\/abs\/2309.13966."}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2026-01-28-1989\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T10:30:37Z","timestamp":1769596237000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2026-01-28-1989\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,28]]},"references-count":32,"URL":"https:\/\/doi.org\/10.22331\/q-2026-01-28-1989","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,28]]},"article-number":"1989"}}